遗传算法交叉变异

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

2、雷码编码是其连续的两个整数所对应的编码之间只有一个码位是不同的，其余码位完全相同。它是二进制编码方法的一种变形。十进制数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）举例：对于区间0。1023中两个邻近的整数X1=175和X2=176，若用长

3、度为10位的二进制编码，可表示为X11：0010101111和X12 0010110000，而使用同样长度的格雷码，它们可分别表示为X21：0010101111和X22：0010101000。（3）优点：增强了遗传算法的局部搜索能力，便于连续函数的局部控件搜索。3、符号编码法符号编码法是指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集如A,B,C。符号编码的主要优点是：1)符合有意义积术块编码原则2)便于在遗传算法中利用所求解问题的专门知识3)便于遗传算法与相关近似算法之间的混合使用。但对于使用符号编码方法的遗传算法，一般需要认真设计交叉、变异等遗传运算的操作方法，以满足

4、问题的各种约束村求，这样才能提高算法的搜索性能。2、 交叉的方法1、单点交叉：单点交叉又称为简单交叉，它是指在个体编码串中只随机设置一个交叉点，然后在该点相互交换两个配体个体的部分染色体。如图1图1 单点交叉2、两点交叉：两点交叉是指在个体编码串中随机设置了两个交叉点 然后再进行部分基因交换，两点交叉的具体操作过程是: 在相互配对的两个个体编码串中随机设置两个交叉点，交换两个个体在所设定的两个交叉点之间的部分染色体，图2为两点交叉运算示意图图2 两点交叉3、多点交叉：或称广义交叉，是指在个体编码串中随机设置多个交叉点，然后进行基因交换，其操作过程与单点交叉和两点交叉相类似3、 均匀交叉：也称一

5、致交叉，是指两个配对个体的每个基因座上的基因都以相同的交叉概率进行交换，从而形成两个新的个体，其具体运算是通过设置一屏蔽字来确定新个体的各个基因如何由哪一个父代个体来提供，主要操作过程如下：1）随机产生一个与个体编码串长度等长的屏蔽字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、均匀两点交叉：是指两个

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

7、线性组合而产生出两个新的个体，算术交叉的操作对象一般是由浮点数编码所表示的个体. 其定义为两个向量，染色体的组合: x1= 1x1+ 2x2；x2= 1x2+ 2x1其中 1、 2称为乘子，特殊情况有当 1= 2= 0.5时，Davis称 其 为 平 均 交 叉Schwefel称其为中间交叉 intermediate crossover把乘子作为区间 - d ，1 + d 上的随机数时，Muhlenbein 和Schlierkamp - Voosen称其为扩展中间交叉。3）启发式交叉：如果父个体1和父个体2而父个体1有较好的适应度，则如下函数产生子个体:子个体=父个体2 + Radio 3 （

8、父个体1 -父个体2）其中Radio指定子代离较好适应度的父代有多远，其缺省值为1. 23、 变异的方法1）均有变异均有变异( Uniform Mutation) 操作是指分别用符合某一范围内均匀分布的随即数, 以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。均匀变异的具体操作过程是:( 1) 依次指定个体编码串中的每各个基因座为变异点;( 2) 对每一个变异点, 以概率 pm从对应基因的取值范围内取一随机数来来代替原有基因值。2） 边界变异算子 边界变异算子( Boundary Mutation) 是均匀变异操作的一个变形遗传算法。在进行边界变异操作时, 随机地取基因座的二个对应

9、边界基因之一取代替原有基因值。3）非均匀变异算子 非均匀变异的具体操作过程于均匀那变异相似, 但它重点搜索原个体附近的微小区域。在进行由 X=X1X2XkXl向X=X1X2Xk Xl的非均匀变异操作时, 若变异点 Xk处的基因值取值范围为Ukmin,Ukmax, 则新的基因 Xk 由下式确定:式中, (t, y),( y 表示 Ukmax- Xk和 Xk- Ukmin) 表示0, y范围内符合非均匀分布的一个随机数, 要求随着进化代数 t 的增加,(t, y)接近于 0 的概率也逐渐增加。例如, (t, y)可按下式定义: (t, y)=y.(1-r(1- t/T)b)式中 r 为0,1范围内符合均匀分布的一个随机数, T 时最大进化代数, b 时一个系统参数, 它决定了随机数扰动对进化代数 t 的依赖程度。4）高斯变异算子高斯变异( Gaussian Muta