遗传算法的实现技术.ppt

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

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

有最小编码字符集的编码方案 由于遗传算法应用的广泛性，迄今为止人们已经提出了许多种不同的编码方法由于遗传算法应用的广泛性，迄今为止人们已经提出了许多种不同的编码方法 总的来说，这些编码方法可以分为三大类：总的来说，这些编码方法可以分为三大类： 二进制编码方法二进制编码方法 浮点数编码方法浮点数编码方法 符号编码方法符号编码方法 9.1.1 9.1.1 二进制编码方法二进制编码方法二进制编码方法二进制编码方法 二进制编码方法是遗传算法中最常用的一种编码方法，它使用的编码符号集二进制编码方法是遗传算法中最常用的一种编码方法，它使用的编码符号集 是由二进制符号是由二进制符号0和和1所组成的二值符号集所组成的二值符号集{0，，1}，它所构成的个体基因型是一个，它所构成的个体基因型是一个 二进制编码符号串二进制编码符号串 (1) (1) 编码编码编码编码 假设某一参数的取值范围是假设某一参数的取值范围是[umax, umin]，我们用长度为，我们用长度为l的二进制编码符号串的二进制编码符号串 来表示该参数，则它总共能够产生来表示该参数，则它总共能够产生 2l种不同的编码，参数编码时的对应关系如种不同的编码，参数编码时的对应关系如 下：下： 00000000…00000000＝＝0 umin 00000000…00000001＝＝1 umin +   …… 11111111…11111111=2l–1 umax 二进制编码的编码精度为：二进制编码的编码精度为：  = Umax   umin2l   1 (2) (2) 解码解码解码解码 假设某一个体的编码是：假设某一个体的编码是： x：： bl bl-1 bl-2……b2b1 则对应的解码公式为：则对应的解码公式为： 例如，对于例如，对于 x [ 0, 1023] ，若用，若用 10 位长的二进制编码表示该参数的话，位长的二进制编码表示该参数的话， 则下述符号串：则下述符号串： x：：0010101111 就可表示一个个体，就可表示一个个体， 它所对应的参数值是它所对应的参数值是 x＝＝175。

编码精度为编码精度为   = 1 x = umin + (   bi · 2i-1) · 1i=lUmax   umin2l   1  (3) (3) 二进制编码方法的优点：二进制编码方法的优点：二进制编码方法的优点：二进制编码方法的优点： Ⅰ. 编码、解码操作简单易行；编码、解码操作简单易行； Ⅱ. 交叉、变异等遗传操作便于实现；交叉、变异等遗传操作便于实现； Ⅲ. 符合最小字符集编码原则（使用能使问题得到自然表示或描述的具有最小符合最小字符集编码原则（使用能使问题得到自然表示或描述的具有最小 编码字符集的编码方案编码字符集的编码方案 Ⅳ. 便于利用模式定理对算法进行理论分析便于利用模式定理对算法进行理论分析9.1.2 9.1.2 格雷码编码方法格雷码编码方法格雷码编码方法格雷码编码方法 格雷码编码方法是二进制编码方法的一种变形格雷码编码方法是二进制编码方法的一种变形。

(1) (1) 格雷码编码：格雷码编码：格雷码编码：格雷码编码： 其连续的两个整数所对应的编码值之间仅仅只有一个码位是不相同的，其连续的两个整数所对应的编码值之间仅仅只有一个码位是不相同的， 其余码位都完全相同如图所示其余码位都完全相同如图所示 (2) (2) 优点：优点：优点：优点： • 便于提高遗传算法的局部搜索能力；便于提高遗传算法的局部搜索能力； • 交叉、变异等遗传操作便于实现；交叉、变异等遗传操作便于实现； • 符合最小字符集编码原则；符合最小字符集编码原则； • 便于利用模式定理对算法进行理论分析便于利用模式定理对算法进行理论分析49.1.3 9.1.3 浮点数编码方法浮点数编码方法浮点数编码方法浮点数编码方法 (1) (1) 二进制编码的缺点二进制编码的缺点二进制编码的缺点二进制编码的缺点 • 二进制编码存在着连续函数离散化时的映射误差二进制编码存在着连续函数离散化时的映射误差 个体编码串的长度较短时，可能达不到精度要求；个体编码串的长度较短时，可能达不到精度要求； 个体编码串的长度较长时，虽然能提高编码精度，但却会使遗传算法的搜索个体编码串的长度较长时，虽然能提高编码精度，但却会使遗传算法的搜索 空间急剧扩大。

空间急剧扩大 • 二二进进制制编码编码不便于反映所求不便于反映所求问题问题的特定知的特定知识识，，这样这样也就不便于开也就不便于开发针对问题专发针对问题专 门门知知识识的的遗传遗传运算算子，人运算算子，人们们在一些在一些经经典典优优化算法的研究中所化算法的研究中所总结总结出的一些出的一些 宝宝贵经验贵经验也就无法在也就无法在这这里加以利用，也不便于里加以利用，也不便于处处理非平凡理非平凡约约束条件 (2) (2) 浮点数编码方法浮点数编码方法浮点数编码方法浮点数编码方法 个体的每个基因值用某一范围内的一个浮点数来表示；个体的每个基因值用某一范围内的一个浮点数来表示； 个体的编码长度等于其决策变量的个数个体的编码长度等于其决策变量的个数 因为这种编码方法使用的是决策变量的真实值，所以浮点数编码方法也叫做因为这种编码方法使用的是决策变量的真实值，所以浮点数编码方法也叫做 真值编码方法真值编码方法 例如，如果一个优化问题含有例如，如果一个优化问题含有5个变量个变量xi(i＝＝1,2,…,5)，每个变量都有其对应的上，每个变量都有其对应的上 下限下限[Uimin , Uimax]，则：，则： 5.80 6.90 3.50 3.80 5.00 x: 表示一个体的基因型，表示一个体的基因型， 其对应的表现型是：其对应的表现型是：x：：[ 5.80，，6.90，，3.50，，3.80，，5.00]T。

3) (3) 注意事项：注意事项：注意事项：注意事项： • 在浮点数编码方法中在浮点数编码方法中: 必须保证基因值在给定的区间限制范围内；遗传算法中所使用的交叉、变异必须保证基因值在给定的区间限制范围内；遗传算法中所使用的交叉、变异 等遗传算子也必须保证其运算结果所产生的新个体的基因值也在这个区间限等遗传算子也必须保证其运算结果所产生的新个体的基因值也在这个区间限 制范围内制范围内 • 当用多个字节来表示一个基因值时，交叉运算必须在两个基因的分界字节处进当用多个字节来表示一个基因值时，交叉运算必须在两个基因的分界字节处进 行，而不能在某个基因的中间字节分隔处进行行，而不能在某个基因的中间字节分隔处进行 (4) (4) 浮点数编码方法的优点：浮点数编码方法的优点：浮点数编码方法的优点：浮点数编码方法的优点： • 适合于在遗传算法中表示范围较大的数；适合于在遗传算法中表示范围较大的数； • 适合于精度要求较高的遗传算法；适合于精度要求较高的遗传算法； • 便于较大空间的遗传搜索；便于较大空间的遗传搜索； • 改善了遗传算法的计算复杂性，提高了运算效率；改善了遗传算法的计算复杂性，提高了运算效率； • 便于遗传算法与经典优化方法的混合使用；便于遗传算法与经典优化方法的混合使用； • 便于设计针对问题的专门知识的知识型遗传算子；便于设计针对问题的专门知识的知识型遗传算子； • 便于处理复杂的决策变量约束条件。

便于处理复杂的决策变量约束条件9.1.4 9.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个城市，并且每个城市个城市，并且每个城市 只能访问一次，最后又必须返回出发城市如何安排他对这些城市的访问次序，可只能访问一次，最后又必须返回出发城市如何安排他对这些城市的访问次序，可 使其旅行路线的总长度最短使其旅行路线的总长度最短? ] (2) (2) 符号编码的主要优点：符号编码的主要优点：符号编码的主要优点：符号编码的主要优点： • 符合有意义积木块编码原则符合有意义积木块编码原则 • 便于在遗传算法中利用所求解问题的专门知识便于在遗传算法中利用所求解问题的专门知识 • 便于遗传算法与相关近似算法之间的混合使用便于遗传算法与相关近似算法之间的混合使用 但对于使用符号编码方法的遗传算法，一般需要认真设计交叉、变异等遗传运但对于使用符号编码方法的遗传算法，一般需要认真设计交叉、变异等遗传运 算的操作方法，以满足问题的各种约束要求，这样才能提高算法的搜索性能算的操作方法，以满足问题的各种约束要求，这样才能提高算法的搜索性能。

9.1.5 9.1.5 多参数级联编码方法多参数级联编码方法多参数级联编码方法多参数级联编码方法9.1.5 9.1.5 多参数交叉编码方法多参数交叉编码方法多参数交叉编码方法多参数交叉编码方法9.2 9.2 适应度函数适应度函数适应度函数适应度函数 • 在研究自然界生物的遗传和进化现象时，生物学家使用适应度这个术语来度量在研究自然界生物的遗传和进化现象时，生物学家使用适应度这个术语来度量 某个物种对于其生存环境的适应程度某个物种对于其生存环境的适应程度 • 与此相类似，遗传算法中也使用适应度这个概念来度量群体中各个个体在优化与此相类似，遗传算法中也使用适应度这个概念来度量群体中各个个体在优化 计算中有可能达到或接近于或有助于找到最优解的优良程度计算中有可能达到或接近于或有助于找到最优解的优良程度 度量个体适应度的函数称为适应度函数度量个体适应度的函数称为适应度函数 9.2.1 9.2.1 目标函数与适应度函数目标函数与适应度函数目标函数与适应度函数目标函数与适应度函数 遗传算法的一个特点是它仅使用所求问题的目标函数值就可以得到下一步的遗传算法的一个特点是它仅使用所求问题的目标函数值就可以得到下一步的 有关搜索信息。

有关搜索信息 最优化问题可分为两大类，一类为求目标函数的全局最大值，另一类为求目标函最优化问题可分为两大类，一类为求目标函数的全局最大值，另一类为求目标函 数的全局最小值对于这两类优化问题，第二章中已经介绍过由解空间中某一点的数的全局最小值对于这两类优化问题，第二章中已经介绍过由解空间中某一点的 目标函数值目标函数值 f(x) 到搜索空间中对应个体的适应度函数值到搜索空间中对应个体的适应度函数值F(x)的转换方法：的转换方法： • 对于求最大值的问题，作下述转换：对于求最大值的问题，作下述转换： F(X) =f(X)+Cmin if f(X)+Cmin> 00 if f(X)+Cmin ≤ 0• 对于求最小值问题，变换如下：对于求最小值问题，变换如下：F(X) =Cmax - f(X) if f(X)   Cmax0 if f(X)   Cmax 9.2.2 9.2.2 适应度尺度变换适应度尺度变换适应度尺度变换适应度尺度变换 (1) (1) 适应度尺度变换的原因适应度尺度变换的原因适应度尺度变换的原因适应度尺度变换的原因 在遗传算法中，各个个体被遗传到下一代群体中的概率是由该个体的适应度来在遗传算法中，各个个体被遗传到下一代群体中的概率是由该个体的适应度来 确定的，应用实践表明，仅使用以上两式来计算个体适应度时，有些遗传算法确定的，应用实践表明，仅使用以上两式来计算个体适应度时，有些遗传算法 会收敛得很快，也有些遗传算法会收敛得很慢。

会收敛得很快，也有些遗传算法会收敛得很慢 • • 在遗传算法运行的初期阶段在遗传算法运行的初期阶段在遗传算法运行的初期阶段在遗传算法运行的初期阶段 群体中可能会有少数几个个体的适应度相对其他个体来说非常高若按照常群体中可能会有少数几个个体的适应度相对其他个体来说非常高若按照常 用的比例选择算子来确定个体的遗传数量时，则这几个相对较好的个体将在下用的比例选择算子来确定个体的遗传数量时，则这几个相对较好的个体将在下 一代群体中占有很高的比例，在极端情况下或当群体现模较小时，新的群体甚一代群体中占有很高的比例，在极端情况下或当群体现模较小时，新的群体甚 至完全由这样的少数几个个体所组成这时产生新个体作用较大的交叉算子就至完全由这样的少数几个个体所组成这时产生新个体作用较大的交叉算子就 起不了什么作用，因为相同的两个个体不论在何处进行交叉操作都永远不会产起不了什么作用，因为相同的两个个体不论在何处进行交叉操作都永远不会产 生出新的个体，如下所示：生出新的个体，如下所示： A: 10101010 1010 10101010 1010 B: 10101010 1010 10101010 1010单点交叉单点交叉 这样就会使群体的多样性降低，容易导致遗传算法发生早熟现象（或称早期收这样就会使群体的多样性降低，容易导致遗传算法发生早熟现象（或称早期收 敛敛)，使遗传算法所求到的解停留在某一局部最优点上。

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

这将导致无法对某些重点区域进行重点搜索， 从而影响遗传算法的运行效率从而影响遗传算法的运行效率 因此，我们希望在遗传算法运行的后期阶段，算法能够对个体的适应度进行因此，我们希望在遗传算法运行的后期阶段，算法能够对个体的适应度进行 适当的放大，扩大最佳个体适应度与其他个体适应度之间的差异程度，以提高适当的放大，扩大最佳个体适应度与其他个体适应度之间的差异程度，以提高 个体之间的竞争性个体之间的竞争性(2) (2) 适应度尺度变换定义适应度尺度变换定义适应度尺度变换定义适应度尺度变换定义 在遗传算法运行的不同阶段，有时需要对个体的适应度进行适当的扩大或缩小在遗传算法运行的不同阶段，有时需要对个体的适应度进行适当的扩大或缩小 这种对个体适应度所做的扩大或缩小变换就称为适应度尺度变换这种对个体适应度所做的扩大或缩小变换就称为适应度尺度变换3) (3) 适应度尺度变换方法适应度尺度变换方法适应度尺度变换方法适应度尺度变换方法 目前常用的个体适应度尺度变换方法主要有三种：线性尺度变换、乘幂尺度变目前常用的个体适应度尺度变换方法主要有三种：线性尺度变换、乘幂尺度变 换和指数尺度变换。

换和指数尺度变换 Ⅰ. Ⅰ. 线性尺度变换线性尺度变换线性尺度变换线性尺度变换 线性尺度变换的公式如下线性尺度变换的公式如下: F’ = aF + b 式中式中 F——原适应度；原适应度； F’——变换后的新适应度；变换后的新适应度； a,b——系数 系数系数a,b直接影响到这个尺度变换的大小，所以对其选取有一定的要求，一般直接影响到这个尺度变换的大小，所以对其选取有一定的要求，一般 希望它们满足下面两个条件希望它们满足下面两个条件: 条件条件1：：尺度变换后全部个体的新适应度的平均值尺度变换后全部个体的新适应度的平均值 F’avg 要等于其原适应度平均值要等于其原适应度平均值Favg 即：即： F’avg = Favg 这条要求是为了保证群体中适应度接近于平均适应度的个体能够有期待的数这条要求是为了保证群体中适应度接近于平均适应度的个体能够有期待的数 量被遗传到下一代群体中。

量被遗传到下一代群体中 条件条件2：：尺度变换后群体中新的最大适应度尺度变换后群体中新的最大适应度 F’max 要等于其原平均适应度要等于其原平均适应度 Favg 的指定的指定 倍数即：倍数即： F’max = CFavg 式中，式中，C为最佳个体的期望复制数量，对于群体规模大小为为最佳个体的期望复制数量，对于群体规模大小为50 ~ 100个个体的个个体的 情况，一般取情况，一般取 C = 1.2 ~ 2 这条要求是为了保证群体中最好的个体能够期望复制这条要求是为了保证群体中最好的个体能够期望复制C倍到新一代群体中倍到新一代群体中 如下图所示如下图所示 最小适应度为负时的处理：最小适应度为负时的处理： 在遗传算法执行的后期，个别劣质个体的适应度远远小于群体平均适应度及最在遗传算法执行的后期，个别劣质个体的适应度远远小于群体平均适应度及最 大适应度，并且后两者比较接近这时按上述方法缩放适应度会使低适应度变成大适应度，并且后两者比较接近。

这时按上述方法缩放适应度会使低适应度变成 负值，如图所示这将会给后面的处理过程带来不便，必须避免这种情况的发生，负值，如图所示这将会给后面的处理过程带来不便，必须避免这种情况的发生， 解决这个问题的方法是：把原最小适应度解决这个问题的方法是：把原最小适应度Fmin映射为映射为Fmin= 0，并且保持原平均适，并且保持原平均适 应度应度 Favg与新的平均适应度与新的平均适应度 F’avg 相等 综上所述，参数综上所述，参数a, b的计算方法如下：的计算方法如下： (1) 计算适应度非负判别式：计算适应度非负判别式： Fmin >C · Favg - FmaxC -1 若不等式满足，则执行若不等式满足，则执行(2)，， 否则执行否则执行(3) (2) 正常情况下的缩放：正常情况下的缩放： C - 1 a =Fmax - FavgFavgFmax - C · Favg b =Fmax - FavgFavg(3) 负适应度时的缩放：负适应度时的缩放： a =FavgFavg - Fmin b =Favg · FminFavg - Fmin Ⅱ. Ⅱ. 乘幂尺度变换乘幂尺度变换乘幂尺度变换乘幂尺度变换 乘幂尺度变换的公式为：乘幂尺度变换的公式为： F’ = Fk 即新的适应度是原有适应度的某个指定乘幂。

幂指数即新的适应度是原有适应度的某个指定乘幂幂指数k与所求解的问题有关，与所求解的问题有关， 并且在算法的执行过程中需要不断对其进行修正才能使尺度变换满足一定的伸并且在算法的执行过程中需要不断对其进行修正才能使尺度变换满足一定的伸 缩要求 Ⅲ. Ⅲ. 指数尺度变换指数尺度变换指数尺度变换指数尺度变换 指数尺度变换的公式为：指数尺度变换的公式为： F’＝＝exp(- F) 即新的适应度是原有适应度的某个指数式中系数即新的适应度是原有适应度的某个指数式中系数 决定了选择的强制性，决定了选择的强制性，  越小，原有适应度较高的个体的新适应度就越与其他个体的新适应度相差较越小，原有适应度较高的个体的新适应度就越与其他个体的新适应度相差较 大，亦即越增加了选择该个体的强制性大，亦即越增加了选择该个体的强制性9.2.3 9.2.3 约束条件的处理方法约束条件的处理方法约束条件的处理方法约束条件的处理方法 实际应用中的优化问题一般都含有一定的约束条件，它们的描述形式各种各样。

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

此时的搜索空间与解空间的对解空间中表示一个可行解的点有一一对应的关系此时的搜索空间与解空间的对应关系如图所示应关系如图所示 [对一些比较简单的约束条件对一些比较简单的约束条件(如如a

定的对应解，而不会产生无效解 [处理方法处理方法] 方法一：用编码方法来保证总是能够产生出在解空间中有对应可行解的染色体方法一：用编码方法来保证总是能够产生出在解空间中有对应可行解的染色体 这个实现方法要求我们设计出一种比较好的个体编码方案这个实现方法要求我们设计出一种比较好的个体编码方案 如前面我们讲到的二进制编码方案即可实现上述要求如前面我们讲到的二进制编码方案即可实现上述要求 方法二：用程序来保证直到产生出在解空间中有对应可行解的染色体之前，一方法二：用程序来保证直到产生出在解空间中有对应可行解的染色体之前，一 直进行交叉运算和变异运算直进行交叉运算和变异运算 虽然这个实现方法对编码方法的要求不高，但它有可能需要反复地进虽然这个实现方法对编码方法的要求不高，但它有可能需要反复地进 行交叉运算和变异运算才能产生出一个满足约束条件的可行解，这样行交叉运算和变异运算才能产生出一个满足约束条件的可行解，这样 就有可能会降低遗传算法的运行效率。

就有可能会降低遗传算法的运行效率 (2) (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 max 式中式中  ——惩罚函数；惩罚函数；  ——惩罚系数。

惩罚系数 Ⅰ. Ⅰ. 最简单的惩罚函数形式是平方法最简单的惩罚函数形式是平方法最简单的惩罚函数形式是平方法最简单的惩罚函数形式是平方法，即：，即：Ⅱ.Ⅱ.也有人建议采用松紧法也有人建议采用松紧法也有人建议采用松紧法也有人建议采用松紧法在遗传算法初期，惩罚轻一些；到了后期，则惩在遗传算法初期，惩罚轻一些；到了后期，则惩 罚重一些具体的新目标函数罚重一些具体的新目标函数F为：为： 加入罚函数后，原来的问题变为下述一个新的目标函数：加入罚函数后，原来的问题变为下述一个新的目标函数： 其中：其中： K——系数，可取系数，可取 1/m；； t——当前的迭代代次；当前的迭代代次； T——终止迭代次数；终止迭代次数；  ——系数，系数，1左右；左右； f——个体适应度的平均值；个体适应度的平均值； di——违背约束违背约束i的程度，视问题的不同而定义。

的程度，视问题的不同而定义[难点难点] 如何确定合理的罚函数是这种处理方法的难点之所在，因为这时既要考虑如如何确定合理的罚函数是这种处理方法的难点之所在，因为这时既要考虑如 何度量解对约束条件不满足的程度，又要考虑遗传算法在计算效率上的要求何度量解对约束条件不满足的程度，又要考虑遗传算法在计算效率上的要求 • 罚函数的强度太小的话，部分个体仍有可能破坏约束条件，所以保证不了遗罚函数的强度太小的话，部分个体仍有可能破坏约束条件，所以保证不了遗 传运算所得到的个体一定是满足约束条件的一个可行解；传运算所得到的个体一定是满足约束条件的一个可行解； • 罚函数的强度太大的话，又有可能使个体的适应度差异不大，降低了个体之罚函数的强度太大的话，又有可能使个体的适应度差异不大，降低了个体之 间的竞争力，从而影响遗传算法的运行效率间的竞争力，从而影响遗传算法的运行效率(3) (3) 可行解变换法可行解变换法可行解变换法可行解变换法 [基本思想基本思想] 在由个体基因型到个体表现型在由个体基因型到个体表现型 的变换中，增加使其满足约束条的变换中，增加使其满足约束条 件的处理过程。

件的处理过程 即寻找出一种个即寻找出一种个 体基因型和个体表现型之间的多体基因型和个体表现型之间的多 对一的变换关系，使进化过程中对一的变换关系，使进化过程中 所产生的个体总能够通过这个变所产生的个体总能够通过这个变 换而转化成解空间中满足约束条换而转化成解空间中满足约束条 件的一个可行解件的一个可行解 下图为该方法的示意图下图为该方法的示意图 [优劣优劣] 这种处理方法虽然对个体的编这种处理方法虽然对个体的编 码方法、交叉运算、变异运算码方法、交叉运算、变异运算 等没有附加的要求，但它却是以等没有附加的要求，但它却是以 扩大搜索空间为代价的，所以一扩大搜索空间为代价的，所以一 般会使得遗传算法的运行效率有般会使得遗传算法的运行效率有 所下降9.3 9.3 选择算子选择算子选择算子选择算子 在生物的遗传和自然进化过程中，对生存环境适应程度较高的物种将有更多在生物的遗传和自然进化过程中，对生存环境适应程度较高的物种将有更多 的机会遗传到下一代；的机会遗传到下一代； 遗传算法中的选择操作用来确定如何从父代群体中按某种方法选取哪些个体遗传算法中的选择操作用来确定如何从父代群体中按某种方法选取哪些个体 遗传到下一代群体中的一种遗传运算。

选择操作建立在对个体的适应度进行评遗传到下一代群体中的一种遗传运算选择操作建立在对个体的适应度进行评 价的基础上价的基础上 最常用的选择算子是基本遗传算法中的比例选择算子最常用的选择算子是基本遗传算法中的比例选择算子 但对于各种不同的问题，比例选择算子并不是最合适的一种选择算子，所以但对于各种不同的问题，比例选择算子并不是最合适的一种选择算子，所以 人们提出了其他一些选择算于下面介绍几种常用选择算子的操作方法人们提出了其他一些选择算于下面介绍几种常用选择算子的操作方法 9.3.1 9.3.1 比例选择比例选择比例选择比例选择 ( Fitness proportional selection )( Fitness proportional selection ) [ [基本思想基本思想基本思想基本思想] ] 各个个体被选中的概率与其适应度大小成正比各个个体被选中的概率与其适应度大小成正比 设群体大小为设群体大小为M，个体，个体i的适应度为的适应度为Fi，则个体，则个体i被选中的概率被选中的概率pis为：为： M pis= Fi /   Fi i=1 i=1,2,…M [ [特点特点特点特点] ] 适应度越高的个体被选中的概率也越大，适应度越低的个体被选中的概适应度越高的个体被选中的概率也越大，适应度越低的个体被选中的概 率也越小。

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

渐变的分级代替数值悬殊的适应度 (2) (2) 方法方法方法方法 • 设群体中有设群体中有m个个体，将它们按降序方法依次排序，规定个体优劣的等级依个个体，将它们按降序方法依次排序，规定个体优劣的等级依 次为：次为：1，，2，，3，，…，，i，，…，，M • 采用线性分级，采用线性分级， 使各个个体被选中的可能性使各个个体被选中的可能性有如下有如下线线性关系：性关系： p(i) = q - ( i -1 )d 其中，其中， q —— 最最优优个体被个体被选选中的概率；中的概率； d —— 相相邻邻个体被个体被选选中概率之差中概率之差 上述上述线线性关系使性关系使p(i)构成等差构成等差级级数，即：数，即： q，， q - d，， q – 2d，，…，， q - id，，…，，q – (M-1)d 由于概率定由于概率定义义要求要求 ，按级数求和，有：，按级数求和，有：即：即：①①①①下面按两种情况讨论：下面按两种情况讨论： Ⅰ. 所有个体按相同概率选取，即所有个体按相同概率选取，即 d=0 ，得：，得： q = 1/M Ⅱ. 令最坏（最后）个体的的选取概率为令最坏（最后）个体的的选取概率为0，即，即 q – (M-1)d = 0，带入，带入①①①① 式，得：式，得： q = 2/M 于是，于是，q可在这两种极端情况下选取，即：可在这两种极端情况下选取，即： 1/M ≤q ≤ 2/M 有了有了q，由，由①①①① 式，可得：式，可得：(3) (3) 优缺点优缺点优缺点优缺点 优点：消除个体适应度差别悬殊时的影响，代替适应度的缩放技术。

优点：消除个体适应度差别悬殊时的影响，代替适应度的缩放技术 缺点：抹杀个体适应度的实际差别，未能充分运用遗传信息缺点：抹杀个体适应度的实际差别，未能充分运用遗传信息 9.3.3 9.3.3 竞技选择法竞技选择法竞技选择法竞技选择法 (tournament selection)(tournament selection) (1) (1) 方法简介方法简介方法简介方法简介 这种选择法通过相互竞争，优胜者成为下一代的个体在每一代群体中，每次这种选择法通过相互竞争，优胜者成为下一代的个体在每一代群体中，每次 都随机选择都随机选择 k个个体构成一个小群体，然后从这个个体构成一个小群体，然后从这 k个个体中确定性地取适应度最个个体中确定性地取适应度最 大的个体复制，进入下一代群体被复制后的个体仍返回父代群体中，参加下大的个体复制，进入下一代群体被复制后的个体仍返回父代群体中，参加下 一次一次 k个个体的随机选择这种随机选择重复个个体的随机选择这种随机选择重复M次，产生次，产生M个下一代个体．个下一代个体． (2) (2) 具体操作步骤具体操作步骤具体操作步骤具体操作步骤 Ⅰ. 从第从第t代群体中随机选择代群体中随机选择 k个个体；个个体； Ⅱ. 比较比较 k个个体的适应度，复制适应度最大者进入第个个体的适应度，复制适应度最大者进入第 t+1 代，被复制的个体代，被复制的个体 仍保留在第仍保留在第 t 代；代； Ⅲ. 重复执行重复执行Ⅰ、、 Ⅱ M次，直至产生同次，直至产生同 t 代一样的个体数目。

代一样的个体数目 (3) (3) 特点特点特点特点 竞技选择法中，选择的力度取决于竞技选择法中，选择的力度取决于 k值的大小值的大小k值愈大，每次选出的优胜者值愈大，每次选出的优胜者 具有很高的适应度反之，具有很高的适应度反之，k值愈小，优胜者的适应度或高或低，随机性很强值愈小，优胜者的适应度或高或低，随机性很强9.3.4 9.3.4 最优保存策略（最优保存策略（最优保存策略（最优保存策略（Elitist selectionElitist selection ) 在遗传算法的运行过程中．通过对个体进行交叉、变异等遗传操作而不断地产在遗传算法的运行过程中．通过对个体进行交叉、变异等遗传操作而不断地产 生出新的个体虽然随着群体的进化过程会产生出越来越多的优良个体，但由生出新的个体虽然随着群体的进化过程会产生出越来越多的优良个体，但由 于选择、交叉、变异等遗传操作的随机性，它们也有可能破坏掉当前群体中适于选择、交叉、变异等遗传操作的随机性，它们也有可能破坏掉当前群体中适 应度最好的个体我们希望适应度最好的个体要尽可能地保留到下一代群体中。

应度最好的个体我们希望适应度最好的个体要尽可能地保留到下一代群体中 为达到这个目的，可以使用最优保存策略进化模型来进行优胜劣汰操作为达到这个目的，可以使用最优保存策略进化模型来进行优胜劣汰操作 (1) (1) 基本思想基本思想基本思想基本思想 当前群体中适应度最高的个体不参与交叉运算和变异运算，而是用它来替换当前群体中适应度最高的个体不参与交叉运算和变异运算，而是用它来替换 掉本代群体中经过交叉、变异等遗传操作后所产生的适应度最低的个体掉本代群体中经过交叉、变异等遗传操作后所产生的适应度最低的个体 (2) (2) 最优保存策略进化模型的具体操作过程最优保存策略进化模型的具体操作过程最优保存策略进化模型的具体操作过程最优保存策略进化模型的具体操作过程 Ⅰ. 找出当前群体中适应度最高的个体和适应度最低的个体找出当前群体中适应度最高的个体和适应度最低的个体 Ⅱ. 若当前群体中最佳个体的适应度比总的迄今为止的最好个体的适应度还要若当前群体中最佳个体的适应度比总的迄今为止的最好个体的适应度还要 高，则以当前群体中的最佳个体作为新的迄今为止的最好个体。

高，则以当前群体中的最佳个体作为新的迄今为止的最好个体 Ⅲ. 用迄今为止的最好个体替换掉当前群体中的最差个体用迄今为止的最好个体替换掉当前群体中的最差个体 (3) (3) 特点：特点：特点：特点：最优保存策略可视为选择操作的一部分该策略的实施可保证迄今为止最优保存策略可视为选择操作的一部分该策略的实施可保证迄今为止 所得到的最优个体不会被交叉、变异等遗传运算所破坏，它是遗传算所得到的最优个体不会被交叉、变异等遗传运算所破坏，它是遗传算 法收敛性的一个重要保证条件法收敛性的一个重要保证条件 缺点：缺点：缺点：缺点：它容易使得某个局部最优个体不易被淘汰掉反而快速扩散，从而使得它容易使得某个局部最优个体不易被淘汰掉反而快速扩散，从而使得 算法的全局搜索能力不强算法的全局搜索能力不强 (4) (4) 使用方法：使用方法：使用方法：使用方法： 该方法一般要与其他一些选择操作方法配合起来使用，方可有良好的效果。

该方法一般要与其他一些选择操作方法配合起来使用，方可有良好的效果 另外，最优保存策略还可加以推广，即在每一代的进化过程中保留多个最优个另外，最优保存策略还可加以推广，即在每一代的进化过程中保留多个最优个 体不参加交叉、变异等遗传运算，而直接将它们复制到下一代群体中这种选体不参加交叉、变异等遗传运算，而直接将它们复制到下一代群体中这种选 择方法也称为稳态复制择方法也称为稳态复制9.3.5 9.3.5 确定式采样选择确定式采样选择确定式采样选择确定式采样选择 ( Deterministic Sampling selection)( Deterministic Sampling selection) (1) (1) 基本思想：基本思想：基本思想：基本思想：按照一种确定的方式来进行选择操作按照一种确定的方式来进行选择操作 (2) (2) 具体操作过程：具体操作过程：具体操作过程：具体操作过程： Ⅰ. 计算群体中各个个体在下一代群体中的期望生存数目计算群体中各个个体在下一代群体中的期望生存数目Ni：： Ⅱ. 用用Ni 的整数部分的整数部分  Ni   确定各个对应个体在下一代群体中的生存数目确定各个对应个体在下一代群体中的生存数目 (   x   表示下取值，取不大于表示下取值，取不大于x的最大整数。

的最大整数) Ⅲ. 按照按照Ni 的小数部分对个体进行降序排序，顺序取前的小数部分对个体进行降序排序，顺序取前 M   个个体个个体 加入到下一代群体中加入到下一代群体中 至此可完全确定出下一代群体中的至此可完全确定出下一代群体中的M个个体 (3) (3) 特点：特点：特点：特点：这种选择操作方法可保证适应度较大的一些个体一定能够被保留在下这种选择操作方法可保证适应度较大的一些个体一定能够被保留在下 一代群体中，并且操作也比较简单一代群体中，并且操作也比较简单 M    Ni   i=1i=1,2,…M9.4 9.4 交叉算子交叉算子交叉算子交叉算子 在生物的自然进化过程中，两个同源染色体通过交配而重组，形成新的染色体，在生物的自然进化过程中，两个同源染色体通过交配而重组，形成新的染色体， 从而产生出新的个体或物种交配重组是生物遗传和进化过程中的一个主要环从而产生出新的个体或物种交配重组是生物遗传和进化过程中的一个主要环 节。

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

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

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

 9.4.3 9.4.3 均匀交叉均匀交叉均匀交叉均匀交叉 ( Uniform Crossover )( Uniform Crossover ) (1) (1) 均匀交叉：均匀交叉：均匀交叉：均匀交叉：指两个配对个体的每一个基因座上的基因都以相同的交叉概率进指两个配对个体的每一个基因座上的基因都以相同的交叉概率进 行交换，从而形成两个新的个体均匀交叉实际上可归属于多点行交换，从而形成两个新的个体均匀交叉实际上可归属于多点 交叉的范围交叉的范围 (2) (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的的对应对应基因基因值值。

例如，例如，均匀交叉操作的示例如下均匀交叉操作的示例如下:9.4.4 9.4.4 算术交叉算术交叉算术交叉算术交叉 ( Arithmetic Crossover )( Arithmetic Crossover ) (1) (1) 算术交叉：算术交叉：算术交叉：算术交叉：由两个个体的线性组合而产生出两个新的个体由两个个体的线性组合而产生出两个新的个体 (2) (2) 进行算术交叉的条件：进行算术交叉的条件：进行算术交叉的条件：进行算术交叉的条件：为了能够进行线性组合运算，算术交叉的操作对象一为了能够进行线性组合运算，算术交叉的操作对象一 般是由浮点数编码所表示的个体般是由浮点数编码所表示的个体 (3) (3) 算术交叉产生的新个体：算术交叉产生的新个体：算术交叉产生的新个体：算术交叉产生的新个体： 式中：式中： x 为个体；为个体；  为一参数，它可以是一个常数，此时所进行的交叉运算称为均匀为一参数，它可以是一个常数，此时所进行的交叉运算称为均匀 算术交叉；算术交叉； 它也可以是一个由进化代数所决定的变量，此时所进它也可以是一个由进化代数所决定的变量，此时所进 行的交叉运算称为非均匀算术交叉。

行的交叉运算称为非均匀算术交叉 (4) (4) 算术交叉的主要操作过程算术交叉的主要操作过程算术交叉的主要操作过程算术交叉的主要操作过程 Ⅰ. 确定两个个体进行线性组合时的系数确定两个个体进行线性组合时的系数 Ⅱ. 依据上式生成两个新的个体依据上式生成两个新的个体9.5 9.5 变异算子变异算子变异算子变异算子 (1) (1) 从遗传运算过程中产生新个体的能力方面来说从遗传运算过程中产生新个体的能力方面来说从遗传运算过程中产生新个体的能力方面来说从遗传运算过程中产生新个体的能力方面来说: : • 交叉运算是产生新个体的主要方法，它决定了遗传算法的全局搜索能力；交叉运算是产生新个体的主要方法，它决定了遗传算法的全局搜索能力； • 而变异运算只是产生新个体的辅助方法，但它也是必不可少的一个运算步骤，而变异运算只是产生新个体的辅助方法，但它也是必不可少的一个运算步骤， 因为它决定了遗传算法的局部搜索能力因为它决定了遗传算法的局部搜索能力 • 交叉算子与变异算子的相互配合，共同完成对搜索空间的全局搜索和局部搜交叉算子与变异算子的相互配合，共同完成对搜索空间的全局搜索和局部搜 索，从而使得遗传算法能够以良好的搜索性能完成最优化问题的寻优过程。

索，从而使得遗传算法能够以良好的搜索性能完成最优化问题的寻优过程 (2) (2) 在遗传算法中使用变异算子主要有以下两个目的：在遗传算法中使用变异算子主要有以下两个目的：在遗传算法中使用变异算子主要有以下两个目的：在遗传算法中使用变异算子主要有以下两个目的： (1) 改善遗传算法的局部搜索能力；改善遗传算法的局部搜索能力； (2) 维持群体的多样性，防止出现早熟现象维持群体的多样性，防止出现早熟现象 (3) (3) 变异算子的设计包括如下两方面的内容：变异算子的设计包括如下两方面的内容：变异算子的设计包括如下两方面的内容：变异算子的设计包括如下两方面的内容： • 如何确定变异点的位置如何确定变异点的位置? • 如何进行基因值替换如何进行基因值替换? 下面介绍其中较常用的几种变异操作方法，它们适合于二进制编码的个体和下面介绍其中较常用的几种变异操作方法，它们适合于二进制编码的个体和 浮点数编码的个体浮点数编码的个体 9.5.1 9.5.1 基本位变异基本位变异基本位变异基本位变异(Simple Mutation)(Simple Mutation)9.5.2 9.5.2 均匀变异均匀变异均匀变异均匀变异(Uniform Mutation)(Uniform Mutation) (1) (1) 均匀变异操作均匀变异操作均匀变异操作均匀变异操作 指分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体指分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体 编码串中各个基因座上的原有基因值。

编码串中各个基因座上的原有基因值 (2) (2) 均匀变异的具体操作过程均匀变异的具体操作过程均匀变异的具体操作过程均匀变异的具体操作过程 Ⅰ. 依次指定个体编码串中的每个基因座为变异点依次指定个体编码串中的每个基因座为变异点 Ⅱ. 对每一个变异点，以变异概率对每一个变异点，以变异概率pm从对应基因的取值范围内取一随机数来替代从对应基因的取值范围内取一随机数来替代 原有基因值原有基因值 (3) (3) 举例举例举例举例 假设有一个体为假设有一个体为X=x1x2…xk…xn , 若若xk为变异点，其取值范围为为变异点，其取值范围为[Ukmin,Ukmax], 在该点对个体在该点对个体X进行均匀变异操作后，可得到一个新的个体进行均匀变异操作后，可得到一个新的个体X=x1x2…xk’…xn, 其中变异点的新基因值是：其中变异点的新基因值是： xk’ = Ukmin + r · (Ukmax – Ukmin ) 式中，式中，r 为为[0, 1] 范围内符合均匀概率分布的一个随机数。

范围内符合均匀概率分布的一个随机数 (4) (4) 适用范围适用范围适用范围适用范围 均匀变异操作持别适合应用于遗传算法的初期运行阶段，它使得搜索点可以在整均匀变异操作持别适合应用于遗传算法的初期运行阶段，它使得搜索点可以在整 个搜索空间内自由地移动，从而可以增加群体的多样性，使算法处理更多的模式个搜索空间内自由地移动，从而可以增加群体的多样性，使算法处理更多的模式 9.5.3 9.5.3 边界变异边界变异边界变异边界变异(Boundary mutation)(Boundary mutation) (1) (1) 边界变异边界变异边界变异边界变异 均匀变异操作的一个变形算法在进行边界变异操作时，随机地取基因座的均匀变异操作的一个变形算法在进行边界变异操作时，随机地取基因座的 二个对应边界基因值之一去替代原有基因值二个对应边界基因值之一去替代原有基因值 (2) (2) 举例举例举例举例 假设有一个体为假设有一个体为X=x1x2…xk…xn , 若若xk为变异点，其取值范围为为变异点，其取值范围为[Ukmin,Ukmax], 在该点对个体在该点对个体X进行边界变异操作后，可得到一个新的个体进行边界变异操作后，可得到一个新的个体X=x1x2…xk’…xn, 其中变异点的新基因值是：其中变异点的新基因值是：Ukmin, if random(0,1)=0Ukmax, if random(0,1)=1xk’=式中，式中， random(0,1)表示以均等的概率从表示以均等的概率从 0, 1中任取其一。

中任取其一 (3) (3) 适用范围适用范围适用范围适用范围 当变量的取值范围特别宽，并且无其他约束条件时，边界变异会带来不好当变量的取值范围特别宽，并且无其他约束条件时，边界变异会带来不好 的作用但它特别适用于最优点位于或接近于可行解的边界时的一类问题但它特别适用于最优点位于或接近于可行解的边界时的一类问题9.5.4 9.5.4 非均匀变异（非均匀变异（非均匀变异（非均匀变异（Non_UniformNon_Uniform Mutation) Mutation) (1) (1) 均匀变异的不足均匀变异的不足均匀变异的不足均匀变异的不足 均匀变异操作取某一范围内均匀分布的随机数来替换原有基因值，可使得个体均匀变异操作取某一范围内均匀分布的随机数来替换原有基因值，可使得个体在搜索空间内自由移动但另一方面，它却不便于对某一重点区域进行局部搜索在搜索空间内自由移动但另一方面，它却不便于对某一重点区域进行局部搜索 (2) (2) 非均匀变异非均匀变异非均匀变异非均匀变异 不取均匀分布的随机数去替换原有的基因值，而是对原有基因值作一随机扰动，不取均匀分布的随机数去替换原有的基因值，而是对原有基因值作一随机扰动， 以扰动后的结果作为变异后的新基因值。

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

9.5.5 9.5.5 高斯变异高斯变异高斯变异高斯变异(Gaussian mutation)(Gaussian mutation) (1) (1) 高斯变异高斯变异高斯变异高斯变异 是改进遗传算法对重点搜索区域的局部搜索性能的另一种变异操作方法是改进遗传算法对重点搜索区域的局部搜索性能的另一种变异操作方法 所谓高斯变异操作是指进行变异操作时，用符合均值为所谓高斯变异操作是指进行变异操作时，用符合均值为 、方差为、方差为  2 的正态分布的正态分布 的一个随机数来替换原有基因值的一个随机数来替换原有基因值 (2) (2) 操作操作操作操作 • 高斯变异的具体操作过程与均匀变异类似高斯变异的具体操作过程与均匀变异类似 • 具体实现高斯变异时，符合正态分布的随机数具体实现高斯变异时，符合正态分布的随机数Q可由一些符合均匀分布的随机可由一些符合均匀分布的随机 数利用公式来近似产生数利用公式来近似产生 例：例： • 假定有假定有12个在个在[ 0, 1]范围内均匀分布的随机数范围内均匀分布的随机数 ri(i=1,2,…,12)，则符合，则符合N( , 2) 正态分布的一个随机数正态分布的一个随机数Q可由下式求得：可由下式求得： • 则新的个体则新的个体X=x1x2…xk’…xn 的新基因值的新基因值xk’由下式得到：由下式得到： • 有一个体为有一个体为X=x1x2…xk…xn , 若若xk为变异点，其取值范围为为变异点，其取值范围为[Ukmin,Ukmax], 在该点对个体在该点对个体X进行高斯变异操作，并假设进行高斯变异操作，并假设9.6 9.6 终止终止终止终止 遗传算法是一个反复迭代的过程，每次选代期间，要执行适应度计算、复制、交遗传算法是一个反复迭代的过程，每次选代期间，要执行适应度计算、复制、交 叉、变异等操作，直至满足终止条件。

叉、变异等操作，直至满足终止条件 使遗传算法终止的方法有三种：使遗传算法终止的方法有三种： (1) (1) 规定最大选代次数规定最大选代次数规定最大选代次数规定最大选代次数T T一旦遗传算法的迭代次数达到一旦遗传算法的迭代次数达到T，则停止操作，输出结，则停止操作，输出结 果通常T取取200一一500次 由于遗传算法中有许多随机因素影响，最后一代的结果不一定含有最优个体由于遗传算法中有许多随机因素影响，最后一代的结果不一定含有最优个体 为此，要经常记录每代的最优个体以便查询比较为此，要经常记录每代的最优个体以便查询比较 (2) (2) 规定最小的偏差规定最小的偏差规定最小的偏差规定最小的偏差   对于适应度目标已知的遗传算法，如用方差作为适应度计对于适应度目标已知的遗传算法，如用方差作为适应度计 算的曲线拟合问题，可用最小的偏差算的曲线拟合问题，可用最小的偏差 制定终止条件，即：制定终止条件，即： | fmax – f*| ≤   式中式中 f*——已知的适应度目标；已知的适应度目标； fmax——每代最大的适应废。

每代最大的适应废 (3)(3)观察适应度的变化趋势观察适应度的变化趋势观察适应度的变化趋势观察适应度的变化趋势在遗传算法的初期，最优个体的适应度以及群体的在遗传算法的初期，最优个体的适应度以及群体的 平均适应度都较小，以后随着复制、交叉平均适应度都较小，以后随着复制、交叉 、变异等操作，适应度值增加到、变异等操作，适应度值增加到 了遗传算法后期，这种增加已趋缓和或停止．一旦这种增加停止，即中止遗了遗传算法后期，这种增加已趋缓和或停止．一旦这种增加停止，即中止遗 传算法9.7 9.7 遗传算法的高级实现技术遗传算法的高级实现技术遗传算法的高级实现技术遗传算法的高级实现技术 9.7.1 9.7.1 倒位算子倒位算子倒位算子倒位算子 9.7.2 9.7.2 二倍体与显性操作算子二倍体与显性操作算子二倍体与显性操作算子二倍体与显性操作算子 9.7.3 9.7.3 变长度染色体遗传算法变长度染色体遗传算法变长度染色体遗传算法变长度染色体遗传算法 9.7.4 9.7.4 小生境遗传算法小生境遗传算法小生境遗传算法小生境遗传算法 9.7.59.7.5 混合遗传算法混合遗传算法混合遗传算法混合遗传算法。