三、遗传算法
遗传算法（Genetic Algorithm，简称GA）是一类模拟生物界自然选择和遗传的启发式
随机搜索算法。标准遗传算法的步骤包括编码、初始群体的生成、适应度评估和检测、选择、
交叉操作和变异操作。它是一种具有“生成+检测”的迭代过程的搜索算法，如图11.5 所示。
编 码
初始群体的生成
群体中个体适应度函数的评估
交 叉
终止？
结束
选 择
变 异
是
否
图11.5 标准遗传算法的流程图
（一）编码
编码的作用是将设计变量表示成遗传空间的基因型串结构数据。通常采用一定长度的二
进制码代表设计变量的各种取值。对于连续变量，如果设计变量的精度指定为Z，下限为XL，
上限为XU，那么二进制码的长度K为：
2K ≥ [(XU – XL)/ Z + 1 ]
对于离散变量，如果离散变量可能取值数为M，那么二进制码的长度K 为：
2K ≥ M
将各个变量的二进制码连成一串，得到一个二进制代码串，它代表了设计空间的一个点。二
进制码所有可能的结构代表了整个设计空间。因此，GA 中的编码技术可统一地将含连续/离
散变量的设计空间用一系列二进制代码来表示。
（二）初始群体的生成
遗传算法是一种群体操作算法，必须为遗传操作准备一个由若干初始解组成的初始群体。
通常采用随机方法来产生初始群体。群体规模的确定对遗传算法的效果有影响。群体规模越
· 171 ·
大，GA 陷入局部最优解的危险性越小，但计算量会增加；群体规模太小，会使GA 在搜索空
间中分布范围有限，会引起未成熟收敛现象。
（三）适应度函数的评估
遗传算法在进化搜索中基本上不用外部信息，仅用目标函数即适应度函数为依据。适应
度函数评估是选择操作的依据。由于适应度函数应为非负值。一般需将目标函数以一定的方
式映射成适应度函数。适应度函数的设计直接影响到算法的性能。
（四）选择算子
选择算子的目的是把优化的个体(或设计点)直接遗传到下一代或通过配对交叉产生新的
个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的，适应度越大的
个体，被选中的概率越大，也就是说适应度越高的个体，有更多的机会繁殖后代，使其优良
特性得以遗传和保留。常用的选择方法有适应度比例方法、最佳个体保留方法、期望值方法、
排序选择和联赛选择方法。
（五）交叉操作
在自然界生物进化过程中起核心作用的是生物遗传基因的重组。遗传算法中起核心作用
的遗传操作的交叉算子。所谓交叉是指把两个父代个体的部份结构加以替换重组而生成新的
个体，通过交叉，遗传算法的搜索能力得以飞跃提高。最简单的交叉算子是一点交叉
(one-point crossover)：随机地选取一个截断点，将双亲的基因码串在截断点切开，然后交
换其尾部：
双亲 后代
1000┆10011110 ——→ 1000┆11000110
0010┆11000110 ——→ 0010┆10011110
另一种常用的交叉算子是一致交叉(uniform crossover)，它是通过设定屏蔽字(mask)来决定
新个体的基因继承两个旧个体中哪个个体的对应基因。一致交叉的操作过程是：当屏蔽字中
的位为0 时，新个体A′继承旧个体A 中对应的基因，当屏蔽字位为1 时，新个体A′继承旧
个位B 中对应的基因，由此生成一个完整的新个体A′，反之，可生成新个体B′。例如：
旧个体A 0 0 1 1 1 1
旧个体B 1 1 1 1 0 0
屏蔽字 0 1 0 1 0 1
新个体A′ 0 1 1 1 1 0
新个体B′ 1 0 1 1 0 1
（六）变异算子
变异算子的目的是模拟生物在自然的遗传环境中由于各种偶然因素引起的基因突变。其
方法是以一定的概率选取群体中若干个体，对已选取的每个个体，随机选取某一位，将该位
的数码翻转。变异算子增加了群体基因材料的多样性，增加了自然选择的余地，有利的变异
将由于选择操作的作用，得以遗传与保留，而有害的变异则将在逐代遗传中被淘汰。
通过用选择、交叉、变异得到的新一代群体代替其上一代群体，再进行评估、选择、交
叉、变异。如此迭代下去，各代群体的优良基因成份逐渐积累，群体的平均适应度和最优个
体适应度不断上升，直到迭代过程趋于收敛，适应度趋于稳定，不再上升时，就找到了所需
· 172 ·
的最优解。
与传统的优化算法相比，遗传算法的优点主要有以下三方面：
(1) GA 处理的对象广
GA 处理的是计算对象编码，因此它对处理对象的性质几乎没有限制，对象可以是连续变
量、离散变量、各种数据结构和树等。
(2) GA 是一种搜索全局最优解的算法
许多传统的搜索方法都是单点搜索算法，即通过一些变动规则，问题的解从搜索空间中
的当前解(点)移动到另一解(点)。这种单点搜索方法对于多峰分布的设计空间常常会陷于局
中国航空网 www.aero.cn
航空翻译 www.aviation.cn
本文链接地址：飞机总体设计(55)
