多父辈遗传算法交叉算子研究

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

1、多父辈遗传算法交叉算子研究[日期：2006-05-31]来源： 作者：[字体：大中小]罗治情 戴光明 詹炜 郑蔚  摘要:通过对遗传算子和多父辈交叉遗传算法的研究，提出了多父辈循环移位的交叉算子。新的交叉算子能够让多父体之间实现基因互补，达到保持种群个体多样性的目的。仿真测试结果表明：新的算子改进了多父辈遗传算法对全局最优解的搜索能力和收敛速度。在此基础上可以进一步改善多父辈遗传算法的性能，从而使遗传算法获得更广泛的应用。关键词:多父辈；遗传算法；遗传算子；循环交叉1 引言传统的遗传算法作为一种通用的自适应随机搜索算法，存在着局部收敛和收敛速度慢这两个问题。而多父辈交叉

2、(Multi-parentRecombination)遗传算法在近年来逐渐引起了研究者的注意。由于随着在交叉操作中多父辈的引入，降低了一些个体将自身复制到子代中的可能性，这就意味着多父辈交叉有利于提高遗传算法的性能。但是，研究发现，对于不同的测试函数，不知道在何种情况下或者说对于具有何种特点的测试函数，应该采用何种交叉算子才能获得最优的结果。本文在对遗传算子和多父辈交叉遗传算法的研究的基础上，提出了多父辈循环移位的交叉算子，算子改进了多父辈遗传算法的性能。2 多父辈遗传算法的算子在多父辈遗传算法的研究中，其遗传算子一直都是被研究的热点。曾经也有很多学者进行了相关方面的研

3、究。如：多父辈交叉的基因池重组算子(Genepoolrecombination)、、二值编码遗传算法的多父辈扫描交叉(scanningcrossover)算子和对角线交叉(diagonalcrossover)算子以及采用边界镜像延拓(BoundaryExtensionbyMirroring,BEM)的实数编码的质心交叉(CenterofMassCrossover,CMX)算子和单纯形交叉(SimplexCrossover,SPX)算子。另外还有多父辈的单峰均匀分布交叉算子(UnimodalNormalDistributionCrossover,UNDX-m)。通过对以上

4、研究的总结可以知道：多父辈交叉有利于提高遗传算法的性能，但是同时也发现多父辈交叉遗传算法的性能依赖于测试函数和交叉操作的父辈数量。3 循环移位交叉算子的设计循环移位交叉算子的思想实质上就是基本遗传算法中的交叉算子，只是在本文中处理方式不一样而以，由于是多个父体进行交叉，产生的后代也不是只有一个后代个体。因此，需要在交叉过程中进行有效的处理，以便得到同样数目的个体。基本遗传算法的交叉操作一般是在交配池中选择两个个体之后，然后随机选择一个交叉点n，然后将两个个体基因位数n后面的基因交换而得到下一代个体。如图1所示。图1基本遗传算法中的交叉操作本文的多父辈交叉操作思想来自于基

5、本的交叉操作，但是在处理上有些不同之处。在交配池中随机选择一定数目（一般≥3）的参入交叉的父辈个体之后，将这些父辈个体的染色体连接在一起，形成一个长的染色体C。然后，产生一个随机数P（1≤P≤单个染色体长度-1），将C循环左移P位，即让左端移出的基因填补到C的右端，得到C。如图2所示。交叉完之后，再按照单个个体染色体的长度将C’“分割还原”为后代子个体。 图2循环移位交叉操作另外，在算法的实际实现过程中，我们引入了自适应的概念。当进化到群体中最坏个体和最好个体的适应度相差很小的时候，我们可以减小父辈的数目，从而加快算法的收敛速度。4 算法模拟测试为了检验本文交叉算子对多

6、父辈遗传算法的搜索能力的影响，选取平均收敛次数作为评价标准。平均收敛次数是指对于同一目标函数做多次测试(本文对同一目标函数统一都做30次)而得到的停机代数的平均值。算法的停机条件也是采用一般常用的方法，适应度值与当前理论结果的差值（e）很小则认为算法收敛并停机；另外如果进化代数大于某一指定的值时则认为不收敛并停机。本文中选取的测试函数：F1：六驼峰函数f(x,y)=(4-2.1x2+x4/3)x2+xy+(-4+4y2)y2的最小值，-100≤x,y≤100。函数在两个不同点：(-0.089860,0.712657)和(0.089860,-0.712657)为全局最小，

7、最小值为-1.031628。F2：DeJong函数f(x,y)=100*(x2-y)2+(1-x)2的最大值，-2.048≤x,y≤2.048。该函数有两个局部最大点(f(-2.048,-2.048)=3905.926227和f(2.048,-2.048)=3897.722309，其中第一个点为全局最大点。F3：函数f(x,y)=(a÷(b+(x2+y2)))2+(x2+y2)的最大值,-5.12≤x,y≤5.12。其中设a=3.0，b=0.05，maxf(0,0)=3600，同时存在4个局部极值点。测试结果如表1所示：表1函数优化测试结