遗传算法-交叉变异

《遗传算法-交叉变异》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、雷码编码：（1）定义：格雷码编码是其连续的两个整数所对应的编码之间只有一个码位是不同的，其余码位完全相同。它是二进制编码方法的一种变形。十进制数0—15之间的二进制码和相应的格雷码分别编码如下。二进制编码为：0000，0001，0010，0011，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）举例：对于区间[0。1023]

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

4、号编码方法的遗传算法，一般需要认真设计交叉、变异等遗传运算的操作方法，以满足问题的各种约束村求，这样才能提高算法的搜索性能。二、交叉的方法1、单点交叉：单点交叉又称为简单交叉，它是指在个体编码串中只随机设置一个交叉点，然后在该点相互交换两个配体个体的部分染色体。如图1图1单点交叉2、两点交叉：两点交叉是指在个体编码串中随机设置了两个交叉点然后再进行部分基因交换，两点交叉的具体操作过程是:在相互配对的两个个体编码串中随机设置两个交叉点，交换两个个体在所设定的两个交叉点之间的部分染色体，图2为两点交叉运算示意图图2两点交叉3、多点交叉：或称广义交叉，是指在个体编码串中随机设置

5、多个交叉点，然后进行基因交换，其操作过程与单点交叉和两点交叉相类似3、均匀交叉：也称一致交叉，是指两个配对个体的每个基因座上的基因都以相同的交叉概率进行交换，从而形成两个新的个体，其具体运算是通过设置一屏蔽字来确定新个体的各个基因如何由哪一个父代个体来提供，主要操作过程如下：1）随机产生一个与个体编码串长度等长的屏蔽字W=w1w2Lw1Lw1，其中L为个体编码串长度。2）由上述规则从AB两个父代个体中产生出两个新的子代个体A’、B’，若wi=0则A’在第i个基因座上的基因值继承A的对应基因值，B’在第i个基因座上的基因值继承B的对应基因值，若i=1,则A’在第i个基因座上

6、的基因值继承B的对应基因值，B’在第i个基因座上的基因值继承A的对应基因值。4、均匀两点交叉：是指两个配体A、B中随机产生两个交叉点，然后按随机产生的0、1、2三个整数进行基因交换，从而形成两个新的个体。当随机数是0时，配体的前面部分交叉;当随机数是1时配体的中间部分交叉;当随机数是2时，配体的后面部分交叉还有其他的交叉算子，如缩小代理交叉，洗牌交叉等。5、适合浮点数编码的交叉算子浮点数编码方法是指个体的每个基因值用某一范围内的一个浮点数来表示，个体的编码长度等于其决策变量的个数除上述所述的适合二进制编码方法的交叉算子可用于浮点数编码方法的交叉操作中还使用以下主要的交叉算

7、子1）离散交叉：是指在个体之间交换变量的值子个体的每个变量可按等概率随机地挑选父个体2）算术交叉：是指由两个个体的线性组合而产生出两个新的个体，算术交叉的操作对象一般是由浮点数编码所表示的个体.其定义为两个向量，染色体的组合:x1=ʎ1x1+ʎ2x2；x2=ʎ1x2+ʎ2x1其中ʎ1、ʎ2称为乘子，特殊情况有当ʎ1=ʎ2=0.5时，Davis称其为平均交叉Schwefel称其为中间交叉intermediatecrossover把乘子作为区间[-d，1+d]上的随机数时，Muhlenbein和Schlierkamp-Voosen