第四章 遗传算法的实现技术 80年代以后，遗传算法得到了广泛的使用，在实践过程中，人们对遗传算法的实施提出了许多改进。本节分别予以介绍。

Presentation on theme: "第四章 遗传算法的实现技术 80年代以后，遗传算法得到了广泛的使用，在实践过程中，人们对遗传算法的实施提出了许多改进。本节分别予以介绍。"— Presentation transcript:

1 第四章 遗传算法的实现技术 80年代以后，遗传算法得到了广泛的使用，在实践过程中，人们对遗传算法的实施提出了许多改进。本节分别予以介绍。
第四章 遗传算法的实现技术 80年代以后，遗传算法得到了广泛的使用，在实践过程中，人们对遗传算法的实施提出了许多改进。本节分别予以介绍。 4.1 编码方法 [编码的重要性] 编码是应用遗传算法时要解决的首要问题，也是设计遗传算法的一个关键步骤。 • 编码方法除了决定个体的染色体排列形式之外，它还决定了个体从搜索空间 的基因型变换到解空间的表现型时的解码方法; • 编码方法也影响到交叉算子、变异算子等遗传算子的运算方法。 由此可见，编码方法在很大程度上决定了如何进行群体的遗传进化运算以及 遗传进化运算的效率。

2 [编码原则] 针对一个具体应用问题，如何设计一种完美的编码方案一直是遗传算法的应 用难点之一，也是遗传算法的一个重要研究方向。可以说目前还没有一套既严密 又完整的指导理论及评价准则能够帮助我们设计编码方案。作为参考，De Jong 曾提出了两条操作性较强的实用编码原则(又称为编码规则)： • 编码原则一(有意义积木块编码原则)：应使用能易于产生与所求问题相关的且 具有低阶、短定义长度模式的编码方案。 • 编码原则二(最小字符集编码原则)：应使用能使问题得到自然表示或描述的具 有最小编码字符集的编码方案。 由于遗传算法应用的广泛性，迄今为止人们已经提出了许多种不同的编码方法。 总的来说，这些编码方法可以分为三大类： 二进制编码方法 浮点数编码方法 符号编码方法

3 二进制编码方法 二进制编码方法是遗传算法中最常用的一种编码方法，它使用的编码符号集 是由二进制符号0和1所组成的二值符号集{0，1}，它所构成的个体基因型是一个 二进制编码符号串。 (1) 编码 假设某一参数的取值范围是[umax, umin]，我们用长度为l的二进制编码符号串 来表示该参数，则它总共能够产生 2l种不同的编码，参数编码时的对应关系如 下： … ＝ umin … ＝ umin +  …… … =2l– umax 二进制编码的编码精度为：  = Umax  umin 2l  1

4 例如，对于 x[ 0, 1023] ，若用 10 位长的二进制编码表示该参数的话， 则下述符号串：
(2) 解码 假设某一个体的编码是： x： bl bl-1 bl-2……b2b1 则对应的解码公式为： x = umin + (  bi · 2i-1) · 1 i=l Umax  umin 2l  1 例如，对于 x[ 0, 1023] ，若用 10 位长的二进制编码表示该参数的话， 则下述符号串： x： 就可表示一个个体， 它所对应的参数值是 x＝175。 编码精度为  = 1。

5 (3) 二进制编码方法的优点： Ⅰ. 编码、解码操作简单易行； Ⅱ. 交叉、变异等遗传操作便于实现； Ⅲ. 符合最小字符集编码原则（使用能使问题得到自然表示或描述的具有最小 编码字符集的编码方案。）； Ⅳ. 便于利用模式定理对算法进行理论分析。

6 4.1.2 格雷码编码方法 格雷码编码方法是二进制编码方法的一种变形。 (1) 格雷码编码：
格雷码编码方法 格雷码编码方法是二进制编码方法的一种变形。 (1) 格雷码编码： 其连续的两个整数所对应的编码值之间仅仅只有一个码位是不相同的， 其余码位都完全相同。如图所示。 (2) 优点： • 便于提高遗传算法的局部搜索能力； • 交叉、变异等遗传操作便于实现； • 符合最小字符集编码原则； • 便于利用模式定理对算法进行理论分析。

7 4

8 4.1.3 浮点数编码方法 (1) 二进制编码的缺点 • 二进制编码存在着连续函数离散化时的映射误差。
浮点数编码方法 (1) 二进制编码的缺点 • 二进制编码存在着连续函数离散化时的映射误差。 个体编码串的长度较短时，可能达不到精度要求； 个体编码串的长度较长时，虽然能提高编码精度，但却会使遗传算法的搜索 空间急剧扩大。 • 二进制编码不便于反映所求问题的特定知识，这样也就不便于开发针对问题专 门知识的遗传运算算子，人们在一些经典优化算法的研究中所总结出的一些 宝贵经验也就无法在这里加以利用，也不便于处理非平凡约束条件。 (2) 浮点数编码方法 个体的每个基因值用某一范围内的一个浮点数来表示； 个体的编码长度等于其决策变量的个数。 因为这种编码方法使用的是决策变量的真实值，所以浮点数编码方法也叫做 真值编码方法。

9 x: 例如，如果一个优化问题含有5个变量xi(i＝1,2,…,5)，每个变量都有其对应的上 下限[Uimin , Uimax]，则：
x: 表示一个体的基因型， 其对应的表现型是：x：[ 5.80，6.90，3.50，3.80，5.00]T。 (3) 注意事项： • 在浮点数编码方法中: 必须保证基因值在给定的区间限制范围内；遗传算法中所使用的交叉、变异 等遗传算子也必须保证其运算结果所产生的新个体的基因值也在这个区间限 制范围内。 • 当用多个字节来表示一个基因值时，交叉运算必须在两个基因的分界字节处进 行，而不能在某个基因的中间字节分隔处进行。

10 (4) 浮点数编码方法的优点： • 适合于在遗传算法中表示范围较大的数； • 适合于精度要求较高的遗传算法； • 便于较大空间的遗传搜索； • 改善了遗传算法的计算复杂性，提高了运算效率； • 便于遗传算法与经典优化方法的混合使用； • 便于设计针对问题的专门知识的知识型遗传算子； • 便于处理复杂的决策变量约束条件。

11 4.1.4 符号编码方法 (1) 编码方法 个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集。
符号编码方法 (1) 编码方法 个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集。 这个符号集可以是一个字母表，如 { A, B, C, D, …} ； 也可以是一个数宇序号表，如 { 1, 2, 3, 4, 5, …} ； 还可以是一个代码表，如 { Al, A2, A3, A4, A5, … } 等等。 例如 ：对于旅行商问题，假设有n个城市分别记为 C1, C2, …, Cn ，将各个城市的 代号按其被访问的顺序连接在一起，就可构成一个表示旅行路线的个体，如： X：[ C1, C2, …, Cn ] 若将各个城市按其代号的下标进行编号，则这个个体也可表示为： X：[1，2， …，n ] [ 旅行商问题(Traveling Salesman Problem，简称TSP)可描述为； 已知n个城市之间的相互距离。现有一推销员必须遍访这n个城市，并且每个城市 只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可 使其旅行路线的总长度最短? ]

12 4.1.5 多参数级联编码方法 4.1.5 多参数交叉编码方法 (2) 符号编码的主要优点： • 符合有意义积木块编码原则。
(2) 符号编码的主要优点： • 符合有意义积木块编码原则。 • 便于在遗传算法中利用所求解问题的专门知识。 • 便于遗传算法与相关近似算法之间的混合使用。 但对于使用符号编码方法的遗传算法，一般需要认真设计交叉、变异等遗传运 算的操作方法，以满足问题的各种约束要求，这样才能提高算法的搜索性能。 多参数级联编码方法 多参数交叉编码方法

13 4.2 适应度函数 4.2.1 目标函数与适应度函数 • 在研究自然界生物的遗传和进化现象时，生物学家使用适应度这个术语来度量
4.2 适应度函数 • 在研究自然界生物的遗传和进化现象时，生物学家使用适应度这个术语来度量 某个物种对于其生存环境的适应程度。 • 与此相类似，遗传算法中也使用适应度这个概念来度量群体中各个个体在优化 计算中有可能达到或接近于或有助于找到最优解的优良程度。 度量个体适应度的函数称为适应度函数。 目标函数与适应度函数 遗传算法的一个特点是它仅使用所求问题的目标函数值就可以得到下一步的 有关搜索信息。 最优化问题可分为两大类，一类为求目标函数的全局最大值，另一类为求目标函 数的全局最小值。对于这两类优化问题，第二章中已经介绍过由解空间中某一点的 目标函数值 f(x) 到搜索空间中对应个体的适应度函数值F(x)的转换方法： • 对于求最大值的问题，作下述转换： F(X) = f(X)+Cmin if f(X)+Cmin> 0 if f(X)+Cmin ≤ 0

14 4.2.2 适应度尺度变换 • 对于求最小值问题，变换如下： Cmax - f(X) if f(X)  Cmax
• 对于求最小值问题，变换如下： F(X) = Cmax - f(X) if f(X)  Cmax if f(X)  Cmax 适应度尺度变换 (1) 适应度尺度变换的原因 在遗传算法中，各个个体被遗传到下一代群体中的概率是由该个体的适应度来 确定的，应用实践表明，仅使用以上两式来计算个体适应度时，有些遗传算法 会收敛得很快，也有些遗传算法会收敛得很慢。 • 在遗传算法运行的初期阶段 群体中可能会有少数几个个体的适应度相对其他个体来说非常高。若按照常 用的比例选择算子来确定个体的遗传数量时，则这几个相对较好的个体将在下 一代群体中占有很高的比例，在极端情况下或当群体现模较小时，新的群体甚 至完全由这样的少数几个个体所组成。这时产生新个体作用较大的交叉算子就 起不了什么作用，因为相同的两个个体不论在何处进行交叉操作都永远不会产 生出新的个体，如下所示：

15 A: B: 单点交叉 这样就会使群体的多样性降低，容易导致遗传算法发生早熟现象（或称早期收 敛)，使遗传算法所求到的解停留在某一局部最优点上。 因此，我们希望在遗传算法运行的初期阶段，算法能够对一些适应度较高的个 体进行控制，降低其适应度与其他个体适应度之间的差异程度，从而限制其复 制数量，以维护群体的多样性。 • 在遗传算法运行的后期阶段 群体中所有个体的平均适应度可能会接近于群体中最佳个体的适应度。也就 是说，大部分个体的适应度和最佳个体的适应度差异不大，它们之间无竞争力， 都会有以相接近的概率被遗传到下一代的可能性，从而使得进化过程无竞争性 可言，只是一种随机的选择过程。这将导致无法对某些重点区域进行重点搜索， 从而影响遗传算法的运行效率。 因此，我们希望在遗传算法运行的后期阶段，算法能够对个体的适应度进行 适当的放大，扩大最佳个体适应度与其他个体适应度之间的差异程度，以提高 个体之间的竞争性。

16 (2) 适应度尺度变换定义 在遗传算法运行的不同阶段，有时需要对个体的适应度进行适当的扩大或缩小。 这种对个体适应度所做的扩大或缩小变换就称为适应度尺度变换。 (3) 适应度尺度变换方法 目前常用的个体适应度尺度变换方法主要有三种：线性尺度变换、乘幂尺度变 换和指数尺度变换。 Ⅰ. 线性尺度变换。 线性尺度变换的公式如下: F’ = aF + b 式中 F——原适应度； F’——变换后的新适应度； a,b——系数。 系数a,b直接影响到这个尺度变换的大小，所以对其选取有一定的要求，一般 希望它们满足下面两个条件:

17 条件1：尺度变换后全部个体的新适应度的平均值 F’avg 要等于其原适应度平均值Favg
这条要求是为了保证群体中适应度接近于平均适应度的个体能够有期待的数 量被遗传到下一代群体中。 条件2：尺度变换后群体中新的最大适应度 F’max 要等于其原平均适应度 Favg 的指定 倍数。即： F’max = CFavg 式中，C为最佳个体的期望复制数量，对于群体规模大小为50 ~ 100个个体的 情况，一般取 C = 1.2 ~ 2。 这条要求是为了保证群体中最好的个体能够期望复制C倍到新一代群体中。 如下图所示。

18

19 最小适应度为负时的处理： 在遗传算法执行的后期，个别劣质个体的适应度远远小于群体平均适应度及最 大适应度，并且后两者比较接近。这时按上述方法缩放适应度会使低适应度变成 负值，如图所示。这将会给后面的处理过程带来不便，必须避免这种情况的发生， 解决这个问题的方法是：把原最小适应度Fmin映射为Fmin= 0，并且保持原平均适 应度 Favg与新的平均适应度 F’avg 相等。

20 综上所述，参数a, b的计算方法如下： (1) 计算适应度非负判别式： Fmin > C · Favg - Fmax C -1 若不等式满足，则执行(2)， 否则执行(3)。 (2) 正常情况下的缩放： C - 1 a = Fmax - Favg Favg Fmax - C · Favg b = Fmax - Favg Favg (3) 负适应度时的缩放： a = Favg Favg - Fmin b = Favg · Fmin Favg - Fmin

21 Ⅱ. 乘幂尺度变换 乘幂尺度变换的公式为： F’ = Fk 即新的适应度是原有适应度的某个指定乘幂。幂指数k与所求解的问题有关， 并且在算法的执行过程中需要不断对其进行修正才能使尺度变换满足一定的伸 缩要求。 Ⅲ. 指数尺度变换 指数尺度变换的公式为： F’＝exp(-F) 即新的适应度是原有适应度的某个指数。式中系数决定了选择的强制性， 越小，原有适应度较高的个体的新适应度就越与其他个体的新适应度相差较 大，亦即越增加了选择该个体的强制性。

22 4.2.3 约束条件的处理方法 实际应用中的优化问题一般都含有一定的约束条件，它们的描述形式各种各样。
约束条件的处理方法 实际应用中的优化问题一般都含有一定的约束条件，它们的描述形式各种各样。 在遗传算法的应用中，必须对这些约束条件进行处理，而目前还未找到一种能够 处理各种约束条件的一般化方法。所以对约束条件进行处理时，只能是针对具体 应用问题及约束条件的特征，再考虑遗传算法中遗传算子的运行能力，选用不同 的处理方法。 在构造遗传算法时，处理约束条件的常用方法主要有如下三种： 搜索空间限定法 罚函数法 可行解变换法 (1) 搜索空间限定法 [基本思想] 对遗传算法的搜索空间的大小加以限制，使得搜索空间中表示一个个体的点与解空间中表示一个可行解的点有一一对应的关系。此时的搜索空间与解空间的对应关系如图所示。

23

24 [对一些比较简单的约束条件(如a<x＜b之类)]
在个体染色体的编码方法上着手，就能够达到这种搜索空间与解空间之间的对 应的要求。 • 用这种处理方法能够在遗传算法中设置最小的搜索空间，所以它能够提高遗传 算法的搜索效率。 • 但需要注意的是：除了在编码方法上想办法之外，也必须保证经过交叉、变异 等遗传其子作用之后所产生出的新个体在解空间中也要有确 定的对应解，而不会产生无效解。 [处理方法] 方法一：用编码方法来保证总是能够产生出在解空间中有对应可行解的染色体。 这个实现方法要求我们设计出一种比较好的个体编码方案。 如前面我们讲到的二进制编码方案即可实现上述要求。 方法二：用程序来保证直到产生出在解空间中有对应可行解的染色体之前，一 直进行交叉运算和变异运算。 虽然这个实现方法对编码方法的要求不高，但它有可能需要反复地进 行交叉运算和变异运算才能产生出一个满足约束条件的可行解，这样 就有可能会降低遗传算法的运行效率。

25 (2) 罚函数法 [基本思想] 对在解空间中无对应可行解的个体，计算其适应度时，处以一个罚函数，从 而降低该个体适应度，使该个体被遗传到下一代群体中的机会减少。即用下式 来对个体的适应度进行调整： F(X) X满足约束条件时 F(X) – P(X) X不满足约束条件时 F’(X)= 式中，F(X)为原适应度; F’(x)为考虑了罚函数之后的新适应度; P(x)为罚函数。 [惩罚函数] 设有优化问题的目标函数： max F(x1,x2,…,xn) S.t Hi(x1,x2,…,xn) i=1,2,…,m

26 加入罚函数后，原来的问题变为下述一个新的目标函数：
max 式中 ——惩罚函数； ——惩罚系数。 Ⅰ. 最简单的惩罚函数形式是平方法，即： Ⅱ.也有人建议采用松紧法。在遗传算法初期，惩罚轻一些；到了后期，则惩 罚重一些。具体的新目标函数F为：

27 其中： K——系数，可取 1/m； t——当前的迭代代次； T——终止迭代次数； ——系数，1左右； f——个体适应度的平均值； di——违背约束i的程度，视问题的不同而定义。 [难点] 如何确定合理的罚函数是这种处理方法的难点之所在，因为这时既要考虑如 何度量解对约束条件不满足的程度，又要考虑遗传算法在计算效率上的要求。 • 罚函数的强度太小的话，部分个体仍有可能破坏约束条件，所以保证不了遗 传运算所得到的个体一定是满足约束条件的一个可行解； • 罚函数的强度太大的话，又有可能使个体的适应度差异不大，降低了个体之 间的竞争力，从而影响遗传算法的运行效率。

28 (3) 可行解变换法 [基本思想] 在由个体基因型到个体表现型 的变换中，增加使其满足约束条 件的处理过程。 即寻找出一种个 体基因型和个体表现型之间的多 对一的变换关系，使进化过程中 所产生的个体总能够通过这个变 换而转化成解空间中满足约束条 件的一个可行解。 下图为该方法的示意图。 [优劣] 这种处理方法虽然对个体的编 码方法、交叉运算、变异运算 等没有附加的要求，但它却是以 扩大搜索空间为代价的，所以一 般会使得遗传算法的运行效率有 所下降。

29 4.3 选择算子 pis= Fi /  Fi 在生物的遗传和自然进化过程中，对生存环境适应程度较高的物种将有更多 的机会遗传到下一代；
4.3 选择算子 在生物的遗传和自然进化过程中，对生存环境适应程度较高的物种将有更多 的机会遗传到下一代； 遗传算法中的选择操作用来确定如何从父代群体中按某种方法选取哪些个体 遗传到下一代群体中的一种遗传运算。选择操作建立在对个体的适应度进行评 价的基础上。 最常用的选择算子是基本遗传算法中的比例选择算子。 但对于各种不同的问题，比例选择算子并不是最合适的一种选择算子，所以 人们提出了其他一些选择算于。下面介绍几种常用选择算子的操作方法。 比例选择 ( Fitness proportional selection ) [基本思想] 各个个体被选中的概率与其适应度大小成正比。 设群体大小为M，个体i的适应度为Fi，则个体i被选中的概率pis为： M pis= Fi /  Fi i=1 i=1,2,…M

30 4.3.2 分级选择 ( ranking selecton ) （或称排序选择）
[特点] 适应度越高的个体被选中的概率也越大，适应度越低的个体被选中的概 率也越小。 [缺点] 由于是随机操作的原因，这种选择方法的选择误差比较大，有时甚至连 适应度较高的个体也选择不上。 分级选择 ( ranking selecton ) （或称排序选择） (1) 产生原因 遗传算法中个体适应度数值上的差别有时会很大，尤其是在算法的早期这种差 别更是悬殊。因此，个别特优个体会多次被选中进行复制，经过几代后它们在群 体中数目愈来愈多，冲淡了群体的多样性。因此，人们提出分级的概念，用连续 渐变的分级代替数值悬殊的适应度。 (2) 方法 • 设群体中有m个个体，将它们按降序方法依次排序，规定个体优劣的等级依 次为：1，2，3，…，i，…，M。

31 • 采用线性分级， 使各个个体被选中的可能性有如下线性关系：
p(i) = q - ( i -1 )d 其中， q —— 最优个体被选中的概率； d —— 相邻个体被选中概率之差。 上述线性关系使p(i)构成等差级数，即： q， q - d， q – 2d，…， q - id，…，q – (M-1)d 由于概率定义要求 ，按级数求和，有： 即： ①

32 下面按两种情况讨论： Ⅰ. 所有个体按相同概率选取，即 d=0 ，得： q = 1/M Ⅱ. 令最坏（最后）个体的的选取概率为0，即 q – (M-1)d = 0，带入① 式，得： q = 2/M 于是，q可在这两种极端情况下选取，即： 1/M ≤q ≤ 2/M 有了q，由① 式，可得： (3) 优缺点 优点：消除个体适应度差别悬殊时的影响，代替适应度的缩放技术。 缺点：抹杀个体适应度的实际差别，未能充分运用遗传信息。

33 4.3.3 竞技选择法 (tournament selection)
(1) 方法简介 这种选择法通过相互竞争，优胜者成为下一代的个体。在每一代群体中，每次 都随机选择 k个个体构成一个小群体，然后从这 k个个体中确定性地取适应度最 大的个体复制，进入下一代群体。被复制后的个体仍返回父代群体中，参加下 一次 k个个体的随机选择。这种随机选择重复M次，产生M个下一代个体． (2) 具体操作步骤 Ⅰ. 从第t代群体中随机选择 k个个体； Ⅱ. 比较 k个个体的适应度，复制适应度最大者进入第 t+1 代，被复制的个体 仍保留在第 t 代； Ⅲ. 重复执行Ⅰ、 Ⅱ M次，直至产生同 t 代一样的个体数目。 (3) 特点 竞技选择法中，选择的力度取决于 k值的大小。k值愈大，每次选出的优胜者 具有很高的适应度。反之，k值愈小，优胜者的适应度或高或低，随机性很强。

34 4.3.4 最优保存策略（Elitist selection )
在遗传算法的运行过程中．通过对个体进行交叉、变异等遗传操作而不断地产 生出新的个体。虽然随着群体的进化过程会产生出越来越多的优良个体，但由 于选择、交叉、变异等遗传操作的随机性，它们也有可能破坏掉当前群体中适 应度最好的个体。我们希望适应度最好的个体要尽可能地保留到下一代群体中。 为达到这个目的，可以使用最优保存策略进化模型来进行优胜劣汰操作。 (1) 基本思想 当前群体中适应度最高的个体不参与交叉运算和变异运算，而是用它来替换 掉本代群体中经过交叉、变异等遗传操作后所产生的适应度最低的个体。

35 (2) 最优保存策略进化模型的具体操作过程 Ⅰ. 找出当前群体中适应度最高的个体和适应度最低的个体。 Ⅱ. 若当前群体中最佳个体的适应度比总的迄今为止的最好个体的适应度还要 高，则以当前群体中的最佳个体作为新的迄今为止的最好个体。 Ⅲ. 用迄今为止的最好个体替换掉当前群体中的最差个体。 (3) 特点：最优保存策略可视为选择操作的一部分。该策略的实施可保证迄今为止 所得到的最优个体不会被交叉、变异等遗传运算所破坏，它是遗传算 法收敛性的一个重要保证条件。 缺点：它容易使得某个局部最优个体不易被淘汰掉反而快速扩散，从而使得 算法的全局搜索能力不强。 (4) 使用方法： 该方法一般要与其他一些选择操作方法配合起来使用，方可有良好的效果。 另外，最优保存策略还可加以推广，即在每一代的进化过程中保留多个最优个 体不参加交叉、变异等遗传运算，而直接将它们复制到下一代群体中。这种选 择方法也称为稳态复制。

36   Ni  4.3.5 确定式采样选择 ( Deterministic Sampling selection)
(1) 基本思想：按照一种确定的方式来进行选择操作 (2) 具体操作过程： Ⅰ. 计算群体中各个个体在下一代群体中的期望生存数目Ni： Ⅱ. 用Ni 的整数部分 Ni  确定各个对应个体在下一代群体中的生存数目 (  x  表示下取值，取不大于x的最大整数。) Ⅲ. 按照Ni 的小数部分对个体进行降序排序，顺序取前 M  个个体 加入到下一代群体中。 至此可完全确定出下一代群体中的M个个体。 (3) 特点：这种选择操作方法可保证适应度较大的一些个体一定能够被保留在下 一代群体中，并且操作也比较简单。 i=1,2,…M M   Ni  i=1

37 4.4 交叉算子 在生物的自然进化过程中，两个同源染色体通过交配而重组，形成新的染色体，
4.4 交叉算子 在生物的自然进化过程中，两个同源染色体通过交配而重组，形成新的染色体， 从而产生出新的个体或物种。交配重组是生物遗传和进化过程中的一个主要环 节。模仿这个环节，在遗传算法中也使用交叉算子来产生新的个体。 遗传算法中的所谓交叉运算，是指对两个相互配对的染色体按某种方式相互交 换其部分基因，从而形成两个新的个体。 交叉算子的设计和实现与所研究的问题密切相关，一般要求它既不要太多地破 坏个体编码串中表示优良性状的优良模式，又要能够有效地产生出一些较好的 新个体模式。另外，交叉算子的设计要和个体编码设计统一考虑。 交叉算子的设计包括以下两方面的内容: (1) 如何确定交叉点的位置? (2) 如何进行部分基因交换?

38 4.4.2 双点交叉与多点交叉 4.4.1 单点交叉 ( One-point Crossover )
(1) 单点交叉：又称为简单交叉，它是指在个体编码串中只随机设置一个交叉点， 然后在该点相互交换两个配对个体的部分染色体。 (2) 特点：若邻接基因座之间的关系能提供较好的个体性状和较高的个体适应度 的话，则这种单点交叉操作破坏这种个体性状和降低个体适应度的可 能性最小。 双点交叉与多点交叉 (1) 双点交叉 ( Two-point Crossover )： 指在个体编码串中随机设置了二个交叉点，然后再进行部分基因交换。 (2) 双点交叉的具体操作过程 Ⅰ. 在相互配对的两个个体编码串中随机设置两个交叉点。 Ⅱ. 交换两个个体在所设定的两个交叉点之间的部分染色体。 例如：

39 (3) 多点交叉 ( Multi-point Crossover )：
指在个体编码串中随机设置多个交叉点，然后进行基因交换。多点交叉又称为 广义交叉。 (4) 操作过程：与单点交叉和双点交叉相类似。 例如，三个交叉点时的交叉操作示例： (5) 说明： 一般不大使用多点交叉算子，因为它有可能破坏一些好的模式。事实上， 随着交叉点数的增多，个体的结构被破坏的可能性也逐渐增大。

40 4.4.3 均匀交叉 ( Uniform Crossover )
(1) 均匀交叉：指两个配对个体的每一个基因座上的基因都以相同的交叉概率进 行交换，从而形成两个新的个体。均匀交叉实际上可归属于多点 交叉的范围。 (2) 操作过程： Ⅰ. 随机产生一个与个体编码串长度等长的屏蔽字 W = w1 w2 … wi … wl , 其中l为个体编码串长度。 Ⅱ. 由下述规则从A、B两个父代个体中产生出两个新的子代个体 A’ 、B’ : • 若 wi = 0，则A’ 在第i个基因座上的基因值继承A的对应基因值，B’ 在第i个 基因座上的基因值继承B的对应基因值； • 若 wi＝l，则A’ 在第i个基因座上的基因值继承B的对应基因值，B’ 在第i个 基因座上的基因值继承A的对应基因值。 例如，均匀交叉操作的示例如下:

41 4.4.4 算术交叉 ( Arithmetic Crossover )
(1) 算术交叉：由两个个体的线性组合而产生出两个新的个体。 (2) 进行算术交叉的条件：为了能够进行线性组合运算，算术交叉的操作对象一 般是由浮点数编码所表示的个体。 (3) 算术交叉产生的新个体： 式中： x 为个体； 为一参数，它可以是一个常数，此时所进行的交叉运算称为均匀 算术交叉； 它也可以是一个由进化代数所决定的变量，此时所进 行的交叉运算称为非均匀算术交叉。 (4) 算术交叉的主要操作过程 Ⅰ. 确定两个个体进行线性组合时的系数。 Ⅱ. 依据上式生成两个新的个体。

42 4.5 变异算子 4.5.1 基本位变异(Simple Mutation) (1) 从遗传运算过程中产生新个体的能力方面来说:
4.5 变异算子 (1) 从遗传运算过程中产生新个体的能力方面来说: • 交叉运算是产生新个体的主要方法，它决定了遗传算法的全局搜索能力； • 而变异运算只是产生新个体的辅助方法，但它也是必不可少的一个运算步骤， 因为它决定了遗传算法的局部搜索能力。 • 交叉算子与变异算子的相互配合，共同完成对搜索空间的全局搜索和局部搜 索，从而使得遗传算法能够以良好的搜索性能完成最优化问题的寻优过程。 (2) 在遗传算法中使用变异算子主要有以下两个目的： (1) 改善遗传算法的局部搜索能力； (2) 维持群体的多样性，防止出现早熟现象。 (3) 变异算子的设计包括如下两方面的内容： • 如何确定变异点的位置? • 如何进行基因值替换? 下面介绍其中较常用的几种变异操作方法，它们适合于二进制编码的个体和 浮点数编码的个体。 4.5.1 基本位变异(Simple Mutation)

43 4.5.2 均匀变异(Uniform Mutation)
(1) 均匀变异操作 指分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体 编码串中各个基因座上的原有基因值。 (2) 均匀变异的具体操作过程 Ⅰ. 依次指定个体编码串中的每个基因座为变异点。 Ⅱ. 对每一个变异点，以变异概率pm从对应基因的取值范围内取一随机数来替代 原有基因值。 (3) 举例 假设有一个体为X=x1x2…xk…xn , 若xk为变异点，其取值范围为[Ukmin,Ukmax], 在该点对个体X进行均匀变异操作后，可得到一个新的个体X=x1x2…xk’…xn, 其中变异点的新基因值是： xk’ = Ukmin + r · (Ukmax – Ukmin ) 式中，r 为[0, 1] 范围内符合均匀概率分布的一个随机数。 (4) 适用范围 均匀变异操作持别适合应用于遗传算法的初期运行阶段，它使得搜索点可以在整 个搜索空间内自由地移动，从而可以增加群体的多样性，使算法处理更多的模式。

44 4.5.3 边界变异(Boundary mutation) (1) 边界变异
均匀变异操作的一个变形算法。在进行边界变异操作时，随机地取基因座的 二个对应边界基因值之一去替代原有基因值。 (2) 举例 假设有一个体为X=x1x2…xk…xn , 若xk为变异点，其取值范围为[Ukmin,Ukmax], 在该点对个体X进行边界变异操作后，可得到一个新的个体X=x1x2…xk’…xn, 其中变异点的新基因值是： Ukmin, if random(0,1)=0 Ukmax, if random(0,1)=1 xk’= 式中， random(0,1)表示以均等的概率从 0, 1中任取其一。 (3) 适用范围 当变量的取值范围特别宽，并且无其他约束条件时，边界变异会带来不好 的作用。但它特别适用于最优点位于或接近于可行解的边界时的一类问题。

45 4.5.4 非均匀变异（Non_Uniform Mutation)
(1) 均匀变异的不足 均匀变异操作取某一范围内均匀分布的随机数来替换原有基因值，可使得个体在搜索空间内自由移动。但另一方面，它却不便于对某一重点区域进行局部搜索。 (2) 非均匀变异 不取均匀分布的随机数去替换原有的基因值，而是对原有基因值作一随机扰动， 以扰动后的结果作为变异后的新基因值。对每个基因座都以相同的概率进行变异 运算之后，相当于整个解向量在解空间中作了一个轻微的变动。 (3) 操作 非均匀变异的具体操作过程与均匀变异相类似，但它重点搜索原个体附近的微小区域。 (4) 适用范围 非均匀变异可使得遗传算法在其初始运行阶段(t较小时)进行均匀随机搜索，而 在其后期运行阶段(t较接近于T时)进行局部搜索，所以它产生的新基因值比均匀变异所产生的基因值更接近于原有基因值。故随着遗传算法的运行，非均匀变异就使得最优解的搜索过程更加集中在某一最有希望的重点区域中。

46 4.5.5 高斯变异(Gaussian mutation)
(1) 高斯变异 是改进遗传算法对重点搜索区域的局部搜索性能的另一种变异操作方法。 所谓高斯变异操作是指进行变异操作时，用符合均值为、方差为 2 的正态分布 的一个随机数来替换原有基因值。 (2) 操作 • 高斯变异的具体操作过程与均匀变异类似。 • 具体实现高斯变异时，符合正态分布的随机数Q可由一些符合均匀分布的随机 数利用公式来近似产生。 例： • 假定有12个在[ 0, 1]范围内均匀分布的随机数 ri(i=1,2,…,12)，则符合N(,2) 正态分布的一个随机数Q可由下式求得：

47 • 有一个体为X=x1x2…xk…xn , 若xk为变异点，其取值范围为[Ukmin,Ukmax],

48 4.6 终止 遗传算法是一个反复迭代的过程，每次选代期间，要执行适应度计算、复制、交 叉、变异等操作，直至满足终止条件。
4.6 终止 遗传算法是一个反复迭代的过程，每次选代期间，要执行适应度计算、复制、交 叉、变异等操作，直至满足终止条件。 使遗传算法终止的方法有三种： (1) 规定最大选代次数T。一旦遗传算法的迭代次数达到T，则停止操作，输出结 果。通常T取200一500次。 由于遗传算法中有许多随机因素影响，最后一代的结果不一定含有最优个体。 为此，要经常记录每代的最优个体以便查询比较。 (2) 规定最小的偏差。对于适应度目标已知的遗传算法，如用方差作为适应度计 算的曲线拟合问题，可用最小的偏差制定终止条件，即： | fmax – f*| ≤  式中 f*——已知的适应度目标； fmax——每代最大的适应废。 (3)观察适应度的变化趋势。在遗传算法的初期，最优个体的适应度以及群体的 平均适应度都较小，以后随着复制、交叉 、变异等操作，适应度值增加。到 了遗传算法后期，这种增加已趋缓和或停止．一旦这种增加停止，即中止遗 传算法。

49 4.7 遗传算法的高级实现技术 4.7.2 二倍体与显性操作算子 4.7.3 变长度染色体遗传算法 4.7.4 小生境遗传算法
倒位算子 二倍体与显性操作算子 变长度染色体遗传算法 小生境遗传算法 混合遗传算法