遗传算法及其MATLAB程序代码

遗传算法及其MATLAB实现主要参考书：MATLAB6.5辅助优化计算与设计飞思科技产品研发中心编著电子工业出版社2003.1遗传算法及其应用陈国良等编著人民邮电出版社1996.6主要内容：遗传算法简介遗传算法的MATLAB实现应用举例在工业工程中,许多最优化问题性质十分复杂,很难用传统的优化方法来求解.自1960年以来,人们对求解这类难解问题日益增加.一种模仿生物自然进化过程的、被称为“进化算法（evolutionaryalgorithm）”的随机优化技术在解这类优化难题中显示了优于传统优化算法的性能。目前，进化算法主要包括三个研究领域：遗传算法、进化规划和进化策略。其中遗传算法是迄今为止进化算法中应用最多、比较成熟、广为人知的算法。一、遗传算法简介遗传算法（GeneticAlgorithm,GA）最先是由美国Mic-hgan大学的JohnHolland于1975年提出的。遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的思想源于生物遗传学和适者生存的自然规律，是具有“生存+检测”的迭代过程的搜索算法。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定等5个要素组成了遗传算法的核心内容。遗传算法的基本步骤：遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法，与传统搜索算法不同，遗传算法从一组随机产生的称为“种群(Population)”的初始解开始搜索过程。种群中的每个个体是问题的一个解，称为“染色体(chromosome)”。染色体是一串符号，比如一个二进制字符串。这些染色体在后续迭代中不断进化，称为遗传。在每一代中用“适值(fitness)”来测量染色体的好坏，生成的下一代染色体称为后代（offspring）。后代是由前一代染色体通过交叉(crossover)或者变异（mutation）运算形成的。在新一代形成过程中，根据适度的大小选择部分后代，淘汰部分后代。从而保持种群大小是常数。适值高的染色体被选中的概率较高，这样经过若干代之后，算法收敛于最好的染色体，它很可能就是问题的最优解或次优解。主要步骤如下所示：(1)编码：GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点。(2)初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了—个群体。GA以这N个串结构数据作为初始点开始迭代。(3)适应性值评估检测：适应性函数表明个体或解的优劣性。对于不同的问题，适应性函数的定义方式也不同。(4)选择：选择的目的是为了从当前群体个选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的适者生存原则。(5)交叉：交叉操作是遗传算法中最主要的遗传操作。通过交叉操作可以得到新一代个体，新个体组合了其父辈个体的特性。交叉体现了信息交换的思想。(6)变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样，GA中变异发生的概率很低，通常取值在0.001~0.01之间。变异为新个体的产中提供了机会。实际上，遗传算法中有两类运算：●遗传运算：交叉和变异●进化运算：选择GA的计算过程流程图遗传算法的特点GA是对问题参数的编码组进行计算，而不是针对参数本身。GA的搜索是从问题解的编码组开始搜素、而不是从单个解开始。GA使用目标函数值（适应度）这一信息进行搜索，而不需导数等其他信息。GA算法使用的选择、交叉、变异这三个算子都是随机操作，而不是确定规则。举例图解说明计算流程二、遗传算法的MATLAB实现需要如下主函数：编码和种群生成function[pop]=initializega(num,bounds,evalFN,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%orderOps,precistheprecisionofthevariablesdefaults[1e-61]交叉function[c1,c2]=arithXover(p1,p2,bounds,Ops)%ArithcrossovertakestwoparentsP1,P2andperformsaninterpolation%alongthelineformedbythetwoparents.%%function[c1,c2]=arithXover(p1,p2,bounds,Ops)%p1-thefirstparent([solutionstringfunctionvalue])%p2-thesecondparent([solutionstringfunctionvalue])%bounds-theboundsmatrixforthesolutionspace%Ops-Optionsmatrixforarithcrossover[gen#ArithXovers]选择normGeomSelect：NormGeomSelectisarankingselectionfunctionbasedonthenormalizedgeometricdistribution.（基于正态分布的序列选择函数）变异function[newPop]=normGeomSelect(oldPop,options)%NormGeomSelectisarankingselectionfunctionbasedonthenormalized%geometricdistribution.%%function[newPop]=normGeomSelect(oldPop,options)%newPop-thenewpopulationselectedfromtheoldPop%oldPop-thecurrentpopulation%options-optionstonormGeomSelect[genprobability_of_selecting_best]一些辅助函数：f2b：Returnthebinaryrepresentationofthefloatnumberfval（将浮点数转化为二进制数）b2f：Returnthefloatnumbercorresponingtothebinaryrepresentationofbval.（将二进制数转化为浮点数）nonUnifMutation：Nonuniformmutationchangesoneoftheparametersoftheparentbasedonanon-uniformprobabilitydistribution.ThisGaussiandistributionstartswide,andnarrowstoapointdistributionasthecurrentgenerationapproachesthemaximumgeneration.（基于非均一概率分布进行非均一变异）maxGenTerm：Returns1,i.e.terminatestheGAwhenthemaximal_generationisreached.（当迭代次数大于最大迭代次数时，终止遗传算法，返回为1，否则返回为0。）roulette：rouletteisthetraditionalselectionfunctionwiththeprobabilityofsurvivingequaltothefittnessofi/sumofthefittnessofallindividuals三、应用举例1.计算下列函数的最大值。functionf=my_first_multi(x)f(1)=x(1)^4-10*x(1)^2+x(1)*x(2)+x(2)^4-(x(1)^2)*(x(2)^2);f(2)=x(2)^4-(x(1)^2)*(x(2)^2)+x(1)^4+x(1)*x(2);程序：fitnessfcn=@my_first_multi;%Functionhandletothefitnessfunctionnvars=2;%Numberofdecisionvariableslb=[-5,-5];%Lowerboundub=[5,5];%UpperboundA=[];b=[];%NolinearinequalityconstraintsAeq=[];beq=[];%Nolinearequalityconstraintsoptions=gaoptimset('ParetoFraction',0.3,'PopulationSize',100,'Generations',200,'StallGenLimit',200,'TolFun',1e-100,'PlotFcns',@gaplotpareto);[x,fval]=gamultiobj(fitnessfcn,nvars,A,b,Aeq,beq,lb,ub,options);