《第四讲 软计算方法精选文档.ppt》由会员分享，可在线阅读，更多相关《第四讲 软计算方法精选文档.ppt（40页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四讲 软计算方法本讲稿第一页，共四十页本讲稿第二页，共四十页本讲稿第三页，共四十页本讲稿第四页，共四十页本讲稿第五页，共四十页本讲稿第六页，共四十页本讲稿第七页，共四十页本讲稿第八页，共四十页4.1 4.1 编码方法编码方法n n编码是应用遗传算法要解决的首要问题编码是应用遗传算法要解决的首要问题编码是应用遗传算法要解决的首要问题编码是应用遗传算法要解决的首要问题,也是设计遗传算也是设计遗传算也是设计遗传算也是设计遗传算法的关键法的关键法的关键法的关键.n n编码方法除了决定个体的染色体排列形式以外编码方法除了决定个体的染色体排列形式以外编码方法除了决定个体的染色体排列形式以外编码方法除了决
2、定个体的染色体排列形式以外,它还决它还决它还决它还决定了个体从搜索空间的基因型转换到解空间的表现型时的定了个体从搜索空间的基因型转换到解空间的表现型时的定了个体从搜索空间的基因型转换到解空间的表现型时的定了个体从搜索空间的基因型转换到解空间的表现型时的解码方法解码方法解码方法解码方法.n n编码方法也影响到交叉算子、变异算子等遗传算子编码方法也影响到交叉算子、变异算子等遗传算子的运算方法的运算方法因此，因此，因此，因此，编码方法在很大程度上决定了如何进行群体编码方法在很大程度上决定了如何进行群体编码方法在很大程度上决定了如何进行群体编码方法在很大程度上决定了如何进行群体的遗传进化运算以及遗传进
3、化运算效率。的遗传进化运算以及遗传进化运算效率。本讲稿第九页，共四十页n n迄今为止，人们已经提出了很多种不同的编码方法，这些迄今为止，人们已经提出了很多种不同的编码方法，这些迄今为止，人们已经提出了很多种不同的编码方法，这些迄今为止，人们已经提出了很多种不同的编码方法，这些编码方法可以分为三大类：编码方法可以分为三大类：编码方法可以分为三大类：编码方法可以分为三大类：二进制编码方法二进制编码方法二进制编码方法二进制编码方法 浮点数编码方法浮点数编码方法 符号编码方法符号编码方法符号编码方法符号编码方法本讲稿第十页，共四十页二进制编码方法二进制编码方法n n二进制编码方法是遗传算法中最常用的一
4、种编码方法，二进制编码方法是遗传算法中最常用的一种编码方法，二进制编码方法是遗传算法中最常用的一种编码方法，二进制编码方法是遗传算法中最常用的一种编码方法，n n它使用的编码符号集为它使用的编码符号集为它使用的编码符号集为它使用的编码符号集为0000，1111，n n它所构成的个体基因型是一个二进制编码符号串。它所构成的个体基因型是一个二进制编码符号串。它所构成的个体基因型是一个二进制编码符号串。它所构成的个体基因型是一个二进制编码符号串。n n二进制编码符号串的长度与问题要求的求解精度有关。二进制编码符号串的长度与问题要求的求解精度有关。二进制编码符号串的长度与问题要求的求解精度有关。二进制
5、编码符号串的长度与问题要求的求解精度有关。n n假设一参数的取值范围是假设一参数的取值范围是假设一参数的取值范围是假设一参数的取值范围是 我们用长度为我们用长度为我们用长度为我们用长度为 的二进制表示该参数的二进制表示该参数的二进制表示该参数的二进制表示该参数 本讲稿第十一页，共四十页二进制编码的精度为二进制编码的精度为本讲稿第十二页，共四十页本讲稿第十三页，共四十页二进制编码方法的优点：二进制编码方法的优点：n n编码、解码操作简单可行n n交叉、变异等遗传操作便于实现交叉、变异等遗传操作便于实现n n符合最小字符集编码原则符合最小字符集编码原则n n便于利用模式定理对算法进行理论分析便于利
6、用模式定理对算法进行理论分析本讲稿第十四页，共四十页浮点数编码方法浮点数编码方法对于一些多维、高精度要求的连续函数优化问题，使用二进制编码对于一些多维、高精度要求的连续函数优化问题，使用二进制编码对于一些多维、高精度要求的连续函数优化问题，使用二进制编码对于一些多维、高精度要求的连续函数优化问题，使用二进制编码来表示个体时会有一些不利之处：来表示个体时会有一些不利之处：来表示个体时会有一些不利之处：来表示个体时会有一些不利之处：(1)(1)(1)(1)使用二进制编码存在着连续函数离散化时的映射误差使用二进制编码存在着连续函数离散化时的映射误差使用二进制编码存在着连续函数离散化时的映射误差使用二
7、进制编码存在着连续函数离散化时的映射误差(2)(2)(2)(2)个体编码串较短时，可能达不到精度要求；而个体编个体编码串较短时，可能达不到精度要求；而个体编个体编码串较短时，可能达不到精度要求；而个体编个体编码串较短时，可能达不到精度要求；而个体编码串的长度较长时，虽然能提高编码精度，但却会使码串的长度较长时，虽然能提高编码精度，但却会使码串的长度较长时，虽然能提高编码精度，但却会使码串的长度较长时，虽然能提高编码精度，但却会使遗传算法的搜索空间急剧扩大遗传算法的搜索空间急剧扩大遗传算法的搜索空间急剧扩大遗传算法的搜索空间急剧扩大 本讲稿第十五页，共四十页例例例例:使用二进制方法来处理一个含有
8、使用二进制方法来处理一个含有使用二进制方法来处理一个含有使用二进制方法来处理一个含有100100100100个决策变量的优化，每个决策变量的优化，每个决策变量的优化，每个决策变量的优化，每个决策变量的取值范围是个决策变量的取值范围是个决策变量的取值范围是个决策变量的取值范围是-250,250,-250,250,-250,250,-250,250,要求精度是小数点后面要求精度是小数点后面要求精度是小数点后面要求精度是小数点后面五位，即五位，即五位，即五位，即为为为为0.00001,0.00001,0.00001,0.00001,则为则为则为则为26262626这样每个个体必须用这样每个个体必须用
9、这样每个个体必须用这样每个个体必须用2600260026002600位长的二进制编码符号串来表示。位长的二进制编码符号串来表示。位长的二进制编码符号串来表示。位长的二进制编码符号串来表示。相应的搜索空间大约是相应的搜索空间大约是相应的搜索空间大约是相应的搜索空间大约是本讲稿第十六页，共四十页n n为改变二进制编码方法的缺点，人们提出了浮点数编码方法为改变二进制编码方法的缺点，人们提出了浮点数编码方法为改变二进制编码方法的缺点，人们提出了浮点数编码方法为改变二进制编码方法的缺点，人们提出了浮点数编码方法浮点数编码方法指个体的每个基因值用某一范围内的一个浮点浮点数编码方法指个体的每个基因值用某一范
10、围内的一个浮点浮点数编码方法指个体的每个基因值用某一范围内的一个浮点浮点数编码方法指个体的每个基因值用某一范围内的一个浮点数来表示。个体的编码长度等于其决策变量的个数数来表示。个体的编码长度等于其决策变量的个数数来表示。个体的编码长度等于其决策变量的个数数来表示。个体的编码长度等于其决策变量的个数n n浮点数编码方法使用的是决策变量的真实值，所以该方法也称为浮点数编码方法使用的是决策变量的真实值，所以该方法也称为浮点数编码方法使用的是决策变量的真实值，所以该方法也称为浮点数编码方法使用的是决策变量的真实值，所以该方法也称为真值编码方法。真值编码方法。真值编码方法。真值编码方法。例设一个优化问题
11、含有五个变量，每个变量都有其例设一个优化问题含有五个变量，每个变量都有其例设一个优化问题含有五个变量，每个变量都有其例设一个优化问题含有五个变量，每个变量都有其对应的上下限对应的上下限对应的上下限对应的上下限就表示一个个体的基因型，对应的表现型为就表示一个个体的基因型，对应的表现型为就表示一个个体的基因型，对应的表现型为就表示一个个体的基因型，对应的表现型为 X=5.80,6.90,3.50,3.80,5.00X=5.80,6.90,3.50,3.80,5.00X=5.80,6.90,3.50,3.80,5.00X=5.80,6.90,3.50,3.80,5.00 本讲稿第十七页，共四十页在浮
12、点数编码的算法中的注意要点在浮点数编码的算法中的注意要点在浮点数编码的算法中的注意要点在浮点数编码的算法中的注意要点(1)(1)(1)(1)必须保证给定的基因值在给定的范围内必须保证给定的基因值在给定的范围内必须保证给定的基因值在给定的范围内必须保证给定的基因值在给定的范围内(2)GA(2)GA(2)GA(2)GA算法中所使用的交叉和变异算子必须使运算结果在所给范围算法中所使用的交叉和变异算子必须使运算结果在所给范围算法中所使用的交叉和变异算子必须使运算结果在所给范围算法中所使用的交叉和变异算子必须使运算结果在所给范围(3)(3)(3)(3)当用多个字节来表示一个基因时，交叉运算必须在两个基因
13、的分界当用多个字节来表示一个基因时，交叉运算必须在两个基因的分界当用多个字节来表示一个基因时，交叉运算必须在两个基因的分界当用多个字节来表示一个基因时，交叉运算必须在两个基因的分界字节处进行，而不能在某个基因的中间字节分隔处进行。字节处进行，而不能在某个基因的中间字节分隔处进行。字节处进行，而不能在某个基因的中间字节分隔处进行。字节处进行，而不能在某个基因的中间字节分隔处进行。浮点数编码方法的优点：浮点数编码方法的优点：浮点数编码方法的优点：浮点数编码方法的优点：(1)(1)(1)(1)适合于在中表示范围较大的数适合于在中表示范围较大的数适合于在中表示范围较大的数适合于在中表示范围较大的数(2
14、)(2)(2)(2)适合于精度要求较高的适合于精度要求较高的适合于精度要求较高的适合于精度要求较高的(3)(3)(3)(3)便于较大空间的遗传搜索便于较大空间的遗传搜索便于较大空间的遗传搜索便于较大空间的遗传搜索(4)(4)(4)(4)改善了的计算的复杂性，提高了运算效率改善了的计算的复杂性，提高了运算效率改善了的计算的复杂性，提高了运算效率改善了的计算的复杂性，提高了运算效率(5)(5)(5)(5)便于与经典的优化算法的使用便于与经典的优化算法的使用便于与经典的优化算法的使用便于与经典的优化算法的使用本讲稿第十八页，共四十页符号编码方法符号编码方法n n指个体染色体编码串中基因值取自一个无数
15、值含义，而只有代码含义指个体染色体编码串中基因值取自一个无数值含义，而只有代码含义指个体染色体编码串中基因值取自一个无数值含义，而只有代码含义指个体染色体编码串中基因值取自一个无数值含义，而只有代码含义的符号集。的符号集。的符号集。的符号集。n n可以是一个字母表可以是一个字母表可以是一个字母表可以是一个字母表A,B,C,A,B,C,A,B,C,A,B,C,n n也可以是一个数字序号集也可以是一个数字序号集也可以是一个数字序号集也可以是一个数字序号集1,2,3,1,2,3,1,2,3,1,2,3,n n还可以是一个代码表还可以是一个代码表还可以是一个代码表还可以是一个代码表A1,A2,A3,A
16、1,A2,A3,A1,A2,A3,A1,A2,A3,如问题，假设有如问题，假设有如问题，假设有如问题，假设有n n n n个城市个城市个城市个城市C1 C2 CnC1 C2 CnC1 C2 CnC1 C2 Cn，将各个城市的代码按，将各个城市的代码按，将各个城市的代码按，将各个城市的代码按其被访问的顺序连接起来，可以构成一条旅行路线的个体其被访问的顺序连接起来，可以构成一条旅行路线的个体其被访问的顺序连接起来，可以构成一条旅行路线的个体其被访问的顺序连接起来，可以构成一条旅行路线的个体，nnnn本讲稿第十九页，共四十页4.24.2适应度函数适应度函数n n生物学家使用适应度这个术语来度量某个物
17、种对于其生存环境的生物学家使用适应度这个术语来度量某个物种对于其生存环境的生物学家使用适应度这个术语来度量某个物种对于其生存环境的生物学家使用适应度这个术语来度量某个物种对于其生存环境的适应程度，适应度高的物种有更多的繁殖机会，而对环境适应程适应程度，适应度高的物种有更多的繁殖机会，而对环境适应程适应程度，适应度高的物种有更多的繁殖机会，而对环境适应程适应程度，适应度高的物种有更多的繁殖机会，而对环境适应程度较低的物种，其繁殖机会就较低，甚至回逐步灭绝。度较低的物种，其繁殖机会就较低，甚至回逐步灭绝。度较低的物种，其繁殖机会就较低，甚至回逐步灭绝。度较低的物种，其繁殖机会就较低，甚至回逐步灭绝
18、。n n使用这个概念来度量群体中各个个体在优化计算中有可使用这个概念来度量群体中各个个体在优化计算中有可使用这个概念来度量群体中各个个体在优化计算中有可使用这个概念来度量群体中各个个体在优化计算中有可能达到或接近于或有助于找到最优解的优良程度。能达到或接近于或有助于找到最优解的优良程度。能达到或接近于或有助于找到最优解的优良程度。能达到或接近于或有助于找到最优解的优良程度。n n度量个体适应度的函数称为适应度函数度量个体适应度的函数称为适应度函数度量个体适应度的函数称为适应度函数度量个体适应度的函数称为适应度函数本讲稿第二十页，共四十页n n目标函数与适应度函数转换关系解空间目标函数学值f(x
19、)搜索空间适应度F(x)本讲稿第二十一页，共四十页n n适应度尺度变换实践表明，使用上面的转化关系来计算个体的适应度时，有些实践表明，使用上面的转化关系来计算个体的适应度时，有些实践表明，使用上面的转化关系来计算个体的适应度时，有些实践表明，使用上面的转化关系来计算个体的适应度时，有些GAGAGAGA会收敛得很快，也有些收敛得很慢。所以，如何确定适应度对会收敛得很快，也有些收敛得很慢。所以，如何确定适应度对会收敛得很快，也有些收敛得很慢。所以，如何确定适应度对会收敛得很快，也有些收敛得很慢。所以，如何确定适应度对的性能有较大影响。的性能有较大影响。的性能有较大影响。的性能有较大影响。在运行初期
20、在运行初期在运行初期在运行初期群体中可能会有少数几个各个的适应度相对于其他个体来说非常高。群体中可能会有少数几个各个的适应度相对于其他个体来说非常高。群体中可能会有少数几个各个的适应度相对于其他个体来说非常高。群体中可能会有少数几个各个的适应度相对于其他个体来说非常高。如果按照常用的比例选择算子来确定个体的遗传数量，如果按照常用的比例选择算子来确定个体的遗传数量，如果按照常用的比例选择算子来确定个体的遗传数量，如果按照常用的比例选择算子来确定个体的遗传数量，则这几个相则这几个相则这几个相则这几个相对较好的个体将在下一代群体中占有较高比例对较好的个体将在下一代群体中占有较高比例对较好的个体将在下
21、一代群体中占有较高比例对较好的个体将在下一代群体中占有较高比例，在极端情况，在极端情况，在极端情况，在极端情况下或群体规模较小时，新的群体甚至完全由这少数几个个体下或群体规模较小时，新的群体甚至完全由这少数几个个体下或群体规模较小时，新的群体甚至完全由这少数几个个体下或群体规模较小时，新的群体甚至完全由这少数几个个体组成。这时产生新个体作用较大的交叉算子不起作用。这样组成。这时产生新个体作用较大的交叉算子不起作用。这样组成。这时产生新个体作用较大的交叉算子不起作用。这样组成。这时产生新个体作用较大的交叉算子不起作用。这样就会使就会使就会使就会使群体的多样性降低。群体的多样性降低。群体的多样性降
22、低。群体的多样性降低。容易导致容易导致容易导致容易导致GAGAGAGA过早收敛。使过早收敛。使过早收敛。使过早收敛。使GAGAGAGA所得到的所得到的所得到的所得到的解停留在某一局部最优点上。解停留在某一局部最优点上。解停留在某一局部最优点上。解停留在某一局部最优点上。本讲稿第二十二页，共四十页结论：结论：我们希望在遗传算法运行的初期阶段，算法能对一些适应我们希望在遗传算法运行的初期阶段，算法能对一些适应度较高的个体进行控制，降低其适应度与其他个体适应度度较高的个体进行控制，降低其适应度与其他个体适应度之间的差异程度，从而限制其复制的数量，以维护群体的之间的差异程度，从而限制其复制的数量，以维
23、护群体的多样性。多样性。本讲稿第二十三页，共四十页在运行后期在运行后期在运行后期在运行后期群体中所有个体的平均适应度可能会接近群体中最佳个体的群体中所有个体的平均适应度可能会接近群体中最佳个体的群体中所有个体的平均适应度可能会接近群体中最佳个体的群体中所有个体的平均适应度可能会接近群体中最佳个体的适应度。即大部分个体的适应度和最佳个体的适应度差异不大。适应度。即大部分个体的适应度和最佳个体的适应度差异不大。适应度。即大部分个体的适应度和最佳个体的适应度差异不大。适应度。即大部分个体的适应度和最佳个体的适应度差异不大。它们之间无竞争力，都会以相接近的概率被遗传到下一代。它们之间无竞争力，都会以相
24、接近的概率被遗传到下一代。它们之间无竞争力，都会以相接近的概率被遗传到下一代。它们之间无竞争力，都会以相接近的概率被遗传到下一代。从从从从而使进化过程无竞争可言。只是一种随机的选择过程而使进化过程无竞争可言。只是一种随机的选择过程而使进化过程无竞争可言。只是一种随机的选择过程而使进化过程无竞争可言。只是一种随机的选择过程。这就导致无法。这就导致无法。这就导致无法。这就导致无法对某些重点区域进行重点搜索。从而影响对某些重点区域进行重点搜索。从而影响对某些重点区域进行重点搜索。从而影响对某些重点区域进行重点搜索。从而影响GAGAGAGA的效率。的效率。的效率。的效率。结论：我们希望在后期能够对个体
25、的适应度进行适当的放大，结论：我们希望在后期能够对个体的适应度进行适当的放大，结论：我们希望在后期能够对个体的适应度进行适当的放大，结论：我们希望在后期能够对个体的适应度进行适当的放大，扩大最佳个体适应度与其他个体适应度之间的差异程度，以扩大最佳个体适应度与其他个体适应度之间的差异程度，以扩大最佳个体适应度与其他个体适应度之间的差异程度，以扩大最佳个体适应度与其他个体适应度之间的差异程度，以提高个体之间的竞争性。提高个体之间的竞争性。提高个体之间的竞争性。提高个体之间的竞争性。本讲稿第二十四页，共四十页n n适应度尺度变换适应度尺度变换适应度尺度变换适应度尺度变换(fitness Scalin
26、g)(fitness Scaling)方法方法方法方法在在在在GAGA运行的不同阶段，运行的不同阶段，运行的不同阶段，运行的不同阶段，需要对个体的适应度进行适当的扩需要对个体的适应度进行适当的扩需要对个体的适应度进行适当的扩需要对个体的适应度进行适当的扩大和缩小。这种对个体适应度所做的扩大和缩小变换称为适大和缩小。这种对个体适应度所做的扩大和缩小变换称为适大和缩小。这种对个体适应度所做的扩大和缩小变换称为适大和缩小。这种对个体适应度所做的扩大和缩小变换称为适应度尺度变换。应度尺度变换。应度尺度变换。应度尺度变换。目前变换有三种：目前变换有三种：目前变换有三种：目前变换有三种：(1)(1)(1)
27、(1)线性尺度变换线性尺度变换线性尺度变换线性尺度变换 (2)(2)(2)(2)幂尺度变换幂尺度变换幂尺度变换幂尺度变换 (3)(3)(3)(3)指数尺度变换指数尺度变换指数尺度变换指数尺度变换本讲稿第二十五页，共四十页n n线性尺度变换本讲稿第二十六页，共四十页n n系数系数a,ba,b直接影响到这个尺度变换的大小，对其选取直接影响到这个尺度变换的大小，对其选取直接影响到这个尺度变换的大小，对其选取直接影响到这个尺度变换的大小，对其选取有一定的要求，一般希望他们满足如下条件：有一定的要求，一般希望他们满足如下条件：有一定的要求，一般希望他们满足如下条件：有一定的要求，一般希望他们满足如下条件
28、：(1)(1)(1)(1)尺度变换后全部个体的新适应度的平均值要等于其尺度变换后全部个体的新适应度的平均值要等于其尺度变换后全部个体的新适应度的平均值要等于其尺度变换后全部个体的新适应度的平均值要等于其原适应度的平均值原适应度的平均值原适应度的平均值原适应度的平均值 (2)(2)(2)(2)尺度变换后群体中新的适应度最大值要等于原平尺度变换后群体中新的适应度最大值要等于原平均适应度的指定倍数均适应度的指定倍数 为最佳个体的期望复制数量，对于群体规模为为最佳个体的期望复制数量，对于群体规模为50-10050-10050-10050-100的个体，一般取的个体，一般取的个体，一般取的个体，一般取c
29、=1.2c=1.2c=1.2c=1.2.本讲稿第二十七页，共四十页n n在搜索过程前期在搜索过程前期在搜索过程前期在搜索过程前期,使用线性尺度变换时，群体中少数几个优良使用线性尺度变换时，群体中少数几个优良使用线性尺度变换时，群体中少数几个优良使用线性尺度变换时，群体中少数几个优良个体的适应度按比例缩小，同时几个较差个体的适应度也按个体的适应度按比例缩小，同时几个较差个体的适应度也按个体的适应度按比例缩小，同时几个较差个体的适应度也按个体的适应度按比例缩小，同时几个较差个体的适应度也按比例扩大。比例扩大。比例扩大。比例扩大。n n在搜索过程后期，随着个体适应度从总体上的不断改进，群体在搜索过程
30、后期，随着个体适应度从总体上的不断改进，群体在搜索过程后期，随着个体适应度从总体上的不断改进，群体在搜索过程后期，随着个体适应度从总体上的不断改进，群体中个体的最大适应度和全部个体的平均适应度较接近，而少数中个体的最大适应度和全部个体的平均适应度较接近，而少数中个体的最大适应度和全部个体的平均适应度较接近，而少数中个体的最大适应度和全部个体的平均适应度较接近，而少数几个较差的个体的适应度远远低于最大适应度，这时要维持几个较差的个体的适应度远远低于最大适应度，这时要维持几个较差的个体的适应度远远低于最大适应度，这时要维持几个较差的个体的适应度远远低于最大适应度，这时要维持 本讲稿第二十八页，共四
31、十页 将会使较差个体的适应度变换为负值。将会给后面的处理带来不变。解决这一问题的办法是：使变换满足如下条件本讲稿第二十九页，共四十页本讲稿第三十页，共四十页n na,b的计算方法如下:本讲稿第三十一页，共四十页4.3选择算子常用的选择算子是常用的选择算子是常用的选择算子是常用的选择算子是SGASGASGASGA中的中的中的中的比例选择算子比例选择算子比例选择算子比例选择算子,但对各种各样的问题但对各种各样的问题但对各种各样的问题但对各种各样的问题,比例选择算子并不一定是最合适的比例选择算子并不一定是最合适的比例选择算子并不一定是最合适的比例选择算子并不一定是最合适的.所以人们提出了其他一些选所
32、以人们提出了其他一些选所以人们提出了其他一些选所以人们提出了其他一些选择算子择算子择算子择算子.下面介绍几种常用选择算子的操作方法下面介绍几种常用选择算子的操作方法下面介绍几种常用选择算子的操作方法下面介绍几种常用选择算子的操作方法.(1)(1)(1)(1)比例选择比例选择比例选择比例选择(proportional Model)(proportional Model)(proportional Model)(proportional Model)基本思想基本思想基本思想基本思想:各个个体被选中的概率与其适应度大小成正比各个个体被选中的概率与其适应度大小成正比各个个体被选中的概率与其适应度大小成
33、正比各个个体被选中的概率与其适应度大小成正比.由于由于由于由于随机操作的原因随机操作的原因随机操作的原因随机操作的原因,这种选择方法的误差较大这种选择方法的误差较大这种选择方法的误差较大这种选择方法的误差较大,有时甚至连适应度有时甚至连适应度有时甚至连适应度有时甚至连适应度较高的个体选择不上较高的个体选择不上较高的个体选择不上较高的个体选择不上.本讲稿第三十二页，共四十页(2)(2)(2)(2)最优保存策略（最优保存策略（最优保存策略（最优保存策略（Elitist Model)(e-GA)Elitist Model)(e-GA)Elitist Model)(e-GA)Elitist Model
34、)(e-GA)在在在在GAGAGAGA的运行过程中的运行过程中的运行过程中的运行过程中,通过对个体进行交叉、变异等遗传操作而不断产通过对个体进行交叉、变异等遗传操作而不断产通过对个体进行交叉、变异等遗传操作而不断产通过对个体进行交叉、变异等遗传操作而不断产生新的个体。虽然随着群体的进化过程而不断产生出越来越多的优良生新的个体。虽然随着群体的进化过程而不断产生出越来越多的优良生新的个体。虽然随着群体的进化过程而不断产生出越来越多的优良生新的个体。虽然随着群体的进化过程而不断产生出越来越多的优良个体，但由于选择、交叉、变异等遗传操作的随机性，他们也可能破个体，但由于选择、交叉、变异等遗传操作的随机
35、性，他们也可能破个体，但由于选择、交叉、变异等遗传操作的随机性，他们也可能破个体，但由于选择、交叉、变异等遗传操作的随机性，他们也可能破坏掉当前群体中适应度最好的个体。这样可能会降低群体的平均适应坏掉当前群体中适应度最好的个体。这样可能会降低群体的平均适应坏掉当前群体中适应度最好的个体。这样可能会降低群体的平均适应坏掉当前群体中适应度最好的个体。这样可能会降低群体的平均适应度，对遗传算法的效率产生不良的影响。度，对遗传算法的效率产生不良的影响。度，对遗传算法的效率产生不良的影响。度，对遗传算法的效率产生不良的影响。所以我们希望适应度最好的个体要尽可能地保留到下一代群体中。所以我们希望适应度最好
36、的个体要尽可能地保留到下一代群体中。所以我们希望适应度最好的个体要尽可能地保留到下一代群体中。所以我们希望适应度最好的个体要尽可能地保留到下一代群体中。方法：方法：方法：方法：如果下一代群体的最佳个体适应值小于当前群体最佳个体的适应值，如果下一代群体的最佳个体适应值小于当前群体最佳个体的适应值，如果下一代群体的最佳个体适应值小于当前群体最佳个体的适应值，如果下一代群体的最佳个体适应值小于当前群体最佳个体的适应值，则将当前群体最佳个体或者适应值大于下一代群体中最佳个体适应则将当前群体最佳个体或者适应值大于下一代群体中最佳个体适应则将当前群体最佳个体或者适应值大于下一代群体中最佳个体适应则将当前群
37、体最佳个体或者适应值大于下一代群体中最佳个体适应值的多个个体直接复制到下一代，即替代或替代最差的下一代群体值的多个个体直接复制到下一代，即替代或替代最差的下一代群体值的多个个体直接复制到下一代，即替代或替代最差的下一代群体值的多个个体直接复制到下一代，即替代或替代最差的下一代群体中的相应数量的个体。中的相应数量的个体。中的相应数量的个体。中的相应数量的个体。本讲稿第三十三页，共四十页本讲稿第三十四页，共四十页4.4 4.4 交叉算子交叉算子n n在生物的自然进化过程中，两个同源染色体通过交配而重组，形成在生物的自然进化过程中，两个同源染色体通过交配而重组，形成在生物的自然进化过程中，两个同源染
38、色体通过交配而重组，形成在生物的自然进化过程中，两个同源染色体通过交配而重组，形成新的染色体，从而产生新的个体。新的染色体，从而产生新的个体。新的染色体，从而产生新的个体。新的染色体，从而产生新的个体。n nGAGAGAGA中的所谓交叉算子是指对两个相互配对的染色体按某种方式相互交换中的所谓交叉算子是指对两个相互配对的染色体按某种方式相互交换中的所谓交叉算子是指对两个相互配对的染色体按某种方式相互交换中的所谓交叉算子是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成新的个体其部分基因，从而形成新的个体其部分基因，从而形成新的个体其部分基因，从而形成新的个体n nGAGAGAGA中
39、，在交叉运算之前还必须对群体中的个体进行配对。目前常用的配中，在交叉运算之前还必须对群体中的个体进行配对。目前常用的配中，在交叉运算之前还必须对群体中的个体进行配对。目前常用的配中，在交叉运算之前还必须对群体中的个体进行配对。目前常用的配对策略是随机配对。即将群体中的对策略是随机配对。即将群体中的对策略是随机配对。即将群体中的对策略是随机配对。即将群体中的M M M M个个体以随机的方式组成个个体以随机的方式组成个个体以随机的方式组成个个体以随机的方式组成 对个体组，交叉操作在这些配对个体组中的两个个体之间进行。对个体组，交叉操作在这些配对个体组中的两个个体之间进行。对个体组，交叉操作在这些配
40、对个体组中的两个个体之间进行。对个体组，交叉操作在这些配对个体组中的两个个体之间进行。本讲稿第三十五页，共四十页本讲稿第三十六页，共四十页n n交叉算子的设计和实现与所研究的问题密切相关。一般要求它既交叉算子的设计和实现与所研究的问题密切相关。一般要求它既交叉算子的设计和实现与所研究的问题密切相关。一般要求它既交叉算子的设计和实现与所研究的问题密切相关。一般要求它既不要太多地破坏个体编码串表示优良性状的优良模式，又要能够不要太多地破坏个体编码串表示优良性状的优良模式，又要能够不要太多地破坏个体编码串表示优良性状的优良模式，又要能够不要太多地破坏个体编码串表示优良性状的优良模式，又要能够有效地产
41、生出一些较好的新个体模式。有效地产生出一些较好的新个体模式。有效地产生出一些较好的新个体模式。有效地产生出一些较好的新个体模式。n n交叉算子的设计包含以下两方面的内容交叉算子的设计包含以下两方面的内容交叉算子的设计包含以下两方面的内容交叉算子的设计包含以下两方面的内容(1)(1)(1)(1)如何确定交叉点的位置如何确定交叉点的位置如何确定交叉点的位置如何确定交叉点的位置(2)(2)(2)(2)如何进行部分基因交换如何进行部分基因交换如何进行部分基因交换如何进行部分基因交换n n几种适合于二进制编码个体或浮点数编码个体的交叉算子几种适合于二进制编码个体或浮点数编码个体的交叉算子几种适合于二进制
42、编码个体或浮点数编码个体的交叉算子几种适合于二进制编码个体或浮点数编码个体的交叉算子单点交叉单点交叉单点交叉单点交叉双点交叉与多点交叉双点交叉与多点交叉双点交叉与多点交叉双点交叉与多点交叉均匀交叉均匀交叉均匀交叉均匀交叉算术交叉算术交叉算术交叉算术交叉本讲稿第三十七页，共四十页单点交叉单点交叉单点交叉单点交叉(one-point crossover)(one-point crossover)(one-point crossover)(one-point crossover)个体编码串中只随机设置一个交叉点，然后在该点相互交换两个配对个体编码串中只随机设置一个交叉点，然后在该点相互交换两个配对个
43、体编码串中只随机设置一个交叉点，然后在该点相互交换两个配对个体编码串中只随机设置一个交叉点，然后在该点相互交换两个配对个体的部分染色体。个体的部分染色体。个体的部分染色体。个体的部分染色体。双点交叉与多点交叉双点交叉与多点交叉双点交叉与多点交叉双点交叉与多点交叉(Two-point crossover)(Two-point crossover)(Two-point crossover)(Two-point crossover)(multi-point crossover)(multi-point crossover)(multi-point crossover)(multi-point cro
44、ssover)注意：一般不太使用多点交叉算子，因为它可能破坏一些好注意：一般不太使用多点交叉算子，因为它可能破坏一些好注意：一般不太使用多点交叉算子，因为它可能破坏一些好注意：一般不太使用多点交叉算子，因为它可能破坏一些好的结构。随着交叉点的增多，个体结构被破坏的可能的结构。随着交叉点的增多，个体结构被破坏的可能的结构。随着交叉点的增多，个体结构被破坏的可能的结构。随着交叉点的增多，个体结构被破坏的可能性也逐渐增大，这样可能就很难有效地保护较好的模性也逐渐增大，这样可能就很难有效地保护较好的模性也逐渐增大，这样可能就很难有效地保护较好的模性也逐渐增大，这样可能就很难有效地保护较好的模式，从而影
45、响式，从而影响式，从而影响式，从而影响GAGAGAGA的性能。的性能。的性能。的性能。本讲稿第三十八页，共四十页均匀交叉均匀交叉(uniform crossover)(uniform crossover)(uniform crossover)(uniform crossover)两个配对个体的每一个基因座上的基因都以相同的交叉两个配对个体的每一个基因座上的基因都以相同的交叉概率进行交换，从而形成两个新的个体。概率进行交换，从而形成两个新的个体。本讲稿第三十九页，共四十页算术交叉算术交叉算术交叉算术交叉(Arithmetic crossover)(Arithmetic crossover)是指由两个个体的线性组合而产生出的新个体。算术交是指由两个个体的线性组合而产生出的新个体。算术交叉的操作对象一般是由浮点数编码所表示的个体叉的操作对象一般是由浮点数编码所表示的个体本讲稿第四十页，共四十页