第四章遗传算法的实现技术

第四章遗传算法的实现技术80年代以后，遗传算法得到了广泛的使用，在实践过程中，人们对遗传算法的实施提出了许多改进。本节分别予以介绍。4.1编码方法[编码的重要性]编码是应用遗传算法时要解决的首要问题，也是设计遗传算法的一个关键步骤。•编码方法除了决定个体的染色体排列形式之外，它还决定了个体从搜索空间的基因型变换到解空间的表现型时的解码方法;•编码方法也影响到交叉算子、变异算子等遗传算子的运算方法。由此可见，编码方法在很大程度上决定了如何进行群体的遗传进化运算以及遗传进化运算的效率。[编码原则]针对一个具体应用问题，如何设计一种完美的编码方案一直是遗传算法的应用难点之一，也是遗传算法的一个重要研究方向。可以说目前还没有一套既严密又完整的指导理论及评价准则能够帮助我们设计编码方案。作为参考，DeJong曾提出了两条操作性较强的实用编码原则(又称为编码规则)：•编码原则一(有意义积木块编码原则)：应使用能易于产生与所求问题相关的且具有低阶、短定义长度模式的编码方案。•编码原则二(最小字符集编码原则)：应使用能使问题得到自然表示或描述的具有最小编码字符集的编码方案。由于遗传算法应用的广泛性，迄今为止人们已经提出了许多种不同的编码方法。总的来说，这些编码方法可以分为三大类：二进制编码方法浮点数编码方法符号编码方法4.1.1二进制编码方法二进制编码方法是遗传算法中最常用的一种编码方法，它使用的编码符号集是由二进制符号0和1所组成的二值符号集{0，1}，它所构成的个体基因型是一个二进制编码符号串。(1)编码假设某一参数的取值范围是[umax,umin]，我们用长度为l的二进制编码符号串来表示该参数，则它总共能够产生2l种不同的编码，参数编码时的对应关系如下：00000000…00000000＝0umin00000000…00000001＝1umin+……11111111…11111111=2l–1umax二进制编码的编码精度为：=Umaxumin2l1(2)解码假设某一个体的编码是：x：blbl-1bl-2……b2b1则对应的解码公式为：例如，对于x[0,1023]，若用10位长的二进制编码表示该参数的话，则下述符号串：x：0010101111就可表示一个个体，它所对应的参数值是x＝175。编码精度为=1。x=umin+(bi·2i-1)·1i=lUmaxumin2l1(3)二进制编码方法的优点：Ⅰ.编码、解码操作简单易行；Ⅱ.交叉、变异等遗传操作便于实现；Ⅲ.符合最小字符集编码原则（使用能使问题得到自然表示或描述的具有最小编码字符集的编码方案。）；Ⅳ.便于利用模式定理对算法进行理论分析。4.1.2格雷码编码方法格雷码编码方法是二进制编码方法的一种变形。(1)格雷码编码：其连续的两个整数所对应的编码值之间仅仅只有一个码位是不相同的，其余码位都完全相同。如图所示。(2)优点：•便于提高遗传算法的局部搜索能力；•交叉、变异等遗传操作便于实现；•符合最小字符集编码原则；•便于利用模式定理对算法进行理论分析。44.1.3浮点数编码方法(1)二进制编码的缺点•二进制编码存在着连续函数离散化时的映射误差。个体编码串的长度较短时，可能达不到精度要求；个体编码串的长度较长时，虽然能提高编码精度，但却会使遗传算法的搜索空间急剧扩大。•二进制编码不便于反映所求问题的特定知识，这样也就不便于开发针对问题专门知识的遗传运算算子，人们在一些经典优化算法的研究中所总结出的一些宝贵经验也就无法在这里加以利用，也不便于处理非平凡约束条件。(2)浮点数编码方法个体的每个基因值用某一范围内的一个浮点数来表示；个体的编码长度等于其决策变量的个数。因为这种编码方法使用的是决策变量的真实值，所以浮点数编码方法也叫做真值编码方法。例如，如果一个优化问题含有5个变量xi(i＝1,2,…,5)，每个变量都有其对应的上下限[Uimin,Uimax]，则：5.806.903.503.805.00x:表示一个体的基因型，其对应的表现型是：x：[5.80，6.90，3.50，3.80，5.00]T。(3)注意事项：•在浮点数编码方法中:必须保证基因值在给定的区间限制范围内；遗传算法中所使用的交叉、变异等遗传算子也必须保证其运算结果所产生的新个体的基因值也在这个区间限制范围内。•当用多个字节来表示一个基因值时，交叉运算必须在两个基因的分界字节处进行，而不能在某个基因的中间字节分隔处进行。(4)浮点数编码方法的优点：•适合于在遗传算法中表示范围较大的数；•适合于精度要求较高的遗传算法；•便于较大空间的遗传搜索；•改善了遗传算法的计算复杂性，提高了运算效率；•便于遗传算法与经典优化方法的混合使用；•便于设计针对问题的专门知识的知识型遗传算子；•便于处理复杂的决策变量约束条件。4.1.4符号编码方法(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][旅行商问题(TravelingSalesmanProblem，简称TSP)可描述为；已知n个城市之间的相互距离。现有一推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短?](2)符号编码的主要优点：•符合有意义积木块编码原则。•便于在遗传算法中利用所求解问题的专门知识。•便于遗传算法与相关近似算法之间的混合使用。但对于使用符号编码方法的遗传算法，一般需要认真设计交叉、变异等遗传运算的操作方法，以满足问题的各种约束要求，这样才能提高算法的搜索性能。4.1.5多参数级联编码方法4.1.5多参数交叉编码方法4.2适应度函数•在研究自然界生物的遗传和进化现象时，生物学家使用适应度这个术语来度量某个物种对于其生存环境的适应程度。•与此相类似，遗传算法中也使用适应度这个概念来度量群体中各个个体在优化计算中有可能达到或接近于或有助于找到最优解的优良程度。度量个体适应度的函数称为适应度函数。4.2.1目标函数与适应度函数遗传算法的一个特点是它仅使用所求问题的目标函数值就可以得到下一步的有关搜索信息。最优化问题可分为两大类，一类为求目标函数的全局最大值，另一类为求目标函数的全局最小值。对于这两类优化问题，第二章中已经介绍过由解空间中某一点的目标函数值f(x)到搜索空间中对应个体的适应度函数值F(x)的转换方法：•对于求最大值的问题，作下述转换：F(X)=f(X)+Cminiff(X)+Cmin00iff(X)+Cmin≤0•对于求最小值问题，变换如下：F(X)=Cmax-f(X)iff(X)Cmax0iff(X)Cmax4.2.2适应度尺度变换(1)适应度尺度变换的原因在遗传算法中，各个个体被遗传到下一代群体中的概率是由该个体的适应度来确定的，应用实践表明，仅使用以上两式来计算个体适应度时，有些遗传算法会收敛得很快，也有些遗传算法会收敛得很慢。•在遗传算法运行的初期阶段群体中可能会有少数几个个体的适应度相对其他个体来说非常高。若按照常用的比例选择算子来确定个体的遗传数量时，则这几个相对较好的个体将在下一代群体中占有很高的比例，在极端情况下或当群体现模较小时，新的群体甚至完全由这样的少数几个个体所组成。这时产生新个体作用较大的交叉算子就起不了什么作用，因为相同的两个个体不论在何处进行交叉操作都永远不会产生出新的个体，如下所示：A:101010101010101010101010B:101010101010101010101010单点交叉这样就会使群体的多样性降低，容易导致遗传算法发生早熟现象（或称早期收敛)，使遗传算法所求到的解停留在某一局部最优点上。因此，我们希望在遗传算法运行的初期阶段，算法能够对一些适应度较高的个体进行控制，降低其适应度与其他个体适应度之间的差异程度，从而限制其复制数量，以维护群体的多样性。•在遗传算法运行的后期阶段群体中所有个体的平均适应度可能会接近于群体中最佳个体的适应度。也就是说，大部分个体的适应度和最佳个体的适应度差异不大，它们之间无竞争力，都会有以相接近的概率被遗传到下一代的可能性，从而使得进化过程无竞争性可言，只是一种随机的选择过程。这将导致无法对某些重点区域进行重点搜索，从而影响遗传算法的运行效率。因此，我们希望在遗传算法运行的后期阶段，算法能够对个体的适应度进行适当的放大，扩大最佳个体适应度与其他个体适应度之间的差异程度，以提高个体之间的竞争性。(2)适应度尺度变换定义在遗传算法运行的不同阶段，有时需要对个体的适应度进行适当的扩大或缩小。这种对个体适应度所做的扩大或缩小变换就称为适应度尺度变换。(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)计算适应度非负判别式：FminC·Favg-FmaxC-1若不等式满足，则执行(2)，否则执行(3)。(2)正常情况下的缩放：C-1a=Fmax-FavgFavgFmax-C·Favgb=Fmax-FavgFavg(3)负适应度时的缩放：a=FavgFavg-Fminb=Favg·FminFavg-FminⅡ.乘幂尺度变换乘幂尺度变换的公式为：F’=Fk即新的适应度是原有适应度的某个指定乘幂。幂指数k与所求解的问题有关，并且在算法的执行过程中需要不断对其进行修正才能使尺度变换满足一定的伸缩要求。Ⅲ.指数尺度变换指数尺度变换的公式为：F’＝exp(-F)即新的适应度是原有适应度的某个指数。式中系数决定了选择的强制性，越小，原有适应度较高的个体的新适应度就越与其他个体的新适应度相差较大，亦即越增加了选择该个体的强制性。4.2.3约束条件的处理方法实际应用中的优化问题一般都含有一定的约束条件，它们的描述形式各种各样。在遗传算法的应用中，必须对这些约束条件进行处理，而目前还未找到一种能够处理各种约束条件的一般化方法。所以对约束条件进行处理时，只能是针对具体应用问题及约束条件的特征，再考虑遗传算法中遗传算子的运行能力，选用不同的处理方法。在构造遗传算法时，处理约束条件的常用方法主要有如下三种：搜索空间限定法罚函数法可行解变换法(1)搜索空间限定法[基本思想]对遗传算法的搜索空间的大小加以