--
11.1 遗传算法及其在机构参数优化中的应用
基于进化规律的遗传算法（Genetic Algorithm）简称GA，是一种模拟生物进化过程的
随机全局优化搜索方法。GA最早是由美国科学家J.H.Holland教授在1975年提出来的，自20世纪80年代中期以来，由于计算机容量的不断扩大和速度的不断提高，以及GA方法本身的逐步成熟，GA得到了迅速的发展。它具有很强的鲁棒性和通用优化能力，优化计算时只需适应度函数值（适值），不需要导数信息，可应用于科学研究和工程实际中的各种搜索过程和优化问题，特别是能较有效地求解常规优化方法难以解决的组合优化问题和大型复杂非线性系统的全局寻优问题，因此适用范围广。目前，其应用遍布于计算机科学、物理学、社会学、图像处理、生产管理、企业经营规划、最优控制等领域。近年来，GA在机构参数优化方面的应用也越来越多。
11.1.1 遗传算法原理
生物的进化是一个依照群体遗传与自然选择机理进行的过程，优胜劣汰，适者生存，有利于生存的基因遗传给下一代，含不利于生存的基因的个体产生子代机会较小而逐渐消亡。基于这一原理，GA搜索首先是利用随机方法产生一初始群体（祖先），这一点与传统的搜索方法不同。群体中的每个个体称为染色体，它是一串符号，比如一个二进制字符串，对应着优化问题的一个设计向量（即一个可能解）。染色体的最小组成元素称为基因，如二进制字符串的一位。基因与设计变量的关系取决于编码方法。例如，采用实数编码时，基因即
解空间编码 初始群体 结 果 解码评价 后代 选 择 新种群 杂 交
图11.13 遗传算法过程 变 异 对应某一设计变量（即可能解的某一特征）；采用二进制编码时，若干个基因对应一个设计变量。搜索过程中，这些染色体不断遗传进化，产生下一代，即称为后代。染色体的后代是前一代通过杂交、变异操作产生的。新一代群体的形成是按照优胜劣汰的原则对染色体进行选择，相对好的个体被选中的概率高，得以繁殖，相对差的个体将趋于死亡。因此，通过选择、杂交、变异等过程，群体的整体性能趋于改善。经过若干代繁衍进化，群体性能趋于最佳。
--
--
遗传算法的主要步骤如下：在当代群体中，使用解码后设计变量的适应度函数值评价该代中的每个染色体，按照适值的概率分布选择新群体，然后，通过变异和杂交算子改变新群体中的染色体。如果在经过若干代后，观察不到更进一步的改进，最好染色体就作为一个可能的全局最优解。通常根据工程实际问题及计算速度和资源情况确定一固定代数，在循环结束后停止计算。这一过程可用图11.13表示。
11.1.2 遗传算法的一些基本操作
1.
编码和解码
从设计空间向遗传空间（由染色体个体组成）的映射称为编码，反之称为解码。对于一个实际待优化问题，首先要将根据具体问题确定的一组寻优参数即设计向量X表示为适合于遗传算法操作的二进制码串，即染色体。
例如，欲求一个有n个设计变量的函数f(X)= f(x1, ···,xn)的最大值。事先需确定每个参数的变化范围，设参数xi的变化范围为[ximin, ximax]，即设计变量xi为域Di=[ai，bi]＝[ximin， ximax]?R内的一个值，也就是对所有xi?Di, f(x1, ···,xn)>0。假定以某个要求的精度来优化函数f：这里取设计变量小数点后第6位。显然，为达到这样的精度，每个域Di应该被分割成 (bi – ai)?106份等长度的区间。令mi表示使 (bi – ai)?106?2mi–1成立的最小整数，则对每个变量，由串长为mi的二进制编码表达能满足精度要求。因此，公式
xi = ai + decimal (substringi) ·
bi?ai （i=1,2,3, ···,n ） （11.5.1）
2mi?1对应于每一二进制串substringi的设计变量的十进制值。式中，decimal (substringi)表示二进制串的十进制值。
设计变量xi的编码精度为
Ai＝
bi?ai （11.5.2）
2mi?1由上式可见，mi长则编码精度高，但是遗传算法的复杂性增加。
显然，设计变量的码串长度mi不仅与计算精度有关，还与其变化范围有关。各设计变量可以根据实际工程需要取不同的计算精度。
最后，将所有表示设计变量的二进制码串接起来组成一个长的总二进制码串，构成染色体v，它就是遗传算法可以操作的对象。这样，代表一个潜在解的染色体二进制串总长度为m=
?mi?1ki，前m1位对应区间[a1，b1]中的一个值x1，随后的m2位对应区间[a2，b2]中的一个
值x2，······ ，最后的mk位对应区间[ak，bk]中的一个值xk。
2.
初始群体的产生
这里要解决两个问题，即群体规模popsize和初始群体的产生。
群体规模越大，GA所处理的模式越多，陷入局部解的可能性越小，即不易陷入未成熟收敛。但规模过大会大大增加计算量，影响算法效率。实际应用时需要根据具体问题来确定。
至于初始群体确定方法一种是完全随机的方法，如用掷硬币的方法，正面表示1，反面
--
--
表示0，不断掷，直至产生popsize个染色体。若对所求解的问题具有某些最优分布的先验知识，可首先将这些先验知识转变为必须满足的一组要求，在满足这些要求的前提下随机地选取样本。例如，若知最优解在问题空间中的分布范围，可在此范围内选初始群体。
3.
染色体的评价
染色体的好坏通过其适值大小来评价，所以，适应度函数是评价各群体或个体是否优化、先进的准则，或者说适应度函数具有测定染色体对目标的适应性的作用。例如，对于机构参数优化问题，可以直接将目标函数作为适应度函数。因此，简单的适应度函数可以用一个公式来表示，如误差平方积分、二次型性能指标等。对于复杂系统，可能要对系统仿真，由多个目标值来判断；或者要通过一系列规则要求，经过多个步骤才能求得适值，而不能用公式来表达。
遗传算法讨论的问题一般都是适值为正且求最大值问题。若目标函数f可能为负，则可通过加法机制来调整，即加入某个适当大的正常数C(计算时取群体中的最大适值或某一足够大的数)使之为正，也就是问题转化为
maxf(X) ?max{f(X)+C}
如果优化问题是求函数f的最小值，它等同于求函数g的最大值，其中g = –f，即
minf( X) = max g(X) = max {–f(X)} （11.5.3）
4.
遗传操作
遗传操作是遗传算法的核心，其重要特点是有向随机的。操作的效果与效率取决于编码的方式、群体规模、初始种群、适应度函数及各个遗传操作概率。
（1）选择——复制。选择——复制操作的目的是选出群体中优质（如适值高）的个体，淘汰劣质个体，并使优质个体直接遗传或得以配对杂交。
对基于适值的概率分布选择新群体的过程，称为正比选择或轮盘选择，其基本思想是每个染色体的选择概率（即生存概率）正比于它的适值。通常，使用一个按照如下方法构造的一个轮盘：
? 计算每个染色体vi的适应值eval(vi) (i=1,2，···, popsize)。 ? 计算群体的总适值
popsizeF =
?i?1eval(vi) （11.5.4）
? 计算每个染色体vi的选择概率（生存概率）pi，
pi = eval(vi)/F (i=1, ···, popsize) （11.5.5）
? 计算每个vi染色体的累积概率qi，（区间大小）
qi =
?pj?1ij (i=1, ···, popsize) （11.5.6）
对轮盘转动popsize次，每次按照下面的方法为新群体选择一个单个的染色体：产生一个在区间[0，1]里的随机数r，如果r --
遗传算法及其在机构参数优化中的应用
