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