遗传算法-交叉变异

《遗传算法-交叉变异》由会员分享，可在线阅读，更多相关《遗传算法-交叉变异（6页珍藏版）》请在装配图网上搜索。

1、第三部分 遗传算法 课后任务查找资料，学习了解个体编码的方法、交叉的方法和变异的方法。一、个体编码方法1、二进制编码：（1）定义：二进制编码方法是使用二值符号集0,1，它所构成的个 体基因型是一个二进制编码符号串。二进制编码符号串的长度与问题 所要求的求解精度有关。（2）举例：0WxW1023,精度为1,m表示二进制编码的长度。则有建 议性说法：使2m-1 W1000 （跟精度有关）W 2m-1。取m=10则 X:0010101111就可以表示一个个体，它所对应的问题空间的值是 x=175。（3）优缺点优点：符合最小字符集原则，便于用模式定理分析；缺点：连续函数离散化时的映射误差。2、格雷码编

2、码：（1）定义：格雷码编码是其连续的两个整数所对应的编码之间只有 一个码位是不同的，其余码位完全相同。它是二进制编码方法的一种 变形。十进制数015之间的二进制码和相应的格雷码分别编码如下。二进制编码为：0000, 0001, 0010, 001 1, 0100。0101, 0110, 0111, 1000， 1001, 1010, 1011, 1100, 1101, 1110, 1111；格雷码编码为：0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100,1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000。(2

3、) 举例：对于区间0。1023中两个邻近的整数X1=175和X2=176, 若用长度为10位的二进制编码，可表示为X11： 0010101111和X12 0010110000，而使用同样长度的格雷码，它们可分别表示为X21： 0010101111和 X22： 0010101000O(3) 优点：增强了遗传算法的局部搜索能力，便于连续函数的局部 控件搜索。3、符号编码法符号编码法是指个体染色体编码串中的基因值取自一个无数值含 义、而只有代码含义的符号集如A,B,C。符号编码的主要优点是：1) 符合有意义积术块编码原则2) 便于在遗传算法中利用所求解问题的专门知识3) 便于遗传算法与相关近似算法之

4、间的混合使用。但对于使用符号编码方法的遗传算法，一般需要认真设计交叉、 变异等遗传运算的操作方法，以满足问题的各种约束村求，这样才能 提高算法的搜索性能。二、交叉的方法1、单点交叉：单点交叉又称为简单交叉，它是指在个体编码串中只 随机设置一个交叉点，然后在该点相互交换两个配体个体的部分染色 体。如图1父代九01| 101单点交叉.子代1： 011 000 一父代2： 11 000 J丨子代2： 11| 101 JA交罠点图1单点交叉2、两点交叉：两点交叉是指在个体编码串中随机设置了两个交叉点 然后再进行部分基因交换，两点交叉的具体操作过程是 在相互配对 的两个个体编码串中随机设置两个交叉点，交

5、换两个个体在所设定的 两个交叉点之间的部分染色体，图2为两点交叉运算示意图父代仆01| 101| 00110双点交叉.子代011 000 00110父代2: 11| 000 10100子代z 11| 101| 10100t t*十交叉点1交叉点2图2两点交叉3、多点交叉：或称广义交叉，是指在个体编码串中随机设置多个交 叉点，然后进行基因交换，其操作过程与单点交叉和两点交叉相类似3、均匀交叉：也称一致交叉，是指两个配对个体的每个基因座 上的基因都以相同的交叉概率进行交换，从而形成两个新的个体，其 具体运算是通过设置一屏蔽字来确定新个体的各个基因如何由哪一 个父代个体来提供，主要操作过程如下：1）

6、随机产生一个与个体编码串长度等长的屏蔽字W=w1w2Lw1Lw1， 其中L为个体编码串长度。2）由上述规则从A B两个父代个体中产生出两个新的子代个体A、B，若wi = 0则A在第i个基因座上的基因值继承A的对应基因值，B 在第i个基因座上的基因值继承B的对应基因值，若i二1，则A在第i 个基因座上的基因值继承B的对应基因值，B在第i个基因座上的基 因值继承A的对应基因值。4、均匀两点交叉：是指两个配体A、B中随机产生两个交叉点，然 后按随机产生的0、1、2三个整数进行基因交换，从而形成两个新 的个体。当随机数是0时，配体的前面部分交叉;当随机数是1时配体的中间部分交叉;当随机数是2时，配体的

7、后面部分交叉还有其 他的交叉算子，如缩小代理交叉，洗牌交叉等。5、适合浮点数编码的交叉算子浮点数编码方法是指个体的每个基因值用某一范围内的一个浮点 数来表示，个体的编码长度等于其决策变量的个数除上述所述的适 合二进制编码方法的交叉算子可用于浮点数编码方法的交叉操作中 还使用以下主要的交叉算子1）离散交叉：是指在个体之间交换变量的值子个体的每个变量可按 等概率随机地挑选父个体2）算术交叉：是指由两个个体的线性组合而产生出两个新的个体， 算术交叉的操作对象一般是由浮点数编码所表示的个体其定义为 两个向量，染色体的组合:x1=人1x1+人2x2；x2二人1x2+人2x1其中人1、人2 称为乘子,特殊

8、情况有当人1二人2二0.5时,Davis称其为平均交叉Schwefel称其为中间交叉intermediate crossover把乘子作为区间 -d ， 1 + d上的随机数时，Muhlenbein 和 Schlierkamp - Voosen 称 其为扩展中间交叉。3）启发式交叉：如果父个体1和父个体2而父个体1有较好的适应 度，则如下函数产生子个体:子个体二父个体2 + Radio 3 （父个体1 -父个体2 )其中Radio指定子代离较好适应度的父代有多远，其缺省值为1. 2三、变异的方法1) 均有变异均有变异(Uniform Mutation)操作是指分别用符合某一范围内均 匀分布的随

9、即数，以某一较小的概率来替换个体编码串 中各个基因座上的原有基因值。均匀变异的具体操作过程是：(1) 依次指定个体编码串中的每各个基因座为变异点；(2) 对每一个变异点，以概率pm从对应基因的取值范围内取一随机 数来来代替原有基因值。2) 边界变异算子边界变异算子(Boundary Mutation)是均匀变异操作的一个变形 遗传算法。在进行边界变异操作时，随机地取基因座的二个对应边界 基因之一取代替原有基因值。3) 非均匀变异算子非均匀变异的具体操作过程于均匀那变异相似，但它重点搜索原 个体附近的微小区域。在进行由X=X1X2XkXI向X=X1X2Xk XI的非均 匀变异操作时,若变异点Xk

10、处的基因值取值范围为Ukmin,Ukmax, 则新的基因Xk由下式确定：|Xk4-A(t? Uma!(- Xk) if random (0,1 )=0Xk = |Xk-A(t, Xk-uL)5ifrandom0Jr式中，(t, y),( y表示Ukmax- Xk和Xk- Ukmin)表示0, y范围内符 合非均匀分布的一个随机数,要求随着进化代数t的增加,& y)接 近于0的概率也逐渐增加。例如，(t, y)可按下式定义： (t, y)=y.(1-r(1- t/T)b)式中r为0,1 范围内符合均匀分布的一个随机数,T时最大进化代 数,b时一个系统参数，它决定了随机数扰动对进化代数t的依赖程 度。4) 高斯变异算子高斯变异(Gaussian Mutation)是改进遗传算法对重点搜索区域大 局部搜索性能的另一种变异操作方法。所谓高斯变异操作是指进行变 异操作时，用符合均值为m、方差为s2的正态分布的一个随机数来 替换原有基因值。由正态分布的特性可知，高斯变异也时重点搜索原 个体附近大某个局部区域。高斯变异的具体操作过程于均匀变异相 似。