《第四章遗传算法的实现技术优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第四章遗传算法的实现技术优秀PPT.ppt（49页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 :/elecfans 电子发烧友 :/bbs.elecfan 电子技术论坛第四章第四章 遗传算法的实现技术遗传算法的实现技术 80年头以后，遗传算法得到了广年头以后，遗传算法得到了广泛的运用，在实践过程中，人们对泛的运用，在实践过程中，人们对遗传算法的实施提出了很多改进。遗传算法的实施提出了很多改进。本节分别予以介绍。本节分别予以介绍。4.1 编码方法编码方法 编码的重要性编码的重要性 编码是应用遗传算法时要解决的首编码是应用遗传算法时要解决的首要问题，也是设计遗传算法的一个要问题，也是设计遗传算法的一个关键步骤。关键步骤。编码方法除了确定个体的染色体编码方法除了确定个体的染色体排列形式之外
2、，它还确定了个体从排列形式之外，它还确定了个体从搜寻空间搜寻空间 的基因型变换到解空间的表现型的基因型变换到解空间的表现型时的解码方法时的解码方法;编码方法也影响到交叉算子、变编码方法也影响到交叉算子、变异算子等遗传算子的运算方法。异算子等遗传算子的运算方法。由此可见，编码方法在很大程由此可见，编码方法在很大程度上确定了如何进行群体的遗传进度上确定了如何进行群体的遗传进化运算以及化运算以及 遗传进化运算的效率。遗传进化运算的效率。:/elecfans 电子发烧友 :/bbs.elecfan 电子技术论坛 编码原则编码原则编码原则编码原则 针对一个具体应用问题，如何设计一种完备的编码方案始终是遗
3、传算法的应针对一个具体应用问题，如何设计一种完备的编码方案始终是遗传算法的应针对一个具体应用问题，如何设计一种完备的编码方案始终是遗传算法的应针对一个具体应用问题，如何设计一种完备的编码方案始终是遗传算法的应 用难点之一，也是遗传算法的一个重要探讨方向。可以说目前还没有一套既严密用难点之一，也是遗传算法的一个重要探讨方向。可以说目前还没有一套既严密用难点之一，也是遗传算法的一个重要探讨方向。可以说目前还没有一套既严密用难点之一，也是遗传算法的一个重要探讨方向。可以说目前还没有一套既严密 又完整的指导理论及评价准则能够帮助我们设计编码方案。作为参考，又完整的指导理论及评价准则能够帮助我们设计编码
4、方案。作为参考，又完整的指导理论及评价准则能够帮助我们设计编码方案。作为参考，又完整的指导理论及评价准则能够帮助我们设计编码方案。作为参考，De JongDe Jong 曾提出了两条操作性较强的好用编码原则曾提出了两条操作性较强的好用编码原则曾提出了两条操作性较强的好用编码原则曾提出了两条操作性较强的好用编码原则(又称为编码规则又称为编码规则又称为编码规则又称为编码规则)：编码原则一编码原则一编码原则一编码原则一(有意义积木块编码原则有意义积木块编码原则有意义积木块编码原则有意义积木块编码原则)：应运用能易于产生与所求问题相关的且：应运用能易于产生与所求问题相关的且：应运用能易于产生与所求问题
5、相关的且：应运用能易于产生与所求问题相关的且 具有低阶、短定义长度模式的编码方案。具有低阶、短定义长度模式的编码方案。具有低阶、短定义长度模式的编码方案。具有低阶、短定义长度模式的编码方案。编码原则二编码原则二编码原则二编码原则二(最小字符集编码原则最小字符集编码原则最小字符集编码原则最小字符集编码原则)：应运用能使问题得到自然表示或描述的具：应运用能使问题得到自然表示或描述的具：应运用能使问题得到自然表示或描述的具：应运用能使问题得到自然表示或描述的具 有最小编码字符集的编码方案。有最小编码字符集的编码方案。有最小编码字符集的编码方案。有最小编码字符集的编码方案。由于遗传算法应用的广泛性，迄
6、今为止人们已经提出了很多种不同的编码方法。由于遗传算法应用的广泛性，迄今为止人们已经提出了很多种不同的编码方法。由于遗传算法应用的广泛性，迄今为止人们已经提出了很多种不同的编码方法。由于遗传算法应用的广泛性，迄今为止人们已经提出了很多种不同的编码方法。总的来说，这些编码方法可以分为三大类：总的来说，这些编码方法可以分为三大类：总的来说，这些编码方法可以分为三大类：总的来说，这些编码方法可以分为三大类：二进制编码方法二进制编码方法二进制编码方法二进制编码方法 浮点数编码方法浮点数编码方法浮点数编码方法浮点数编码方法 符号编码方法符号编码方法符号编码方法符号编码方法 :/elecfans 电子发烧
7、友 :/bbs.elecfan 电子技术论坛 4.1.1 二进制编码方法二进制编码方法 二进制编码方法是遗传算法中最常用的一种编码方法，它运用的编码符号集二进制编码方法是遗传算法中最常用的一种编码方法，它运用的编码符号集 是由二进制符号是由二进制符号0和和1所组成的二值符号集所组成的二值符号集0，1，它所构成的个体基因型是一个，它所构成的个体基因型是一个 二进制编码符号串。二进制编码符号串。(1)编码编码 假设某一参数的取值范围是假设某一参数的取值范围是umax,umin，我们用长度为，我们用长度为l的二进制编码符号的二进制编码符号串串 来表示该参数，则它总共能够产生来表示该参数，则它总共能够
8、产生 2l种不同的编码，参数编码时的对应关系如种不同的编码，参数编码时的对应关系如 下：下：00000000000000000 umin 00000000000000011 umin+1111111111111111=2l1 umax 二进制编码的编码精度为：二进制编码的编码精度为：=Umax umin2l 1 :/elecfans 电子发烧友 :/bbs.elecfan 电子技术论坛(2)(2)解码解码解码解码 假设某一个体的编码是：假设某一个体的编码是：x：bl bl-1 bl-2b2b1 则对应的解码公式为：则对应的解码公式为：例如，对于例如，对于 x 0,1023，若用，若用 10 位
9、长的二进制编码表示该参数的话，位长的二进制编码表示该参数的话，则下述符号串：则下述符号串：x：0010101111 就可表示一个个体，就可表示一个个体，它所对应的参数值是它所对应的参数值是 x175。编码精度为编码精度为 =1。x=umin+(bi 2i-1)1i=lUmax umin2l 1 :/elecfans 电子发烧友 :/bbs.elecfan 电子技术论坛(3)二进制编码方法的优点：二进制编码方法的优点：.编码、解码操作简洁易行；编码、解码操作简洁易行；.交叉、变异等遗传操作便于实现；交叉、变异等遗传操作便于实现；.符合最小字符集编码原则（运用能使问题得到自然表示或描述的具有最小符
10、合最小字符集编码原则（运用能使问题得到自然表示或描述的具有最小 编码字符集的编码方案。）；编码字符集的编码方案。）；.便于利用模式定理对算法进行理论分析。便于利用模式定理对算法进行理论分析。:/elecfans 电子发烧友 :/bbs.elecfan 电子技术论坛4.1.2 4.1.2 格雷码编码方法格雷码编码方法格雷码编码方法格雷码编码方法 格雷码编码方法是二进制编码方法的一种变形。格雷码编码方法是二进制编码方法的一种变形。格雷码编码方法是二进制编码方法的一种变形。格雷码编码方法是二进制编码方法的一种变形。(1)(1)格雷码编码：格雷码编码：格雷码编码：格雷码编码：其连续的两个整数所对应的编
11、码值之间仅仅只有一个码位是不相同的，其连续的两个整数所对应的编码值之间仅仅只有一个码位是不相同的，其连续的两个整数所对应的编码值之间仅仅只有一个码位是不相同的，其连续的两个整数所对应的编码值之间仅仅只有一个码位是不相同的，其余码位都完全相同。如图所示。其余码位都完全相同。如图所示。其余码位都完全相同。如图所示。其余码位都完全相同。如图所示。(2)(2)优点：优点：优点：优点：便于提高遗传算法的局部搜寻实力；便于提高遗传算法的局部搜寻实力；便于提高遗传算法的局部搜寻实力；便于提高遗传算法的局部搜寻实力；交叉、变异等遗传操作便于实现；交叉、变异等遗传操作便于实现；交叉、变异等遗传操作便于实现；交叉
12、、变异等遗传操作便于实现；符合最小字符集编码原则；符合最小字符集编码原则；符合最小字符集编码原则；符合最小字符集编码原则；便于利用模式定理对算法进行理论分析。便于利用模式定理对算法进行理论分析。便于利用模式定理对算法进行理论分析。便于利用模式定理对算法进行理论分析。:/elecfans 电子发烧友 :/bbs.elecfan 电子技术论坛4 :/elecfans 电子发烧友 :/bbs.elecfan 电子技术论坛4.1.3 4.1.3 浮点数编码方法浮点数编码方法浮点数编码方法浮点数编码方法(1)(1)二进制编码的缺点二进制编码的缺点二进制编码的缺点二进制编码的缺点 二进制编码存在着连续函数
13、离散化时的映射误差。二进制编码存在着连续函数离散化时的映射误差。二进制编码存在着连续函数离散化时的映射误差。二进制编码存在着连续函数离散化时的映射误差。个体编码串的长度较短时，可能达不到精度要求；个体编码串的长度较短时，可能达不到精度要求；个体编码串的长度较短时，可能达不到精度要求；个体编码串的长度较短时，可能达不到精度要求；个体编码串的长度较长时，虽然能提高编码精度，但却会使遗传算法的搜寻个体编码串的长度较长时，虽然能提高编码精度，但却会使遗传算法的搜寻个体编码串的长度较长时，虽然能提高编码精度，但却会使遗传算法的搜寻个体编码串的长度较长时，虽然能提高编码精度，但却会使遗传算法的搜寻 空间急
14、剧扩大。空间急剧扩大。空间急剧扩大。空间急剧扩大。二进制编码不便于反映所求问题的特定学问，这样也就不便于开发针对问题专二进制编码不便于反映所求问题的特定学问，这样也就不便于开发针对问题专二进制编码不便于反映所求问题的特定学问，这样也就不便于开发针对问题专二进制编码不便于反映所求问题的特定学问，这样也就不便于开发针对问题专 门学问的遗传运算算子，人们在一些经典优化算法的探讨中所总结出的一些门学问的遗传运算算子，人们在一些经典优化算法的探讨中所总结出的一些门学问的遗传运算算子，人们在一些经典优化算法的探讨中所总结出的一些门学问的遗传运算算子，人们在一些经典优化算法的探讨中所总结出的一些 珍贵阅历也
15、就无法在这里加以利用，也不便于处理非平凡约束条件。珍贵阅历也就无法在这里加以利用，也不便于处理非平凡约束条件。珍贵阅历也就无法在这里加以利用，也不便于处理非平凡约束条件。珍贵阅历也就无法在这里加以利用，也不便于处理非平凡约束条件。(2)(2)浮点数编码方法浮点数编码方法浮点数编码方法浮点数编码方法 个体的每个基因值用某一范围内的一个浮点数来表示；个体的每个基因值用某一范围内的一个浮点数来表示；个体的每个基因值用某一范围内的一个浮点数来表示；个体的每个基因值用某一范围内的一个浮点数来表示；个体的编码长度等于其决策变量的个数。个体的编码长度等于其决策变量的个数。个体的编码长度等于其决策变量的个数。
16、个体的编码长度等于其决策变量的个数。因为这种编码方法运用的是决策变量的真实值，所以浮点数编码方法也叫做因为这种编码方法运用的是决策变量的真实值，所以浮点数编码方法也叫做因为这种编码方法运用的是决策变量的真实值，所以浮点数编码方法也叫做因为这种编码方法运用的是决策变量的真实值，所以浮点数编码方法也叫做 真值编码方法。真值编码方法。真值编码方法。真值编码方法。:/elecfans 电子发烧友 :/bbs.elecfan 电子技术论坛 例如，假如一个优化问题含有例如，假如一个优化问题含有5个变量个变量xi(i1,2,5)，每个变量都有其对应的上，每个变量都有其对应的上 下限下限Uimin,Uimax
17、，则：，则：5.80 6.90 3.50 3.80 5.00 x:表示一个体的基因型，表示一个体的基因型，其对应的表现型是：其对应的表现型是：x：5.80，6.90，3.50，3.80，5.00T。(3)留意事项：留意事项：在浮点数编码方法中在浮点数编码方法中:必需保证基因值在给定的区间限制范围内；遗传算法中所运用的交叉、变异必需保证基因值在给定的区间限制范围内；遗传算法中所运用的交叉、变异 等遗传算子也必需保证其运算结果所产生的新个体的基因值也在这个区间限等遗传算子也必需保证其运算结果所产生的新个体的基因值也在这个区间限 制范围内。制范围内。当用多个字节来表示一个基因值时，交叉运算必需在两个
18、基因的分界字节处进当用多个字节来表示一个基因值时，交叉运算必需在两个基因的分界字节处进 行，而不能在某个基因的中间字节分隔处进行。行，而不能在某个基因的中间字节分隔处进行。:/elecfans 电子发烧友 :/bbs.elecfan 电子技术论坛(4)(4)浮点数编码方法的优点：浮点数编码方法的优点：浮点数编码方法的优点：浮点数编码方法的优点：适合于在遗传算法中表示范围较大的数；适合于在遗传算法中表示范围较大的数；适合于在遗传算法中表示范围较大的数；适合于在遗传算法中表示范围较大的数；适合于精度要求较高的遗传算法；适合于精度要求较高的遗传算法；适合于精度要求较高的遗传算法；适合于精度要求较高的
19、遗传算法；便于较大空间的遗传搜寻；便于较大空间的遗传搜寻；便于较大空间的遗传搜寻；便于较大空间的遗传搜寻；改善了遗传算法的计算困难性，提高了运算效率；改善了遗传算法的计算困难性，提高了运算效率；改善了遗传算法的计算困难性，提高了运算效率；改善了遗传算法的计算困难性，提高了运算效率；便于遗传算法与经典优化方法的混合运用；便于遗传算法与经典优化方法的混合运用；便于遗传算法与经典优化方法的混合运用；便于遗传算法与经典优化方法的混合运用；便于设计针对问题的特地学问的学问型遗传算子；便于设计针对问题的特地学问的学问型遗传算子；便于设计针对问题的特地学问的学问型遗传算子；便于设计针对问题的特地学问的学问型
20、遗传算子；便于处理困难的决策变量约束条件。便于处理困难的决策变量约束条件。便于处理困难的决策变量约束条件。便于处理困难的决策变量约束条件。:/elecfans 电子发烧友 :/bbs.elecfan 电子技术论坛4.1.4 4.1.4 符号编码方法符号编码方法符号编码方法符号编码方法 (1)(1)编码方法编码方法编码方法编码方法 个体染色体编码串中的基因值取自一个多数值含义、而只有代码含义的符号集。个体染色体编码串中的基因值取自一个多数值含义、而只有代码含义的符号集。个体染色体编码串中的基因值取自一个多数值含义、而只有代码含义的符号集。个体染色体编码串中的基因值取自一个多数值含义、而只有代码含
21、义的符号集。这个符号集可以是一个字母表，如这个符号集可以是一个字母表，如这个符号集可以是一个字母表，如这个符号集可以是一个字母表，如 A,B,C,D,A,B,C,D,；也可以是一个数宇序号表，如也可以是一个数宇序号表，如也可以是一个数宇序号表，如也可以是一个数宇序号表，如 1,2,3,4,5,1,2,3,4,5,；还可以是一个代码表，如还可以是一个代码表，如还可以是一个代码表，如还可以是一个代码表，如 Al,A2,A3,A4,A5,Al,A2,A3,A4,A5,等等。等等。等等。等等。例如例如例如例如 ：对于旅行商问题，假设有：对于旅行商问题，假设有：对于旅行商问题，假设有：对于旅行商问题，假
22、设有n n个城市分别记为个城市分别记为个城市分别记为个城市分别记为 C1,C2,Cn C1,C2,Cn，将各个城市的，将各个城市的，将各个城市的，将各个城市的 代号按其被访问的依次连接在一起，就可构成一个表示旅行路途的个体，如：代号按其被访问的依次连接在一起，就可构成一个表示旅行路途的个体，如：代号按其被访问的依次连接在一起，就可构成一个表示旅行路途的个体，如：代号按其被访问的依次连接在一起，就可构成一个表示旅行路途的个体，如：X X：C1,C2,Cn C1,C2,Cn 若将各个城市按其代号的下标进行编号，则这个个体也可表示为：若将各个城市按其代号的下标进行编号，则这个个体也可表示为：若将各个
23、城市按其代号的下标进行编号，则这个个体也可表示为：若将各个城市按其代号的下标进行编号，则这个个体也可表示为：X X：11，2 2，n n 旅行商问题旅行商问题旅行商问题旅行商问题(Traveling Salesman Problem(Traveling Salesman Problem，简称，简称，简称，简称TSP)TSP)可描述为；可描述为；可描述为；可描述为；已知已知已知已知n n个城市之间的相互距离。现有一推销员必需遍访这个城市之间的相互距离。现有一推销员必需遍访这个城市之间的相互距离。现有一推销员必需遍访这个城市之间的相互距离。现有一推销员必需遍访这n n个城市，并且每个城市个城市，并
24、且每个城市个城市，并且每个城市个城市，并且每个城市 只能访问一次，最终又必需返回动身城市。如何支配他对这些城市的访问次序，可只能访问一次，最终又必需返回动身城市。如何支配他对这些城市的访问次序，可只能访问一次，最终又必需返回动身城市。如何支配他对这些城市的访问次序，可只能访问一次，最终又必需返回动身城市。如何支配他对这些城市的访问次序，可 使其旅行路途的总长度最短使其旅行路途的总长度最短使其旅行路途的总长度最短使其旅行路途的总长度最短?:/elecfans 电子发烧友 :/bbs.elecfan 电子技术论坛 (2)符号编码的主要优点：符号编码的主要优点：符合有意义积木块编码原则。符合有意义积
25、木块编码原则。便于在遗传算法中利用所求解问题的特地学问。便于在遗传算法中利用所求解问题的特地学问。便于遗传算法与相关近似算法之间的混合运用。便于遗传算法与相关近似算法之间的混合运用。但对于运用符号编码方法的遗传算法，一般须要细致设计交叉、变异等遗传运但对于运用符号编码方法的遗传算法，一般须要细致设计交叉、变异等遗传运 算的操作方法，以满足问题的各种约束要求，这样才能提高算法的搜寻性能。算的操作方法，以满足问题的各种约束要求，这样才能提高算法的搜寻性能。4.1.5 多参数级联编码方法多参数级联编码方法4.1.5 多参数交叉编码方法多参数交叉编码方法 :/elecfans 电子发烧友 :/bbs.
26、elecfan 电子技术论坛4.2 4.2 适应度函数适应度函数适应度函数适应度函数 在探讨自然界生物的遗传和进化现象时，生物学家运用适应度这个术语来度量在探讨自然界生物的遗传和进化现象时，生物学家运用适应度这个术语来度量在探讨自然界生物的遗传和进化现象时，生物学家运用适应度这个术语来度量在探讨自然界生物的遗传和进化现象时，生物学家运用适应度这个术语来度量 某个物种对于其生存环境的适应程度。某个物种对于其生存环境的适应程度。某个物种对于其生存环境的适应程度。某个物种对于其生存环境的适应程度。与此相类似，遗传算法中也运用适应度这个概念来度量群体中各个个体在优化与此相类似，遗传算法中也运用适应度这
27、个概念来度量群体中各个个体在优化与此相类似，遗传算法中也运用适应度这个概念来度量群体中各个个体在优化与此相类似，遗传算法中也运用适应度这个概念来度量群体中各个个体在优化 计算中有可能达到或接近于或有助于找到最优解的优良程度。计算中有可能达到或接近于或有助于找到最优解的优良程度。计算中有可能达到或接近于或有助于找到最优解的优良程度。计算中有可能达到或接近于或有助于找到最优解的优良程度。度量个体适应度的函数称为适应度函数。度量个体适应度的函数称为适应度函数。度量个体适应度的函数称为适应度函数。度量个体适应度的函数称为适应度函数。4.2.1 4.2.1 目标函数与适应度函数目标函数与适应度函数目标函
28、数与适应度函数目标函数与适应度函数 遗传算法的一个特点是它仅运用所求问题的目标函数值就可以得到下一步的遗传算法的一个特点是它仅运用所求问题的目标函数值就可以得到下一步的遗传算法的一个特点是它仅运用所求问题的目标函数值就可以得到下一步的遗传算法的一个特点是它仅运用所求问题的目标函数值就可以得到下一步的 有关搜寻信息。有关搜寻信息。有关搜寻信息。有关搜寻信息。最优化问题可分为两大类，一类为求目标函数的全局最大值，另一类为求目标函最优化问题可分为两大类，一类为求目标函数的全局最大值，另一类为求目标函最优化问题可分为两大类，一类为求目标函数的全局最大值，另一类为求目标函最优化问题可分为两大类，一类为求
29、目标函数的全局最大值，另一类为求目标函 数的全局最小值。对于这两类优化问题，其次章中已经介绍过由解空间中某一点的数的全局最小值。对于这两类优化问题，其次章中已经介绍过由解空间中某一点的数的全局最小值。对于这两类优化问题，其次章中已经介绍过由解空间中某一点的数的全局最小值。对于这两类优化问题，其次章中已经介绍过由解空间中某一点的 目标函数值目标函数值目标函数值目标函数值 f(x)f(x)到搜寻空间中对应个体的适应度函数值到搜寻空间中对应个体的适应度函数值到搜寻空间中对应个体的适应度函数值到搜寻空间中对应个体的适应度函数值F(x)F(x)的转换方法：的转换方法：的转换方法：的转换方法：对于求最大值
30、的问题，作下述转换：对于求最大值的问题，作下述转换：对于求最大值的问题，作下述转换：对于求最大值的问题，作下述转换：F(X)=f(X)+Cmin if f(X)+Cmin 00 if f(X)+Cmin 0 :/elecfans 电子发烧友 :/bbs.elecfan 电子技术论坛 对于求最小值问题，变换如下：对于求最小值问题，变换如下：F(X)=Cmax-f(X)if f(X)Cmax0 if f(X)Cmax 4.2.2 4.2.2 适应度尺度变换适应度尺度变换适应度尺度变换适应度尺度变换 (1)(1)适应度尺度变换的缘由适应度尺度变换的缘由适应度尺度变换的缘由适应度尺度变换的缘由 在遗传
31、算法中，各个个体被遗传到下一代群体中的概率是由该个体的适应度来在遗传算法中，各个个体被遗传到下一代群体中的概率是由该个体的适应度来在遗传算法中，各个个体被遗传到下一代群体中的概率是由该个体的适应度来在遗传算法中，各个个体被遗传到下一代群体中的概率是由该个体的适应度来 确定的，应用实践表明，仅运用以上两式来计算个体适应度时，有些遗传算法确定的，应用实践表明，仅运用以上两式来计算个体适应度时，有些遗传算法确定的，应用实践表明，仅运用以上两式来计算个体适应度时，有些遗传算法确定的，应用实践表明，仅运用以上两式来计算个体适应度时，有些遗传算法 会收敛得很快，也有些遗传算法会收敛得很慢。会收敛得很快，也
32、有些遗传算法会收敛得很慢。会收敛得很快，也有些遗传算法会收敛得很慢。会收敛得很快，也有些遗传算法会收敛得很慢。在遗传算法运行的初期阶段在遗传算法运行的初期阶段在遗传算法运行的初期阶段在遗传算法运行的初期阶段 群体中可能会有少数几个个体的适应度相对其他个体来说特别高。若依据常群体中可能会有少数几个个体的适应度相对其他个体来说特别高。若依据常群体中可能会有少数几个个体的适应度相对其他个体来说特别高。若依据常群体中可能会有少数几个个体的适应度相对其他个体来说特别高。若依据常 用的比例选择算子来确定个体的遗传数量时，则这几个相对较好的个体将在下用的比例选择算子来确定个体的遗传数量时，则这几个相对较好的
33、个体将在下用的比例选择算子来确定个体的遗传数量时，则这几个相对较好的个体将在下用的比例选择算子来确定个体的遗传数量时，则这几个相对较好的个体将在下 一代群体中占有很高的比例，在极端状况下或当群体现模较小时，新的群体甚一代群体中占有很高的比例，在极端状况下或当群体现模较小时，新的群体甚一代群体中占有很高的比例，在极端状况下或当群体现模较小时，新的群体甚一代群体中占有很高的比例，在极端状况下或当群体现模较小时，新的群体甚 至完全由这样的少数几个个体所组成。这时产生新个体作用较大的交叉算子就至完全由这样的少数几个个体所组成。这时产生新个体作用较大的交叉算子就至完全由这样的少数几个个体所组成。这时产生
34、新个体作用较大的交叉算子就至完全由这样的少数几个个体所组成。这时产生新个体作用较大的交叉算子就 起不了什么作用，因为相同的两个个体不论在何处进行交叉操作都恒久不会产起不了什么作用，因为相同的两个个体不论在何处进行交叉操作都恒久不会产起不了什么作用，因为相同的两个个体不论在何处进行交叉操作都恒久不会产起不了什么作用，因为相同的两个个体不论在何处进行交叉操作都恒久不会产 生出新的个体，如下所示：生出新的个体，如下所示：生出新的个体，如下所示：生出新的个体，如下所示：:/elecfans 电子发烧友 :/bbs.elecfan 电子技术论坛 A:10101010 1010 10101010 1010
35、 B:10101010 1010 10101010 1010单点交叉单点交叉 这样就会使群体的多样性降低，简洁导致遗传算法发生早熟现象（或称早期收这样就会使群体的多样性降低，简洁导致遗传算法发生早熟现象（或称早期收 敛敛)，使遗传算法所求到的解停留在某一局部最优点上。，使遗传算法所求到的解停留在某一局部最优点上。因此，我们希望在遗传算法运行的初期阶段，算法能够对一些适应度较高的个因此，我们希望在遗传算法运行的初期阶段，算法能够对一些适应度较高的个 体进行限制，降低其适应度与其他个体适应度之间的差异程度，从而限制其复体进行限制，降低其适应度与其他个体适应度之间的差异程度，从而限制其复 制数量，以
36、维护群体的多样性。制数量，以维护群体的多样性。在遗传算法运行的后期阶段在遗传算法运行的后期阶段 群体中全部个体的平均适应度可能会接近于群体中最佳个体的适应度。也就群体中全部个体的平均适应度可能会接近于群体中最佳个体的适应度。也就 是说，大部分个体的适应度和最佳个体的适应度差异不大，它们之间无竞争力，是说，大部分个体的适应度和最佳个体的适应度差异不大，它们之间无竞争力，都会有以相接近的概率被遗传到下一代的可能性，从而使得进化过程无竞争性都会有以相接近的概率被遗传到下一代的可能性，从而使得进化过程无竞争性 可言，只是一种随机的选择过程。这将导致无法对某些重点区域进行重点搜寻，可言，只是一种随机的选
37、择过程。这将导致无法对某些重点区域进行重点搜寻，从而影响遗传算法的运行效率。从而影响遗传算法的运行效率。因此，我们希望在遗传算法运行的后期阶段，算法能够对个体的适应度进行因此，我们希望在遗传算法运行的后期阶段，算法能够对个体的适应度进行 适当的放大，扩大最佳个体适应度与其他个体适应度之间的差异程度，以提高适当的放大，扩大最佳个体适应度与其他个体适应度之间的差异程度，以提高 个体之间的竞争性。个体之间的竞争性。:/elecfans 电子发烧友 :/bbs.elecfan 电子技术论坛(2)(2)适应度尺度变换定义适应度尺度变换定义适应度尺度变换定义适应度尺度变换定义 在遗传算法运行的不同阶段，有
38、时须要对个体的适应度进行适当的扩大或缩小。在遗传算法运行的不同阶段，有时须要对个体的适应度进行适当的扩大或缩小。在遗传算法运行的不同阶段，有时须要对个体的适应度进行适当的扩大或缩小。在遗传算法运行的不同阶段，有时须要对个体的适应度进行适当的扩大或缩小。这种对个体适应度所做的扩大或缩小变换就称为适应度尺度变换。这种对个体适应度所做的扩大或缩小变换就称为适应度尺度变换。这种对个体适应度所做的扩大或缩小变换就称为适应度尺度变换。这种对个体适应度所做的扩大或缩小变换就称为适应度尺度变换。(3)(3)适应度尺度变换方法适应度尺度变换方法适应度尺度变换方法适应度尺度变换方法 目前常用的个体适应度尺度变换方
39、法主要有三种：线性尺度变换、乘幂尺度变目前常用的个体适应度尺度变换方法主要有三种：线性尺度变换、乘幂尺度变目前常用的个体适应度尺度变换方法主要有三种：线性尺度变换、乘幂尺度变目前常用的个体适应度尺度变换方法主要有三种：线性尺度变换、乘幂尺度变 换和指数尺度变换。换和指数尺度变换。换和指数尺度变换。换和指数尺度变换。.线性尺度变换。线性尺度变换。线性尺度变换。线性尺度变换。线性尺度变换的公式如下线性尺度变换的公式如下线性尺度变换的公式如下线性尺度变换的公式如下:F=aF+b F=aF+b 式中式中式中式中 F F原适应度；原适应度；原适应度；原适应度；F F变换后的新适应度；变换后的新适应度；变
40、换后的新适应度；变换后的新适应度；a,b a,b系数。系数。系数。系数。系数系数系数系数a,ba,b干脆影响到这个尺度变换的大小，所以对其选取有确定的要求，一般干脆影响到这个尺度变换的大小，所以对其选取有确定的要求，一般干脆影响到这个尺度变换的大小，所以对其选取有确定的要求，一般干脆影响到这个尺度变换的大小，所以对其选取有确定的要求，一般 希望它们满足下面两个条件希望它们满足下面两个条件希望它们满足下面两个条件希望它们满足下面两个条件:条件条件1：尺度变换后全部个体的新适应度的平均值：尺度变换后全部个体的新适应度的平均值 Favg 要等于其原适应度平均值要等于其原适应度平均值Favg 即：即：
41、Favg=Favg 这条要求是为了保证群体中适应度接近于平均适应度的个体能够有期盼的数这条要求是为了保证群体中适应度接近于平均适应度的个体能够有期盼的数 量被遗传到下一代群体中。量被遗传到下一代群体中。条件条件2：尺度变换后群体中新的最大适应度：尺度变换后群体中新的最大适应度 Fmax 要等于其原平均适应度要等于其原平均适应度 Favg 的指定的指定 倍数。即：倍数。即：Fmax=CFavg 式中，式中，C为最佳个体的期望复制数量，对于群体规模大小为为最佳个体的期望复制数量，对于群体规模大小为50 100个个体的个个体的 状况，一般取状况，一般取 C=1.2 2。这条要求是为了保证群体中最好的
42、个体能够期望复制这条要求是为了保证群体中最好的个体能够期望复制C倍到新一代群体中。倍到新一代群体中。如下图所示。如下图所示。:/elecfans 电子发烧友 :/bbs.elecfan 电子技术论坛 :/elecfans 电子发烧友 :/bbs.elecfan 电子技术论坛 最小适应度为负时的处理：最小适应度为负时的处理：在遗传算法执行的后期，个别劣质个体的适应度远远小于群体平均适应度及最在遗传算法执行的后期，个别劣质个体的适应度远远小于群体平均适应度及最 大适应度，并且后两者比较接近。这时按上述方法缩放适应度会使低适应度变成大适应度，并且后两者比较接近。这时按上述方法缩放适应度会使低适应度变
43、成 负值，如图所示。这将会给后面的处理过程带来不便，必需避开这种状况的发生，负值，如图所示。这将会给后面的处理过程带来不便，必需避开这种状况的发生，解决这个问题的方法是：把原最小适应度解决这个问题的方法是：把原最小适应度Fmin映射为映射为Fmin=0，并且保持原平均适，并且保持原平均适 应度应度 Favg与新的平均适应度与新的平均适应度 Favg 相等。相等。综上所述，参数综上所述，参数a,b的计算方法如下：的计算方法如下：(1)计算适应度非负判别式：计算适应度非负判别式：Fmin C Favg-FmaxC-1 若不等式满足，则执行若不等式满足，则执行(2)，否则执行否则执行(3)。(2)正
44、常状况下的缩放：正常状况下的缩放：C-1 a =Fmax-FavgFavgFmax-C Favg b =Fmax-FavgFavg(3)负适应度时的缩放：负适应度时的缩放：a =FavgFavg-Fmin b =Favg FminFavg-Fmin .乘乘乘乘幂幂幂幂尺度尺度尺度尺度变换变换变换变换 乘乘乘乘幂幂幂幂尺度尺度尺度尺度变换变换变换变换的公式的公式的公式的公式为为为为：F=Fk F=Fk 即新的适即新的适即新的适即新的适应应应应度是原有适度是原有适度是原有适度是原有适应应应应度的某个指定乘度的某个指定乘度的某个指定乘度的某个指定乘幂幂幂幂。幂幂幂幂指数指数指数指数k k与所求解的与
45、所求解的与所求解的与所求解的问题问题问题问题有关，有关，有关，有关，并且在算法的并且在算法的并且在算法的并且在算法的执执执执行行行行过过过过程中程中程中程中须须须须要不断要不断要不断要不断对对对对其其其其进进进进行修正才能使尺度行修正才能使尺度行修正才能使尺度行修正才能使尺度变换满变换满变换满变换满足确定的伸足确定的伸足确定的伸足确定的伸 缩缩缩缩要求。要求。要求。要求。.指数尺度指数尺度指数尺度指数尺度变换变换变换变换 指数尺度指数尺度指数尺度指数尺度变换变换变换变换的公式的公式的公式的公式为为为为：F Fexp(-exp(-F)F)即新的适即新的适即新的适即新的适应应应应度是原有适度是原有
46、适度是原有适度是原有适应应应应度的某个指数。式中系数度的某个指数。式中系数度的某个指数。式中系数度的某个指数。式中系数 确定了确定了确定了确定了选择选择选择选择的的的的强强强强制性，制性，制性，制性，越小，原有适越小，原有适越小，原有适越小，原有适应应应应度度度度较较较较高的个体的新适高的个体的新适高的个体的新适高的个体的新适应应应应度就越与其他个体的新适度就越与其他个体的新适度就越与其他个体的新适度就越与其他个体的新适应应应应度相差度相差度相差度相差较较较较 大，亦即越增加了大，亦即越增加了大，亦即越增加了大，亦即越增加了选择该选择该选择该选择该个体的个体的个体的个体的强强强强制性。制性。制
47、性。制性。:/elecfans 电子发烧友 :/bbs.elecfan 电子技术论坛4.2.3 4.2.3 约束条件的处理方法约束条件的处理方法约束条件的处理方法约束条件的处理方法 实际应用中的优化问题一般都含有确定的约束条件，它们的描述形式各种各样。实际应用中的优化问题一般都含有确定的约束条件，它们的描述形式各种各样。实际应用中的优化问题一般都含有确定的约束条件，它们的描述形式各种各样。实际应用中的优化问题一般都含有确定的约束条件，它们的描述形式各种各样。在遗传算法的应用中，必需对这些约束条件进行处理，而目前还未找到一种能够在遗传算法的应用中，必需对这些约束条件进行处理，而目前还未找到一种能
48、够在遗传算法的应用中，必需对这些约束条件进行处理，而目前还未找到一种能够在遗传算法的应用中，必需对这些约束条件进行处理，而目前还未找到一种能够 处理各种约束条件的一般化方法。所以对约束条件进行处理时，只能是针对具体处理各种约束条件的一般化方法。所以对约束条件进行处理时，只能是针对具体处理各种约束条件的一般化方法。所以对约束条件进行处理时，只能是针对具体处理各种约束条件的一般化方法。所以对约束条件进行处理时，只能是针对具体 应用问题及约束条件的特征，再考虑遗传算法中遗传算子的运行实力，选用不同应用问题及约束条件的特征，再考虑遗传算法中遗传算子的运行实力，选用不同应用问题及约束条件的特征，再考虑遗
49、传算法中遗传算子的运行实力，选用不同应用问题及约束条件的特征，再考虑遗传算法中遗传算子的运行实力，选用不同 的处理方法。的处理方法。的处理方法。的处理方法。在构造遗传算法时，处理约束条件的常用方法主要有如下三种：在构造遗传算法时，处理约束条件的常用方法主要有如下三种：在构造遗传算法时，处理约束条件的常用方法主要有如下三种：在构造遗传算法时，处理约束条件的常用方法主要有如下三种：搜寻空间限定法搜寻空间限定法搜寻空间限定法搜寻空间限定法 罚函数法罚函数法罚函数法罚函数法 可行解变换法可行解变换法可行解变换法可行解变换法 (1)(1)搜寻空间限定法搜寻空间限定法搜寻空间限定法搜寻空间限定法 基本思想
50、基本思想基本思想基本思想 对遗传算法的搜寻空间的大小加以限制，使得搜寻空间中表示一个个体的点与解空间中表示一个可行解的点对遗传算法的搜寻空间的大小加以限制，使得搜寻空间中表示一个个体的点与解空间中表示一个可行解的点对遗传算法的搜寻空间的大小加以限制，使得搜寻空间中表示一个个体的点与解空间中表示一个可行解的点对遗传算法的搜寻空间的大小加以限制，使得搜寻空间中表示一个个体的点与解空间中表示一个可行解的点有一一对应的关系。此时的搜寻空间与解空间的对应关系如图所示。有一一对应的关系。此时的搜寻空间与解空间的对应关系如图所示。有一一对应的关系。此时的搜寻空间与解空间的对应关系如图所示。有一一对应的关系。