一种改进的遗传算法及其性能分析-外文翻译

1、天津大学学报2003 年 9 卷 2 期一种新的改进遗传算法及其性能分析罗批，李锵，郭继昌，腾建辅（天津大学电子信息工程系，天津 300072）摘要： 虽然遗传算法以其全局搜索、 并行计算、 更好的健壮性以及在进化过程中不需要求导而著称，但是它仍然有一定的缺陷，比如收敛速度慢。本文根据几个基本定理，提出了一种使用变异染色体长度和交叉变异概率的改进遗传算法，它的主要思想是：在进化的开始阶段，我们使用短一些的变异染色体长度和高一些的交叉变异概率来解决，在全局最优解附近，使用长一些的变异染色体长度和低一些的交叉变异概率。最后，一些关键功能的测试表明，我们的解决方案可以显著提高遗传算法的收敛速度，其综

2、合性能优于只保留最佳个体的遗传算法。关键字：编译染色体长度；变异概率；遗传算法；在线离线性能文章编号：10064982（2003）02014004遗传算法是一种以自然界进化中的选择和繁殖机制为基础的自适应的搜索技术，它是由Holland1975 年首先提出的。它以其全局搜索、并行计算、更好的健壮性以及在进化过程中不需要求导而著称。然而它也有一些缺点，如本地搜索不佳，过早收敛，以及收敛速度慢。近些年，这个问题被广泛地进行了研究。本文提出了一种使用变异染色体长度和交叉变异概率的改进遗传算法。一些关键功能的测试表明，我们的解决方案可以显著提高遗传算法的收敛速度，其综合性能优于只保留最佳个体的遗传算法

3、。在第一部分，提出了我们的新算法。第二部分，通过几个优化例子，将该算法和只保留最佳个体的遗传算法进行了效率的比较。第三部分，就是所得出的结论。最后，相关定理的证明过程可见附录。1.算法的描述1.1一些定理在提出我们的算法之前，先给出一个一般性的定理（见附件），如下：我们假设有一个变量（多变量可以拆分成多个部分，每一部分是一个变量）xa,b,xCR,二进制的染色体编码是 1.定理 1 染色体的最小分辨率是l2 -1定理 2 染色体的第 i 位的权重值是b-ai工Wi=-2(i=1,2,l)2-1定理 3 单点交叉的染色体搜索步骤的数学期望 Ec(x)是b-aEc(x)=Pc2l其中 Pc是交叉概

4、率定理 4 位变异的染色体搜索步骤的数学期望 Em(x)是Em(X)=(b-a)Pm其中 Pm是变异概率2算法机制在进化过程中，我们假设变量的值域是固定的，交叉的概率是一个常数，所以从定理 1和定理 3 我们知道，较长的染色体长度有着较少的染色体搜索步骤和较高的分辨率；反之亦然。同时，交叉概率与搜索步骤成正比。由定理 4,改变染色体的长度不影响变异的搜索步骤，而变异概率与搜索步骤也是成正比的。进化的开始阶段，较短染色体(可以是过短，否则它不利于种群多样性)和较高的交叉和变异概率会增加搜索步骤，这样可进行更大的域名搜索，避免陷入局部最优。而全局最优的附近，较长染色体和较低的交叉和变异概率会减少搜

5、索的步骤，较长的染色体也提高了变异分辨率，避免在全局最优解附近徘徊，提高了算法收敛速度。最后，应当指出，染色体长度的改变不会使个体适应性改变，因此它不影响选择(轮盘赌选择)。2算法描述由于基本遗传算法没有在全局优化时收敛，而遗传算法保留了当前一代的最佳个体，我们的方法采用这项策略。在进化过程中，我们跟踪到当代个体平均适应度的累计值。它被写成：1GX(t)=favg(t)Gt其中 G 是当前进化的一代，favg是个体的平均适应度。当累计平均适用性增加到最初个体平均适应度的 k(k1,kCR)倍，我们将染色体长度变为其自身的 m(m 是一个正整数)倍，然后减小交叉和变异的概率，可以提高个体分辨率、

6、减少搜索步骤以及提高算法收敛速度。算法的执行步骤如下：第一步：初始化群体，并计算个体平均适应度 favg。，然后设置改变参数的标志 flagoflag设为 1.第二步：在所保留的当代的最佳个体，进行选择、再生、交叉和变异，并计算当代个体的累积平均适应度 favg第三步：如果f且 flag=1,把染色体的长度增加至自身的 m 倍，减少交叉avg0.kfavg和变异概率，并设置 flag 等于 0;否则继续进化。第四步：如果满足结束条件，停止；否则转自第二步。2.测试和分析我们采用以下两种方法来测试我们的方法，和只保留最佳个体的遗传算法进行比较:.2-22sinx3y_0.5fi(x,y)=0.5

7、:22210.01x-y-，、，2一2一，、一，、f2(x,y)=4-(x-2y-0.3cos(3；tx)-0.4cos(4%y)收敛的分析在功能测试中，我们进行了以下政策：轮盘赌选择，单点交叉，位变异。种群的规模是 60。L 是染色体长度，Pc和 Pm分别是交叉概率和变异概率。我们随机选择 4 个遗传算法所保留的最佳个体来与我们的方法进行比较，它们具有不同的固定染色体长度和交叉和变异的概率。表 1 给出了在 100 次测试的平均收敛代。在我们的方法中，我们采取的初始参数是 l0=10,Pc0=0.3,Pm0=0.1 和 k=1.2,当满足改变参数的条件时，我们调整参数 l=30,Pc=0.1

8、,Pm=0.01。从表 1 中得知，我们的方法显著提高了遗传算法的收敛速度，正符合上述分析。表 1 功能测试结果方法我们的算法l=10Pc=0.1,Pm=0.1l=10Pc=0.1,Pm=0.1l=30Pc=0.1,Pm=0.1l=30Pc=0.1,Pm=0.1f1257152363579116264363f219826973423744505433在线和离线性能的分析Dejong 提出了遗传算法的定量评价方法，包括在线和离线性能评价。前者测试动态性能，而后者评估收敛性能。为了更好地分析测试功能的在线和离线性能，我们把个体的适应性乘以 10,并 f1 和 f2 分别给出了 4000 和 100

9、0 代的曲线：x,y6-5,5x,y6-1,1图 1f1 的在线与离线性能图 2f2 的在线与离线性能从图 1 和图 2 可以看出，我们方法的在线性能只比第四种情况差一点点，但比第二种、第三种、第五种好很多，这几种情况下的在线性能几乎完全相同。同时，我们方法的离线性能也比其他四种好很多。3.结论本文提出了一种使用变异染色体长度和交叉变异概率的改进遗传算法。一些关键功能的测试表明，我们的解决方案可以显著提高遗传算法的收敛速度，其综合性能优于只保留最佳个体的遗传算法。附件有了第一部分中假定的条件，定理 1 和定理 2 的验证是显而易见的。下面给出定理 3和定理 4 的证明过程：定理 3 单点交叉的

10、染色体搜索步骤的数学期望 Ec(x)是b-aEc(x)=Pc2l其中 Pc是交叉概率证明：如图 A1 所示，我们假设交叉发生在第 k 个基因位点，从 k 到 l 的父基因位点没有变化，基因位点1 至 IJk 上的基因改变了。在交叉过程中，1 到 k 基因位点上的基因改变的概率为 0.5(1“变化“0“或者0变为 T),因此，交叉之后，基因位点上的染色体搜索步骤从 1 到 k 的数学期望是J1：1b-aj,Eck(x)=Wj一.l.2j土2j壬22-1此外，每个位点的染色体发生交叉的概率是相等的，即1Pc。交叉后，染色体搜索步骤I的数学期望是1b-akl*(222-1-1)(a)在线Pc*Eck

11、(x)LiHaimin,WuChengke.自适应变异概率的遗传算法以及其性能分析.J.ActaElectroniaSinica,1999,27(5):89-92.NaraKoichi.基于大规模的分布式系统损失最小化的改进遗传算法.A.进化计算IEEE 会议C.1995:120-125.LeiYin,WeiHong.一种改进的遗传算法以及它在 E 计划波导过滤器设计重点额应用J.ActaElectroniaSinica,2000,28(6):121-124.EnriqueAlba,JoseMTroya.迁移策略在结构化的随机交配群体中的并行分布遗传算法的影响.J.应用智能，2000,12:1

12、63-181.RudolphR.经典遗传算法的收敛分析.J.基于神经网络的 IEEE 转录，1994,5(1):96-101.把 Eq.(A1)替换为Eq.(A2),我们得到-1Ec(x)八 P1bak(2-1)Pcb-a2liPc*(b-a)(2-1)-l=(12l其中 l 是非常大的，J一定0,所以Ec(x)电吐apc2-12lTransactionsofTianjinUniversityVol.9No.2Jun.2003ImprovedGeneticAlgorithmandItsPerformanceAnalysisLUOPi（罗批），LIQiang（李锵），GUOJichang（郭继昌

13、），TENGJianfu（滕建辅）（SchoolofElectronicInformationEngineering,TianjinUniversity,Tianjin300072,China）Abstract:Althoughgeneticalgorithmhasbecomeveryfamouswithitsglobalsearching,parallelcomputing,betterrobustness,andnotneedingdifferentialinformationduringevolution.However,italsohassomedemerits,suchasslowc

14、onvergencespeed.Inthispaper,basedonseveralgeneraltheorems,animprovedgeneticalgorithmusingvariantchromosomelengthandprobabilityofcrossoverandmutationisproposed,anditsmainideaisasfollows:atthebeginningofevolution,oursolutionwithshorterlengthchromosomeandhigherprobabilityofcrossoverandmutation;andatthe

15、vicinityofglobaloptimum,withlongerlengthchromosomeandlowerprobabilityofcrossoverandmutation.Finally,testingwithsomecriticalfunctionsshowsthatoursolutioncanimprovetheconvergencespeedofgeneticalgorithmsignificantly,itscomprehensiveperformanceisbetterthanthatofthegeneticalgorithmwhichonlyreservesthebes

16、tindividual.Keywords:variantchromosomelength;variantprobability;geneticalgorithm;onlineandofflineperformanceArticleID:10064982（2003）02014004Geneticalgorithmisanadaptivesearchingtechniquebasedonaselectionandreproductionmechanismfoundinthenaturalevolutionprocess,anditwaspioneeredbyHollandinthe1970s.It

17、hasbecomeveryfamouswithitsglobalsearching,parallelcomputing,betterrobustness,andnotneedingdifferentialinformationduringevolution.However,italsohassomedemerits,suchaspoorlocalsearching,prematureconverging,aswellasslowconvergencespeed.Inrecentyears,theseproblemshavebeenstudied.Inthispaper,animprovedge

18、neticalgorithmwithvariantchromosomelengthandvariantprobabilityisproposed.Testingwithsomecriticalfunctionsshowsthatitcanimprovetheconvergencespeedsignificantly,anditscomprehensiveperformanceisbetterthanthatofthegeneticalgorithmwhichonlyreservesthebestindividual.Insection1,ournewapproachisproposed.Thr

19、oughoptimizationexamples,insection2,theefficiencyofouralgorithmiscomparedwiththegeneticalgorithmwhichonlyreservesthebestindividual.Andsection3givesouttheconclusions.Finally,someproofsofrelativetheoremsarecollectedandpresentedinappendix.1Descriptionofthealgorithm1.1SometheoremsBeforeproposingourappro

20、ach,wegiveoutsomegeneraltheorems(seeappendix)asfollows:Letusassumethereisjustonevariable(multivariablecanbedividedintomanysections,onesectionforonevariable)xCa,b,xR,andchromosomelengthwithbinaryencodingis1.Minimalresolutionofchromosomeisbas=Theorem2Weightvalueoftheithbitofchromosomeisone-pointcrosso

21、veriswherePcistheprobabilityofcrossover.MechanismofalgorithmDuringevolutionaryprocess,wepresumethatvaluedomainsofvariablearefixed,andtheprobabilityofcrossoverisaconstant,sofromTheorem1and3,weknowthatthelongerchromosomelengthis,thesmallersearchingstepofchromosome,andthehigherviceversa.Meanwhile,cross

22、overprobabilityisindirectproportiontoFromTheorem4,changingthelengthofchromosomedoesnotaffectofmutation,whilemutationprobabilityisalsoindirectproportiontoAtthebeginningofevolution,shorterlengthchromosome(canbetooshorter,otherwiseitisharmfultopopulationdiversity)andhigherprobabilityofcrossoverandmutat

23、ionincreasessearchingstep,whichcancarryoutgreaterdomainsearching,andavoidfallingintolocaloptimum.Whileatthevicinityofglobaloptimum,longerlengthchromosomeandlowerprobabilityofcrossoverandmutationwilldecreasesearchingstep,andlongerlengthchromosomealsoimprovesresolutionofmutation,whichavoidwanderingnea

24、rtheglobaloptimum,andspeedsupalgorithmconverging.Theorem1b-aijwi=-2(i=1,2,l)Theorem3MathematicalexpectationEc(x)ofchromosomesearchingstepwithEc(x)=b-aPc2lTheorem4MathematicalexpectationmutationisEm(x)=(b-a)PmwherePmistheprobabilityofmutation.Em(x)ofchromosomesearchingstepwithbitresolution;andsearchi

25、ngstep.searchingstepsearchingstep.Finally,itshouldbepointedoutthatchromosomelengthchangingkeepsindividualfitnessunchanged,henceitdoesnotaffectselection(withroulettewheelselection).DescriptionofthealgorithmOwingtobasicgeneticalgorithmnotconvergingontheglobaloptimum,whilethegeneticalgorithmwhichreserv

26、esthebestindividualatcurrentgenerationcan,ourapproachadoptsthispolicy.Duringevolutionaryprocess,wetrackcumulativeaverageofindividualaveragefitnessuptocurrentgeneration.Itiswrittenas1GX(t)=、favg(t)GtXwhereGisthecurrentevolutionarygeneration,favgisindividualaveragefitness.Whenthecumulativeaveragefitne

27、ssincreasestoktimes(k1,kR)ofinitialindividualaveragefitness,wechangechromosomelengthtomtimes(misapositiveinteger)ofitself,andreduceprobabilityofcrossoverandmutation,whichcanimproveindividualresolutionandreducesearchingstep,andspeedupalgorithmconverging.Theprocedureisasfollows:Step1Initializepopulati

28、on,andcalculateindividualaveragefitnessfavg0,andsetchangeparameterflag.Flagequalto1.Step2Basedonreservingthebestindividualofcurrentgeneration,carryoutselection,regeneration,crossoverandmutation,andcalculatecumulativeaverageofindividualaveragefitnessuptocurrentgenerationfavg;favgStep3IfkandFlagequals

29、1,increasechromosomelengthtomtimesoffavg0itself,andreduceprobabilityofcrossoverandmutation,andsetFlagequalto0;otherwisecontinueevolving.Step4Ifendconditionissatisfied,stop;otherwisegotoStep2.2TestandanalysisWeadoptthefollowingtwocriticalfunctionstotestourapproach,andcompareitwiththegeneticalgorithmw

30、hichonlyreservesthebestindividual:.2-22sinx，y0.5L（x,y）=0.52kx,y_5,510.01x2-y222f2（x,y）=4（x-2y0.3cos（3冗x）0.4cos（4冗y）x,y_1,11AnalysisofconvergenceDuringfunctiontesting,wecarryoutthefollowingpolicies:roulettewheelselection,onepointcrossover,bitmutation,andthesizeofpopulationis60,lischromosomelength,Pan

31、dPmaretheprobabilityofcrossoverandmutationrespectively.Andwerandomlyselectfourgeneticalgorithmsreservingbestindividualwithvariousfixedchromosomelengthandprobabilityofcrossoverandmutationtocomparewithourapproach.Tab.1givestheaverageconverginggenerationin100tests.Inourapproach,weadoptinitialparameterl

32、0=10,Pc0=0.3,Pm0=0.1andk=1.2,whenchangingparameterconditionissatisfied,weadjustparameterstol=30,Pc=0.1,Pm=0.01.FromTab.1,weknowthatourapproachimprovesconvergencespeedofgeneticalgorithmsignificantlyanditaccordswithaboveanalysis.Tab.1ResultoffunctiontestingFunctionsOuralgorithml=10Pc=0.1,Pm=0.1l=10Pc=

33、0.1,Pm=0.1l=30Pc=0.1,Pm=0.1l=30Pc=0.1,Pm=0.1f1257152363579116264363f2198269734237445054332AnalysisofonlineandofflineperformanceQuantitativeevaluationmethodsofgeneticalgorithmareproposedbyDejong,includingonlineandofflineperformance.Theformertestsdynamicperformance;andthelatterevaluatesconvergenceperf

34、ormance.Tobetteranalyzeonlineandofflineperformanceoftestingfunction,wemultiplyfitnessofeachindividualby10,andwegiveacurveof4000and1000generationsforf1andf2,respectively.FromFig.1andFig.2,weknowthatonlineperformanceofourapproachisjustlittleworsethanthatofthefourthcase,butitismuchbetterthanthatofthese

35、cond,thirdandfifthcase,whoseonlineperformancesarenearlythesame.Atthesametime,offlineperformanceofourapproachisbetterthanthatofotherfourcases.ConclusionInthispaper,basedonsomegeneraltheorems,animprovedgeneticalgorithmusingvariantchromosomelengthandprobabilityofcrossoverandmutationisproposed.Testingwi

36、thsomecriticalfunctionsshowsthatitcanimproveconvergencespeedofgeneticalgorithmsignificantly,anditscomprehensiveperformanceisbetterthanthatofthegeneticalgorithmwhichonlyreservesthebestindividual.AppendixWiththesupposedconditionsofsection1,weknowthatthevalidationofTheorem1andTheorem2areobvious.(a)onli

37、neFig.1Onlineandofflineperformanceoffl(a)online(b)onlinepointcrossoverisb-aEc(x)=Pc2lwherePcistheprobabilityofcrossover.AsshowninFig.A1,weassumethatcrossoverhappensonthekthlocus,i.e.parentslocusfromktoldonotchange,andgenesonthelocusfrom1tokareexchanged.Duringcrossover,changeprobabilityofgenesonthelocusfrom1tokis20to1).So,aftercrossover,mathematicalexpectationofchromosomesearchingsteponlocusfrom1tokisFurthermore,probabilityoftakingplacecrossoveroneachlocusofchromosomeisequal,namely-Pc.Therefore,aftercrossover,mathematicalexpectationofchromosomel