一种改进型交叉算子和自识别高变异算子新型遗传算法的研究

遗传算法的相关知识

第37卷第6期2009年12月

福州大学学报（自然科学版）

JournalofFuzhouUniversity（NaturalScienceEdition）

Vol.37No.6Dec.2009

文章编号：1000－2243（2009）06－0808－04

一种改进型交叉算子和自识别高变异算子新型遗传算法的研究

叶菁，张莹，阮一文

（福州大学数学与计算机科学学院，福建福州350108）

摘要：为有效地解决遗传算法收敛性和多样性的矛盾，在分析算子结构的基础上，提出了一种新型的遗传算法.该算法的核心在于，一方面通过父子竞争保留优秀个体和改进型交叉算子保证收敛性，另一方面对参与交叉的基因段进行基于海明距离相似度检测提高交叉操作的有效性；最后，采用基于基因位多样度的自识别高变异率算子来改善种群的多样性.实验证明，改进的算子显著地提高了收敛速度和搜索全局最优解的能力.关键词：遗传算法；交叉算子；海明距离；自识别；变异算子中图分类号：TP301.6文献标识码：A

Anewgeneticalgorithmbasedonimprovedcrossoverand

self－identifyhighmutationoperators

YEJing，ZHANGYing，RUANYi－wen

（CollegeofMathematicsandComputerScience，FuzhouUniversity，Fuzhou，Fujian350108，China）

Abstract：Inordertosolvetheconflictbetweenalgorithmconvergenceanddiversity，afteranalyzing

scorethestructureofoperator，thispaperputsforwardanimprovedgeneticalgorithm.Thisalgorithm’

liesonretainingtheoutstandingindividualthroughparents，offspringscompetitionandimprovedcross-overoperatortoguaranteeconvergence.Ontheotherhand，carryingonthesimilarityexaminationtothecrossovergenesectionbasedontheHamingdistancetoenhancevalidity.Finally，usingtheself－identifyhighmutationoperatorbasedongenepositiondiversetoimprovethepopulationdiversity.Theexperimentalresultsshowthattheimprovedoperatorimprovestheabilityofsearchinganoptimumsolu-tionandincreasestheconvergentspeed.

Keywords：geneticalgorithm；crossoveroperator；Hamingdistance；self－identify；mutationoperator遗传算法（GA）是通过模拟自然界中的遗传进化过程而发展起来的算法，GA通过选择、交叉和变异等方式搜寻全局最优解，其主要优点在算法的鲁棒性、全局的最优性和广泛的适用性.然而，在实际应用中，传统的遗传算法都采用较低选择变异概率，特别是对高适应度个体的保护过高，容易发生早熟现象，造成群体的多样性差即全局搜索能力有限.如果采用较高选择变异算子多样性得到改善，但近似随机搜索，收敛性差.很多研究者提出一些方法来改善遗传算法的性能，但这些方法都没有很好地解决上述两者

［1］的矛盾.文献使用较大的变异概率对个体执行变异操作，避免群体早熟的发生，但算法的收敛性较［2］差.文献提出的交叉算子加快了算法的收敛速度，但无法得到最优解.针对遗传算法的弊病，从算子

的结构入手，一方面采用父子竞争保留优秀个体和改进型交叉算子增强收敛性，另一方面使用基于基因位的多样度自识别高变异率算子改善种群的多样性，同时对参与交叉个体的基因段进行相似度检测，保证交叉操作的有效性.

1

1.1

遗传算法的研究与改进

采用父子竞争保留优秀个体

在基本遗传算法（SGA）中，采用轮盘赌算法选择优秀父代个体进行交叉和变异产生新个体，并且希

望子代个体优于父代，但如果父代个体适应度高而子代个体适应度低，这种“父淘子留”的策略反而降低了群体的适应度，只好牺牲交叉和变异概率，以期收敛性的改善，使得算法向最优解的逼近过程缓慢.

收稿日期：2008－12－09

作者简介：叶菁（1974－），男，硕士，讲师.

遗传算法的相关知识

本算法采用父子竞争的机制，保留优秀个体.具体描述如下：2个父代个体交叉产生2个新一代个体，从4个个体中选择适应度高的2个个体进入下一代，这样后代群体的适应度得到很大的改善，有效解决局部及全局收敛性的问题.1.2交叉算子的改进1.2.1

自适应交叉概率

传统遗传算法采用较为保守的交叉概率pc，因为交叉概率的大小直接影响算法的收敛性，交叉概率越大，新个体产生的速度就越快，然而交叉概率过大遗传模式被破坏的可能性也越大，使得具有高适应度的模式很快被破坏；反之，交叉概率过小，个体的多样性受到抑制，搜索过程缓慢.另外，对优秀个体与较差个体都采用相同的交叉概率，不利于保留优秀的基因段和较差基因段的淘汰.采用自适应交叉概率，不同的个体采用不同的交叉概率，对于适应度高于群体平均适应度的个体，给予较高的交叉概率，使它的优秀基因段得以遗传进入下一代；反之适应度低于平均适应度的个体，给予较低的交叉概率，使之被淘

［3］

汰.自适应交叉概率为：

（pc1－pc2）（f－favg）pc1+（f≥favg）

fmax－favgpc=（1）

{

pc2（f<favg）

令pc1=0.7，pc2=0.3，由式（1）得最优个体交叉概率1.0.当个体适应度等于平均值时，其交叉概率为

0.7；当个体适应度值小于平均值时，则交叉概率为0.3.这样，优秀个体有较大概率进行交叉操作.1.2.2

自适交叉位

本算法采用二进制编码，个体基因位采用正排序，保证二进制转变为十进制前段基因的权大于后段，例如：个体A（1101011011101000111111010）转变为十进值为28168698，带下划线3段相同的基因座其权0.0019，0.0.交叉位若发生在基因前段则对子代适应度影响较大的，可实现全局搜系数分别是0.9678，

索；若发生在基因后段，使得权值较大的前段基因得以保留，增加权值较小基因段的多样性，实现局部搜索.算法采用单点交叉，并控制随机数的产生，当进化代数增加时交叉位逐渐后移，即由全局搜索转向局

［r1－1，r2－1］部搜索.例如：C语言中函数random（intr1，intr2）随机生成之间的，本算法取该函数的参数，r1=（int）（1.2.3

gm

·+1），r2=m+1，m为基因长度，G为总的进化代数，g为当前世代数.G2

基于海明距离基因段相似度的检测

采用自适应交叉位生成算子提高局部或全居搜索能力，但随着进化代数的增加，后段基因也接近收敛，如何保证交叉操作的有效性呢？本算法对后段基因采用基于海明距离相似度检测，只有当两个后段基因段相似度s大于阀值v时，两个体才进行交叉；而阀值的选择与世代数相关，因为随着世代数的增加，个体逐渐形成高阶高距的积木块，为保证有交叉操作的发生，采用比较低的阀值，产生更多多样的个体，提高局部搜索能力.相关公式定义如下.

1）海明距离：

k

Dij=

∑n=1

bin－bjn

（r<i，j<m∩i≠j）（2）

其中：k为个体串的编码长度，bin为第i个个体的第n位基因的值，r随机数（0≤r≤m），m后段基因座

长度.

2）基因段相似度：

s（i，j）=Dij/m

3）检测阈值：

v=

1g2－3G

（0≤s（i，j）≤1）

（3）（4）

()

（

12

）≤v≤

33

其中：G为总的进化代数，g为当前世代数.

例如，假设染色体长度m=15，总的进化代数G=100，当前世代数g=30，有两个个体基因A=1011010010|01101和B=1011010111|10001如下，随机产生一交叉位r=10，则两个体后段基因段的海明

遗传算法的相关知识

距离为4，基因段相似度s（A，B）=0.8，阈值v=0.57，相似度大于阀值，执行交叉；否则，从父代中再选择个体进行操作，直到满足种群大小为止.1.3

基于基因位多样度的自识别高变异算子

根据模式定理，在遗传算法中，具有低阶、短定义距、高适应度的模式在子代进化中呈指数增长，种

群即将收敛时，基因模式趋同；而具有高阶、长定义距的模式进化速度就会很慢，甚至停滞，导致整个种群多样性下降.具体到各染色体，即某一个基因位的数值趋向一致，这时本应采用较高的变异概率来提高种群多样性；但传统遗传算法由于担心收敛性的问题，仍采用比较低的变异概率，或者对种群中个体适应

［0.01，0.2］.随世代数度趋于一致时提高变异率，个体适应度比较分散时降低变异率，变异概率pm多在

增加，种群的多样性差，造成局部或全局搜索能力有限，特别对多峰函数的搜索易陷入局部最优解.

由于本算法采用父子竞争保留优秀个体和改进型交叉算子，有效保证了收敛性，因此采用基于基因

［4］

0.0，1.0］.自识别变异率pm定义为：对于本代种群中所有个体的第位多样度自识别的高变异算子pm［

k个基因位，若该基因位“0”的个数为n，则该基因位的多样度d=n/N，N种群个数.当d=0.5时，多样

，“0”“1”度最大，表示种群中的个体在该基因位上比较分散各半，不需要过多的变异操作；第k个基因位

“0”“1”，即p=0或1时，这说明种群在此基因位完全收敛，此时通过增大变异概率来增或上的基因全是

加种群的多样性.第n位基因的变异概率为：

Pnn=k1·dn－0.5+k20，2.0］，令k2=1－2k1.其中：k1∈［

（5）

2算法流程

采用传统的二进制编码，具体的运算步骤如下：

step1初始化操作，设置控制参数和产生初始种群；step2step3step4

计算种群的适应度；

轮盘赌选择参与交叉操作的父代个体；

首先计算当代种群的最大适应度fmax和平均适应度favg，而后根据公式（1）计算交叉概率，若

满足条件执行下一步，否则转向步骤3；

step5随机产生自适应交叉位，根据公式（2）（3）计算后段基因的相似度s（i，j）；

step6step7step8step9

若相似度小于阀值v（公式（4）），则转向步骤2，否则执行交叉；

根据第n位基因的多样度，根据公式（5）计算变异概率pmn，执行变异操作；父子竞争保留选择2个最佳个体进入下一代；

检验新一代群体适应度是否满足要求，若满足则结束，否则转向步骤2.

3

3.1

改进算法仿真实例分析

Camel函数

此函数有6个局部极小点，其中有两个（－0.0898，0.7126）和（0.0898，－0.7126）为全局最小点，最小值为－1.031628，自变量取值范围为－100<x，y<100.改进算法对Camel函数进行测试，并对结果作了详细分析.实验在TurboC环境下各自运行100次，群体规模为50，进化代数为100代.从图1可以看到本算法在16代就已经收敛，与SGA算法相比能以较快的速度跳离局部最优解，并以较高的概率收敛于全局最优解.

表1两种算法的适应度值测试对照表

Thevalueofthefitnesstestcomparisonabouttwokindsofalgorithm

算法

传统遗传算法（SGA）

本算法

平均适应度－0.957763－1.031518

最优适应度－1.02901－1.031628

Tab.1

函数Camel函数

遗传算法的相关知识

图1

Fig.1

Camel函数最大适应度比较

ComparisonofthelargestfitnessCamelfunction

3.2Shaffer函数

先对常用的多局部极值点的二元多峰数值Shaffer函数进行测试.该函数有无数的极大点，其中，只

0）达到全局最大值为1，此函数周围有一个圆脊，它们的取值均为0.990283，因此容易陷入此局有在（0，

部极大点.在TurboCforWindows平台运行，染色体x、y长度分别为28，最大进化代数为100，初始化群

体为100，交叉概率pc为1.0，变异概率pmn参数（k1=2.0，k2=0.0），每组随机运行10.仿真结果如表2所示.

表2测试Shaffer函数获得最大值1时相关性能指标

TherelatedperformanceindexoftestingShafferfunctiontoobtainthemaximumvalue1

平均世代数/代

161611181916

平均适应度0.9420850.9268650.9426430.9540250.9991400.952952

累计子代中父代

个体比例54.52%54.12%39.44%61.44%70.36%55.98%

交叉发生次数/次200342123202207215

因相似度小于阀值而不发生交叉次数的比例

83.26%94.01%90.40%84.14%85.12%90.10%

Tab.2

实验组数第一组第二组第三组第四组第五组平均值

笔者使用同样的参数运行SGA算法10次，最优值为0.9794021，没有得到最大值1，本文算法最快

［5，6］（注：文献［5］、［6］得到最大值分别为55代，22代）的结果.从在第3代就得到最大值，优于文献

表2中得知，性能指标累计子代中父代个体百分比平均值为55.98%，证明采用父子竞争保留优秀个体的思路是正确的，对提高种群平均适应度即收敛效果显著；性能指标因基因段相似度小于阀值而放弃交叉平均比例值高达90.10%，证明了基于海明距离基因段相似度检测保证交叉操作的有效性是有效的.从表3中可知，变异概率相同情况下，种群规模越大效果最好；在种群规模大小一致情况下，变异概率越大，产生子代个体的多样性越丰富，全局收索能力越佳，证明了本算法提出的高变异算子是正确的.

表3种群大小和变异概率参数k1（k2=0）对算法性能的影响

Theinfluenceofpopulationsizeandmutationparameterk1（k2=0）toalgorithmperformance

种群大小

20>100>100>10095>100

40>100>100>10080>100

60>100>100>100>100>100

80181220>100>100

100161830>100>100

12024351050>100

Tab.3

k2取值2.01.51.00.50.1

注：表3内数值为在不同种群大小和k2取值情况下，算法取得最大值运行的代数

（转第817页）

遗传算法的相关知识

第6期参考文献：

程红举，等：一种新颖的多信道多接口无线Mesh网络的接入调度算法

·817·

［1］AkyildizI，WangX，WangW.Wirelessmeshnetworks：asurvey［J］.ComputerNetworks，2005，47：445－487.

［2］KyasanurP，ChereddiC，－X：amultichannelmulti－interfacewirelessmeshimplementation［J］.ACMSIG-COMMComputerCommunicationReview，2007，11：84－95.

［3］RobertL.Alohapacketsystemwithandwithoutslotsandcapture［J］.ACMSIGCOMMComputerCommunicationReview，

1975，5：28－42.

［4］ZhuC，CorsonM.Afive－phasereservationprotocol（FPRP）formobileadhocnetworks［J］.WirelessNetworks，2001，7：

371－384.

［5］LloydE.BroadcastschedulingforTDMAinwirelessmulti－hopnetworks［M］//StojnenovicacuteI.Handbookofwirelessnet-2002：347－370.worksandmobilecomputing.NewJersey：JohnWileyandSonsInc，

［6］PondC，LiV.Adistributedtime－slotassignmentprotocolformobilemulti－hopbroadcastpacketradionetworks［C］//IEEE

MILCOM′89.Boston：［s.n.］，1989，1：70－74.

［7］AP：aunifyingdynamicdistributedmultichannelTDMAslotassignmentprotocol［C］//IEEEMILCOM′96.Wash-ington：［s.n.］，1996，1：235－239.

［8］NgoC，LiV.Centralizedbroadcastschedulinginpacketradionetworksviagenetic－fixalgorithms［J］.IEEETransactionson

2003，51：1439－munications，

［9］ChlamtacI，PinterS.Distributednodesorganizationalgorithmforchannelaccessinamultihopdynamicradionetworks［J］.

IEEETransactionsonComputers，1987，36：729－737.

［10］HermanT，TixeuilS.AdistributedTDMAslotassignmentalgorithmforwirelesssensornetworks［J］.LectureNotesinCom-puterScience，2004，3121：45－58.

［11］BrelazD.Newmethodstocolortheverticesofagraph［J］.CommunicationsoftheACM，1979，22：251－256.［12］KlotzW.Graphcoloringalgorithms［J］.MathematicBericht，2002，5：1－9.

（编辑：林晓）

檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨（接第811页）参考文献：

［1］马均水，刘贵忠，贾玉兰.改进遗传算法搜索性能的大变异操作［J］.控制理论和应用，1998，15（3）：404－407.［2］孟佳娜，王立宏.具有自识别能力的遗传算法求解旅行商问题［J］.计算机工程与应用，2006，26（13）：51－52.［3］王小平，曹立明，遗传算法———理论、应用与软件实现［M］.西安：西安交通大学出版社，2002.［4］吴秋玲，杨启文.改进型自适应遗传变异算子［J］.河海大学常州分校学报，2005，19（4）：12－15.

［5］卢厚清，陈亮，宋以胜.一种遗传算法交叉算子的改进算法［J］.解放军理工大学学报：自然科学版，2006，8（3）：250

－251.

［6］孙秀娟，刘希玉，李丽丽.基于自识别交叉算子和自适应变异算子的遗传算法的研究［J］.信息技术与信息化研究与探

2008（1）：55－57.讨，

（责任编辑：沈芸）

本文来源：https://www.bwwdw.com/article/1324.html