第9章遗传算法的实现技术.ppt

《第9章遗传算法的实现技术.ppt》由会员分享，可在线阅读，更多相关《第9章遗传算法的实现技术.ppt（49页珍藏版）》请在优知文库上搜索。

1、 80年代以后，遗传算法得到了广泛的使用，在实践过程中，人们对遗传算法年代以后，遗传算法得到了广泛的使用，在实践过程中，人们对遗传算法的实施提出了许多改进。本节分别予以介绍。的实施提出了许多改进。本节分别予以介绍。编码是应用遗传算法时要解决的首要问题，也是设计遗传算法的一个关键步骤。编码是应用遗传算法时要解决的首要问题，也是设计遗传算法的一个关键步骤。编码方法除了决定个体的染色体排列形式之外，它还决定了个体从搜索空间编码方法除了决定个体的染色体排列形式之外，它还决定了个体从搜索空间 的基因型变换到解空间的表现型时的解码方法的基因型变换到解空间的表现型时的解码方法;编码方法也影响到交叉算子、变异

2、算子等遗传算子的运算方法。编码方法也影响到交叉算子、变异算子等遗传算子的运算方法。由此可见，编码方法在很大程度上决定了如何进行群体的遗传进化运算以及由此可见，编码方法在很大程度上决定了如何进行群体的遗传进化运算以及 遗传进化运算的效率。遗传进化运算的效率。针对一个具体应用问题，如何设计一种完美的编码方案一直是遗传算法的应针对一个具体应用问题，如何设计一种完美的编码方案一直是遗传算法的应 用难点之一，也是遗传算法的一个重要研究方向。可以说目前还没有一套既严密用难点之一，也是遗传算法的一个重要研究方向。可以说目前还没有一套既严密 又完整的指导理论及评价准则能够帮助我们设计编码方案。作为参考，又完整

3、的指导理论及评价准则能够帮助我们设计编码方案。作为参考，De Jong 曾提出了两条操作性较强的实用编码原则曾提出了两条操作性较强的实用编码原则(又称为编码规则又称为编码规则)：编码原则一编码原则一(有意义积木块编码原则有意义积木块编码原则)：应使用能易于产生与所求问题相关的且：应使用能易于产生与所求问题相关的且 具有低阶、短定义长度模式的编码方案。具有低阶、短定义长度模式的编码方案。编码原则二编码原则二(最小字符集编码原则最小字符集编码原则)：应使用能使问题得到自然表示或描述的具：应使用能使问题得到自然表示或描述的具 有最小编码字符集的编码方案。有最小编码字符集的编码方案。由于遗传算法应用的

4、广泛性，迄今为止人们已经提出了许多种不同的编码方法。由于遗传算法应用的广泛性，迄今为止人们已经提出了许多种不同的编码方法。总的来说，这些编码方法可以分为三大类：总的来说，这些编码方法可以分为三大类：二进制编码方法二进制编码方法 浮点数编码方法浮点数编码方法 符号编码方法符号编码方法 二进制编码方法是遗传算法中最常用的一种编码方法，它使用的编码符号集二进制编码方法是遗传算法中最常用的一种编码方法，它使用的编码符号集 是由二进制符号是由二进制符号0和和1所组成的二值符号集所组成的二值符号集0，1，它所构成的个体基因型是一个，它所构成的个体基因型是一个 二进制编码符号串。二进制编码符号串。假设某一参

5、数的取值范围是假设某一参数的取值范围是umax,umin，我们用长度为，我们用长度为l的二进制编码符号串的二进制编码符号串 来表示该参数，则它总共能够产生来表示该参数，则它总共能够产生 2l种不同的编码，参数编码时的对应关系如种不同的编码，参数编码时的对应关系如 下：下：00000000000000000 umin 00000000000000011 umin+1111111111111111=2l1 umax 二进制编码的编码精度为：二进制编码的编码精度为：=Umax umin2l 1 假设某一个体的编码是：假设某一个体的编码是：x：bl bl-1 bl-2b2b1 则对应的解码公式为：则对

6、应的解码公式为：例如，对于例如，对于 x 0,1023，若用，若用 10 位长的二进制编码表示该参数的话，位长的二进制编码表示该参数的话，则下述符号串：则下述符号串：x：0010101111 就可表示一个个体，就可表示一个个体，它所对应的参数值是它所对应的参数值是 x175。编码精度为编码精度为 =1。x=umin+(bi 2i-1)1i=lUmax umin2l 1 .编码、解码操作简单易行；编码、解码操作简单易行；.交叉、变异等遗传操作便于实现；交叉、变异等遗传操作便于实现；.符合最小字符集编码原则（使用能使问题得到自然表示或描述的具有最小符合最小字符集编码原则（使用能使问题得到自然表示或

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

8、算法进行理论分析。便于利用模式定理对算法进行理论分析。4 二进制编码存在着连续函数离散化时的映射误差。二进制编码存在着连续函数离散化时的映射误差。个体编码串的长度较短时，可能达不到精度要求；个体编码串的长度较短时，可能达不到精度要求；个体编码串的长度较长时，虽然能提高编码精度，但却会使遗传算法的搜索个体编码串的长度较长时，虽然能提高编码精度，但却会使遗传算法的搜索 空间急剧扩大。空间急剧扩大。二进制编码不便于反映所求问题的特定知识，这样也就不便于开发针对问题二进制编码不便于反映所求问题的特定知识，这样也就不便于开发针对问题专专 门知识的遗传运算算子，人们在一些经典优化算法的研究中所总结出的一些

9、门知识的遗传运算算子，人们在一些经典优化算法的研究中所总结出的一些 宝贵经验也就无法在这里加以利用，也不便于处理非平凡约束条件。宝贵经验也就无法在这里加以利用，也不便于处理非平凡约束条件。个体的每个基因值用某一范围内的一个浮点数来表示；个体的每个基因值用某一范围内的一个浮点数来表示；个体的编码长度等于其决策变量的个数。个体的编码长度等于其决策变量的个数。因为这种编码方法使用的是决策变量的真实值，所以浮点数编码方法也叫做因为这种编码方法使用的是决策变量的真实值，所以浮点数编码方法也叫做 真值编码方法。真值编码方法。例如，如果一个优化问题含有例如，如果一个优化问题含有5个变量个变量xi(i1,2,

10、5)，每个变量都有其对应的上，每个变量都有其对应的上 下限下限Uimin,Uimax，则：，则：5.80 6.90 3.50 3.80 5.00 x:表示一个体的基因型，表示一个体的基因型，其对应的表现型是：其对应的表现型是：x：5.80，6.90，3.50，3.80，5.00T。在浮点数编码方法中在浮点数编码方法中:必须保证基因值在给定的区间限制范围内；遗传算法中所使用的交叉、变异必须保证基因值在给定的区间限制范围内；遗传算法中所使用的交叉、变异 等遗传算子也必须保证其运算结果所产生的新个体的基因值也在这个区间限等遗传算子也必须保证其运算结果所产生的新个体的基因值也在这个区间限 制范围内。制

11、范围内。当用多个字节来表示一个基因值时，交叉运算必须在两个基因的分界字节处进当用多个字节来表示一个基因值时，交叉运算必须在两个基因的分界字节处进 行，而不能在某个基因的中间字节分隔处进行。行，而不能在某个基因的中间字节分隔处进行。适合于在遗传算法中表示范围较大的数；适合于在遗传算法中表示范围较大的数；适合于精度要求较高的遗传算法；适合于精度要求较高的遗传算法；便于较大空间的遗传搜索；便于较大空间的遗传搜索；改善了遗传算法的计算复杂性，提高了运算效率；改善了遗传算法的计算复杂性，提高了运算效率；便于遗传算法与经典优化方法的混合使用；便于遗传算法与经典优化方法的混合使用；便于设计针对问题的专门知识

12、的知识型遗传算子；便于设计针对问题的专门知识的知识型遗传算子；便于处理复杂的决策变量约束条件。便于处理复杂的决策变量约束条件。个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集。个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集。这个符号集可以是一个字母表，如这个符号集可以是一个字母表，如 A,B,C,D,；也可以是一个数宇序号表，如也可以是一个数宇序号表，如 1,2,3,4,5,；还可以是一个代码表，如还可以是一个代码表，如 Al,A2,A3,A4,A5,等等。等等。例如例如：对于旅行商问题，假设有：对于旅行商问题，假设有n个城市分别记为个城市分别记为 C

13、1,C2,Cn，将各个城市的，将各个城市的 代号按其被访问的顺序连接在一起，就可构成一个表示旅行路线的个体，如：代号按其被访问的顺序连接在一起，就可构成一个表示旅行路线的个体，如：X：C1,C2,Cn 若将各个城市按其代号的下标进行编号，则这个个体也可表示为：若将各个城市按其代号的下标进行编号，则这个个体也可表示为：X：1，2，n 旅行商问题旅行商问题(Traveling Salesman Problem，简称，简称TSP)可描述为；可描述为；已知已知n个城市之间的相互距离。现有一推销员必须遍访这个城市之间的相互距离。现有一推销员必须遍访这n个城市，并且每个城市个城市，并且每个城市 只能访问一

14、次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可 使其旅行路线的总长度最短使其旅行路线的总长度最短?符合有意义积木块编码原则。符合有意义积木块编码原则。便于在遗传算法中利用所求解问题的专门知识。便于在遗传算法中利用所求解问题的专门知识。便于遗传算法与相关近似算法之间的混合使用。便于遗传算法与相关近似算法之间的混合使用。但对于使用符号编码方法的遗传算法，一般需要认真设计交叉、变异等遗传运但对于使用符号编码方法的遗传算法，一般需要认真设计交叉、变异等遗传运 算的操作方法，以满足问题的各种约束要求，这样才能提高算法

15、的搜索性能。算的操作方法，以满足问题的各种约束要求，这样才能提高算法的搜索性能。在研究自然界生物的遗传和进化现象时，生物学家使用适应度这个术语来度量在研究自然界生物的遗传和进化现象时，生物学家使用适应度这个术语来度量 某个物种对于其生存环境的适应程度。某个物种对于其生存环境的适应程度。与此相类似，遗传算法中也使用适应度这个概念来度量群体中各个个体在优化与此相类似，遗传算法中也使用适应度这个概念来度量群体中各个个体在优化 计算中有可能达到或接近于或有助于找到最优解的优良程度。计算中有可能达到或接近于或有助于找到最优解的优良程度。度量个体适应度的函数称为适应度函数。度量个体适应度的函数称为适应度函

16、数。遗传算法的一个特点是它仅使用所求问题的目标函数值就可以得到下一步的遗传算法的一个特点是它仅使用所求问题的目标函数值就可以得到下一步的 有关搜索信息。有关搜索信息。最优化问题可分为两大类，一类为求目标函数的全局最大值，另一类为求目标函最优化问题可分为两大类，一类为求目标函数的全局最大值，另一类为求目标函 数的全局最小值。对于这两类优化问题，第二章中已经介绍过由解空间中某一点的数的全局最小值。对于这两类优化问题，第二章中已经介绍过由解空间中某一点的 目标函数值目标函数值 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 在遗传算法中，各个个体被遗传到下一代群体中的概率是由该个体的适应度来在遗传算法中，各个个体被遗传到下一代群体中的概率是由该个体