遗传算法及其MATLAB实现 .docx

遗传算法及其MAT1.AB实现主要参考书：MAT1.AB6.5辅助优化计算与设计飞思科技产品研发中心编著电子工业出版社2003.1遗传算法及其应用陈国良等编著人民邮电出版社1996.6主要内容：£遗传算法简介Ga遗传算法的MAT1.AB实现£应用举例在工业工程中,许多最优化问题性质十分复杂,很难用传统的优化方法来求解.自1960年以来,人们对求解这类难解问题日益增加.一种模仿生物自然进化过程的、被称为“进化算法(evolUlionaryalgorithm)”的随机优化技术在解这类优化难题中显示了优于传统优化算法的性能。目前，进化算法主要包括三个研究领域：遗传算法、进化规划和进化策略。其中遗传算法是迄今为止进化算法中应用最多、比较成熟、广为人知的算法。一、遗传算法简介遗传算法(GenetiCAIgOrithm,GA)最先是由美国Mic-hgan大学的JohnHolland于1975年提出的。遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的思想源于生物遗传学和适者生存的自然规律，是具有“生存+检测”的迭代过程的搜索算法。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定等5个要素组成了遗传算法的核心内容。遗传算法的基本步骤：遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法，与传统搜索算法不同，遗传算法从一组随机产生的称为“种群(PoPUlalion)”的初始解开始搜索过程。种群中的每个个体是问题的一个解，称为“染色体(ChromOSome),染色体是一串符号，比如一个二进制字符串。这些染色体在后续迭代中不断进化，称为遗传。在每一代中用“适值(fitness)”来测量染色体的好坏，生成的下一代染色体称为后代(offspring)。后代是由前一代染色体通过交叉(CroSSoVer)或者变异(mutation)运算形成的。在新一代形成过程中，根据适度的大小选择部分后代，淘汰部分后代。从而保持种群大小是常数。适值高的染色体被选中的概率较高，这样经过若干代之后，算法收敛于最好的染色体，它很可能就是问题的最优解或次优解。主要步骤如下所示：编码：GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点。(2)初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了一个群体。GA以这N个串结构数据作为初始点开始迭代。(3)适应性值评估检测：适应性函数表明个体或解的优劣性。对于不同的问题，适应性函数的定义方式也不同。(4)选择：选择的目的是为了从当前群体个选出优良的个体,使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的适者生存原则。(5)交叉：交叉操作是遗传算法中最主要的遗传操作。通过交叉操作可以得到新一代个体，新个体组合了其父辈个体的特性。交叉体现了信息交换的思想。编码和种群生成(6)变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样，GA中变异发生的概率很低，通常取值在0.001-0.01之间。变异为新个体的产中提供了机会。实际上，遗传算法中有两类运算：遗传运算：交叉和变异进化运算：选择GA的计算过程流程图遗传算法的特点GA是对问题参数的编码组进行计算，而不是针对参数本身。GA的搜索是从问题解的编码组开始搜素、而不是从单个解开始。GA使用目标函数值(适应度)这一信息进行搜索，而不需导数等其他信息。GA算法使用的选择、交叉、变异这三个算子都是随机操作,而不是确定规则。举例图解说明计算流程*传算法求IC：%311一值的计算值程袒拈A体不痴弓(1机产生乂无符号运左度方及最率as«宾岳计复”后交配率(£«»示交又处)黑第加,”靠ae/(x)三/Cr>-/«=i7R保白"晶)VS)1OllOlU16941OHOll240110012144Z1100024575Oi491.972IlOOIO141100KS253010008640.C4¢.220U100OI2HOllZl7294100jl1»3610.311.331IOIOH321000016*6iff«fi()JlTO1.004.0040平均由左腹(7g2930.251.CO1.0最大遭与度Sre0.4$1.97to二、遗传算法的MAT1.AB实现需要如下主函数：编码和种群生成functionpop=initializega(num,bounds,evalF'N,evalOps,options)%pop-theinitial,evaluated,randompopulation%num-thesizeofthepopulation,i.e.thenumbertocreate%bounds-thenumberofpermutationsinanindividual(e.g.,number%ofcitiesinatsp%evalFN-theevaluationfn,usuallythenameofthe.mfileforevaluation%evalOps-anyoptionstobepassedtotheevalfunctiondefaults%options-optionstotheinitializefunction,ie.eps,float/binary,prec%whereepsistheepsilonvalueandthesecondoptionis1for%orderps.precistheprecisionofthevariablesdefaultsle-61交叉functioncl,c2=arithXovcr(pl,p2,bounds,Ops)%ArithcrossovertakestwoparentsP1,P2andperformsaninterpolation%alongthelineformedbythetwoparents.%functioncl,c2=arithXover(p1,p2,bounds,Ops)%pl-thefirstparent(solutionstringfunctionvalue)%p2-thesecondparent(solutionstringfunctionvalue)%bounds-theboundsmatrixforthesolutionspace%Ops-Optionsmatrixforarithcrossovergen#ArithXovers选择normGeomSelect：NormGeomSelectisarankingselectionfunctionbasedonthenormalizedgeometricdistribution.(基于正态分布的序列选择函数)变异functionnewPopl=normGeomSelect(oldPop,options)%NormGeomSelectisarankingselectionfunctionbasedonthenormalized%geometricdistribution.%functionnewPop=normGeomSelect(oldPop,options)%newPop-thenewpopulationselectedfromtheoldPop%oldPop-thecurrentpopulation%options-optionstonormGeomSelectgenprobability_o1.selecting_best一些辅助函数：f2b：Returnthebinaryrepresentationof(hefloatnumberfval(将浮点数转化为二进制数)b2f：ReturnthefloatnumberCorresponingtothebinaryrepresentationofbval.(将二进制数转化为浮点数)IioiiUnifMutalion:Nonuniformmutationchangesoneoftheparametersoftheparentbasedonanon-uniformprobabilitydistribution.ThisGaussiandistributionstartswide,andnarrowstoapointdistributionasthecurrentgenerationapproachesthemaximumgeneration.(基于非均一概率分布进行非均一变异)maxGenTerm：Returns1,i.e.terminatestheGAwhenthemaximal_generationisreached.(当迭代次数大于最大迭代次数时，终止遗传算法，返回为1,否则返回为0。)roulette：rouletteisthetraditionalselectionfunctionwiththeprobabilityofsurvivingequaltothefiltnessofi/sumofthefittnessofallindividuals三、应用举例1.计算下列函数的最大值。f(x)=x+10*sin(5x)+7cos(4x),x0,9方式I>>gademo方式2step1编写目标函数gademo1evalI.mfunctionsol,val=gaDemo1Eval(sol,options)x=sol(l);val=x+10*sin(5*x)+7*cos(4*x);step2生成初始种群，大小为10initPop=initializega(10,0,9,'gademo1eva11|,le-6,l);step325次遗传迭代(x,endPop,bpop,trace=ga(091.,gademo1evalI',initPop,.le-61l,maxGenTerm',25,.,normGeomSelect'J0.08,.,arithXover,1.21.'nonUnifMutation2,25,3J)%OutputArguments:%X-thebestsolutionfoundduringthecourseofthe%endPop-thefinalpopulation%bPop-atraceofthebestpopulation（解的变化）%traceinfo-amatrixofbestandmeansofthegaforeachgeneration（种群平均值的变化）%InputArguments:%bounds-amatrixofupperandlowerboundsonthevariables%evalFN-thenameoftheevaluation.mfunction%evalps-optionstopasstotheevaluationfunction(NU1.1.)%StartPop-amatrixofsolutionsthatcanbeinitialized%frominitialize.m%opts-epsilon,prob_ops,displaychangerequiredtoconsidertwosolutionsdifferent,prob_ops0ifyouwanttoapplythe%geneticoperatorsprobabilisticlytoeachsolution,Iifyouaresupplyingadeterministicnumberofoperatorapplicationsanddisplayis1tooutputprogress0forquiet,(le-610)%IennFN-nameofthe.mterminationfunction(,maxGenTerm'l)%termps-optionsstringtobepassedtotheterminationfunction(100).%selectFN-nameofthe.mselectionfunction(,normGeomSelect,l)%SelectOpts-optionssiringtobepassedtoselectafter%select(pop,#,opts)(0.08)%xOverFNS-astringcontainingblankseperatednamesOfXOVemfiles(,arithXoverheurislicXoverSimpleXover')%xverps-AmatrixofoptionstopasstoXover.mfileswiththefirstcolumnbeingthenumberofthatxvertoperformSimiliarlyformutation(20;23;20)%mutFNs-astringcontainingblankseperatednamesofmutation.mfiles(CboundaryMuUtionmultiNonUnifMulation.%nonUnifMutationUnifMutationr)%mutps-AmatrixofoptionstopasstoXover.mfileswiththefirstcolumnbeingthenumberofthatxvertoperformSimiliarlyformutation(4O0;61003;4I003;4001)2.求Sin(X)在。到3.14之间的最大值.functionsol,val=sinI(sol,options)x=sol(l);val=sin(x);initPop=initializega(10,0,3.14,sinl',le-6,l);x,endPop,bpop,trace=ga(03.14,'sin,initPop,.le-61l,maxGenTerm',25,.,normGeomSelect'J0.08,.,arithXover,l,21.'nonUnii'Mutation,2,25,31)3. binaryExample.m二元函数例子二进制编码方式1»binaryExample方式2functionsol,val=gaMichEval(sol,options)val=21.5+sol(l)*sin(4*pi*sol(l)+sol(2)*sin(20*pi*sol(2);%globalbounds%Settingtheseedbacktothebeginningforcomparisonsakerand(,seed',O)%CrossoverOperatorsxFns=,simpleXover,;xpts=.41;%MutationOperatorsmFns='binaryMutalion'mpts=0.0051;%TerminationOperatorstermFns='maxGenTerm,;IermOps=200;%200Generations%SelectionFunctionSelectFn=,roulelte'selectops=;%EvaluationFunctionevalFn='gaMichEva;evalps=;%Boundsonthevariablesbounds=-3,12.1;4.1,5.8;%GAOptionsepsilonfloat/binardisplay1gaOpls=le-601;%Generateanintializepopulationofsize20StartPop=initializega(20,bounds,'gaMichEva,U1e-60);xendPopbestPoptrace=ga(bounds,evalFn,evalOps,StartPop,gapts,.IermFns,termps,selectFn,selectps,xFns,xOpts,mFns,mOpts);%xisthebestsolutionfoundx%endPopistheendingpopulationendPop%traceisatraceofthebestvalueandaveragevalueofgenerationstraceclfplot(trace(:,1),trace(:,2);holdonplot(lrace(:,1),trace(:,3);%1.etsincreasethepopulationsizebyrunningthedefaults%rand('seed',O)term0ps=100;xendPopbestPoptrace=ga(bounds,evalFn,evalOps,gaOpts,termFns,termOps.selectFn,selectps);%xisthebestsolutionfoundx%endPopistheendingpopulation%endPop%traceisatraceofthebestvalueandaveragevalueofgenerations%trace%Plotthebestovertimeclfplot(trace(:,1),trace(:,2);%Addtheaveragetothegraphholdonplot(lrace(:,1),trace(:,3);4. floatExample.m二元函数例子浮点编码globalbounds%Settingtheseedtothesameforbinaryrand(,seed,156789)%CrossoverOperatorsxFns='arithXoverHeuristicXoverSimpleXover'xpts=11O;13;10;%MutationOperatorsmFns='boundaryMutationmultiNonUnifMutationnonUnifMutationUnifMInation'mpts=200;32003;22003;200;%TerminationOperatorstermFns=,maxGenTerm,;IermOps=200;%200Generations%SelectionFunctionSelectFn=,normGeomSelect'SelectOps=10.08J;%EvaluationFunctionevalFn=tgaMichEva;evalps=;%Boundsonthevariablesbounds=-312.1;4.15.81;%GAOptionsepsilonfloat/binardisplaygapts=1e-611;%Generateanintializepopulationofsize20StartPop=iniializega(20,bounds,'gaMichEva,1e-61)xendPopbestPoptracel=ga(bounds,evalFn,evalOps,s(artPop,gaOpts,.termFns,termps,selectFn,selectOps,xFns,xOpts,mFns,mpts);%xisthebestsolutionfoundx%endPopistheendingpopulationendPop%bestPopisthebestsolutiontrackedovergenerationsbestPop%Plotthebestovertimeclfplot(trace(:,1),trace(:,2);%Addtheaveragetothegraphholdonplot(lrace(:,1),lrace(:,3);%1.etsincreasethepopulationsizebyrunningthedefaultsxendPopbestPoptrace=ga(bounds,evalFn,evalOps,gaOpts);%xisthebestsolutionfoundx%endPopistheendingpopulationendPop%bestPopisthebestsolutiontrackedovergenerationsbestPop%Plotthebestovertimeclfplot(lrace(:J),trace(:,2);%Addtheaveragetothegraphholdonplot(lrace(:,1),trace(:,3);5 .求解货郎担问题(TSP)34货郎担问题近几年来,基于遗传算法方法求解货觊担(TSP)问题的研究相当活跃。例如DavidB.FogelM,GrefenStetten£,GoldbergM,等,在遗传算法研究中,TSP问题已祓广泛地用于评价不同的遗传操作及选择机制的性能,之所以如此,主要有以下几个方面的原因：(1)TSP问题於一个典型的、易于描述却难以处理的NP完全问题。有效地解决TSP问题在可计算理论上有着重要的理论价值。<2)TSP问题是诸多领域内出现的多种复杂问题的集中概括和简化形式。因此,快速、有效地解决TSP问题有着极高的实际应用价值；<3)TSP问题因其典型性已成为各种启发式的搜索、优化算法的间接比较标准(如神经网络优化法、列表导优(TABU)法、模拟退火法等)，而遗传算法方法就其本质来说,主要是处理复杂问题的一种鲁讳性强的启发式随机搜索算法,因此遗传算法在TSP问题求解方面的应用研究,对于构造合适的遗传算法框契、建立有效的遗传操作以及有效地解决TSP问题等有着多方面的重要意义。TSP问题描述十分简单,简言之就是寻找一条最短的遍历”个城市的路径,或者说搜索整数子集X=1,2,h(X的元素表示对“个城市的编号)的一个排列KX=刖,使Td=Ed+d(a,u.)(3.9)1取最小值,式中的d(",皿C表示城市V1到城市”的距离。OrderBasedExample.m6 .求解非线性规划问题maxf(x)s.t.gi(x)<=0,i=l,.,mhi(x)=0,i=m+l,.,nxeQ?不可行的后代？1.Q拒绝策略IQa修复策略改进遗传算子策略Ca惩罚策略e.g.minf(x)=(x-2)2+(X2-l)2s.t.g1(x)=x-2x2+1>=0g2(x)=x24-X22+1>=0分析：取加法形式的适值函数：val(x)=f(x)+p(x)惩罚函数P(X)由两部分组成，可变乘法因子和违反约束乘法，其表达式如下：O若X可行P(X)=g1(x)其它J=I其中ri是约束i的可变惩罚系数。步骤如下：functionsol,eval=f552(sol,options)xl=sol(l);x2=sol(2);rl=0.l;r2=0.8;%约束条件gl=xl-2*x2+l;g2=xl24-x2.2+l;%加惩罚项的适值if(gl>=0)<fc(g2>=0)eval=(xl-2)2+(x2-l)2;elseeval=(x1-2).2+(x2-1).2+1*gl+r2*g2;endeval=-eval;%维数n=2%设置参数边界bounds=ones(2,l)*r-I；%?%遗传算法优化p,endPop,bestSols,trace=ga(bounds,'f5521);P%性能跟踪plot(trace(:,l),trace(:,3),b-')holdonPlOI(IraCe(:,1),IraCe(:,2),T-')XlabelCGeneration');ylabel('Fittness,);Iegendc解的变化？种群平均值的变化)；