Matlab与遗传算法

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Matlab与遗传算法,1,遗传算法（Genetic Algorithm, GA）最先是由美国Mic-,hgan大学的John Holland于1975年提出的。遗传算法是,模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算,模型。它的思想源于生物遗传学和适者生存的自然规律，,是具有“生存+检测”的迭代过程的搜索算法。遗传算法,以一种群体中的所有个体为对象，并利用随机化技术指,导对一个被编码的参数空间进行高效搜索。其中，选择、,交叉和变异构成了遗传算法的遗传操作；,参数编码、初始,群体的设定、适应度函数的设计、遗传操作设计、控制参,数设定,等5个要素组成了遗传算法的核心内容。,遗传算法简介,2,. 汽车设计，包括材料选择、多目标汽车组件设计、减轻重量等。, 机电系统设计。, 分布计算机网络的拓扑结构。, 电路设计，此类用途的遗传算法叫做进化电路。, 电子游戏设计，例如计算平衡解决方案。, 机器智能设计和机器人学习。, 模糊控制系统的训练。, 移动通讯优化结构。, 时间表安排，例如为一个大学安排不冲突的课程时间表。, 旅行推销员问题., 神经网络的训练，也叫做神经进化。,适用的领域,3,遗传算法是一种基于生物自然选择与遗传机理的随机,搜索算法，与传统搜索算法不同，遗传算法从一组随机产,生的称为“种群(Population)”的初始解开始搜索过程。种,群中的每个个体是问题的一个解，称为“染色体(chromos,ome)”。染色体是一串符号，比如一个二进制字符串。这,些染色体在后续迭代中不断进化，称为遗传。在每一代中,用“适应度(fitness)”来测量染色体的好坏，生成的下一代染,色体称为后代（offspring）。后代是由前一代染色体通过交配,(crossover)或者突变（mutation）运算形成的。,在新一代形成过程中，根据适度的大小选择部分后代，淘,汰部分后代。从而保持种群大小是常数。适应度高的染色体,被选中的概率较高，这样经过若干代之后，算法收敛于最,好的染色体，它很可能就是问题的最优解或次优解。,4,遗传算法的实现步骤,(1),编码,：GA在进行搜索之前先将解空间的解数据表示成,遗传空间的基因型串结构数据，这些串结构数据的不同组,合便构成了不同的点。,(2),初始群体的生成,：随机产生N个初始串结构数据，每个,串结构数据称为一个个体，N个个体构成了个群体。,GA以这N个串结构数据作为初始点开始迭代。,(3),适应度评估检测,：适应性函数表明个体或解的优劣性。,对于不同的问题，适应性函数的定义方式也不同。,(4),选择新种群,：选择的目的是为了从当前群体个选出优良,的个体，使它们有机会作为父代为下一代繁殖子孙。遗传,算法通过选择过程体现这一思想，进行选择的原则是适应,性强的个体为下一代贡献一个或多个后代的概率大。选择,实现了达尔文的适者生存原则。,5,(5),交配,：交配是遗传算法中最主要的遗传操作。通过,交配可以得到新一代个体，新个体组合了其父辈个体,的特性。,(6),突变,：突变首先在群体中随机选择一个个体，对于选中,的个体以一定的概率随机地改变串结构数据中某个串的值。,同生物界一样，GA中变异发生的概率很低，通常取值在,0.0010.01之间。,6,例子： 求,（1）编码与解码生成种群,随机产生10个个体，其染色体如下,U1=,U2=,U3=11111000110,U4=1101101 1001,U5=11001101000,U6=1111100 1001,U7=11101011101,U8=0001100 1100,U9=1111100 1101,U10=11111101010,7,（2）评价个体适应度,将编码转化为实际值，评价目标函数,求,一般将目标函数就设为适应度,例如求得,8,1. 求得各个染色体的适应度,2. 求种群的适应度总和,3. 计算每个染色体被复制的概率,4. 计算每个染色体被复制的累积概率,9,（3）选择新种群,产生10个随机数：,0.301431，0.322062，0.766503， 0.881893，0.350871,0.538392， 0.177618，0.343242，0.032685，0.197577,选中染色体,U4,U4,U8,U9,U4,U7,U2,U4,U1,U2,10,最终新的染色体为,新的染色体,编码,选中染色体,U1,1101101 1001,U4,U2,1101101 1001,U4,U3,0001100 1100,U8,U4,1111100 1101,U9,U5,1101101 1001,U4,U6,11101011101,U7,U7,U2,U8,1101101 1001,U4,U9,U1,U10,U2,11,（4）新种群交配,1.交配染色体数量：染色体总量乘以交配率,2.5=2,2. 交配染色体对象确立,产生10个随机数，小于交配率所在位置的染色体被选入。,3. 在交配池交配,随机产生0至32间的一个整数，若产生为1，则在二进制的,第二个位置开始分割交换生成新的子辈染色体,U5 =1101101 1001,U7=,12,（5）突变,1. 基因突变的个数：基因数乘以突变概率,约4个基因发生突变,2. 突变基因的确定,产生330个随机数（取值在0，1之间）找到小于突变概率的位,置，除以每个染色体的基因数，找到突变基因。,基因位置,染色体位置,基因位数,随机数,105/33=46,4,6,0.009857,164/33=532,5,32,0.003113,199/33=71,7,1,0.000946,329/33=1032,10,32,0.001282,13,最终新种群染色体,U1,1101101 1001,U2,1101101 1001,U3,0001100 1100,U4,11111,1,0 1101,U5,101110010,1,0,U6,11101011101,U7,1,101101 1001,U8,1101101 1001,U9,U10,001110010,1,0,新种群同样计算适应度，重复上面的步骤。依次迭代，在第,451代找到最大目标函数值的染色体,Ubest=1111100 1111,解码得到实际值,14,其适应度或者最优值为,eval(U)=38.818208,中止的条件有以下几个,1. 进化次数限制；,2. 计算耗费的资源限制（例如计算时间、计算占用的内存等）；,3. 一个个体已经满足最优值的条件，即最优值已经找到；,4. 适应度已经达到饱和，继续进化不会产生适应度更好的个体；,5. 人为干预；,6. 以及以上两种或更多种的组合。,15,Matlab实现这一过程的命令,1）x,fval,reason=ga(fitnessfun, nvars, options),x为经过遗传进化以后自变量最佳染色体的返回值，fval为最佳,染色体的适应度，reason为算法停止原因。,fitnessfun为适应度函数，nvars为目标函数自变量的个数，,options为算法的属性设置，可以通过gaoptimset赋值。,2）options= gaoptimset(Propertyname1,propertyvalue,),16,属性名,默认值,实现功能,PopInitRange,0,1,初始种群生成区间,PopulationSize,20,种群规模,CrossoverFraction,0.8,交配概率,MigrationFraction,0.2,变异概率,Generations,100,超过进化代数时算法停止,TimeLimit,inf,超过运算时间限制时停止,FitnessLimit,-inf,最佳个体等于或小于适应度阈值时算法停止,StallGenLimit,50,超过连续代数不进化算法停止,StallTimeLimit,20,超过连续时间不进化算法停止,InitialPopulation, ,初始化种群,PlotFcns, ,绘图函数,17,3. x,fval,reason,output,final_pop=ga(fitnessfun,nvars),其中final_pop返回的是本次运行得到的最后种群，可以再将,final_pop作为函数ga的初始种群,options=gaoptimset(initialpopulation,final_pop),x,fval=ga(fitnessfun, nvars, options),18,运用GA工具箱求解最优化问题,T=100;,optionsorigin=gaoptimset(generations,T/2);,x,fval,reason,output,final_pop=ga(chl4_2f, 2, optionsorigin);,options1=gaoptimset(generations,T/2,initialpopulation,final_pop,plotfcns,gaplotbestf);,x,fval,reason,output,final_pop=ga(chl4_2f, 2, options1);,bestx=x,bestfval=fval,19,function f=chl4_2f(x),g1=1.5+x(1)*x(2)-x(1)-x(2);,g2=-x(1)*x(2);,if (g10|g20),f=100;,else,f=exp(x(1)*(4*x(1)2+2x(2)2+4x(1)*x(2)+2*x(2)+1;,end,20,遗传算法的优点,遗传算法的优点：1. 与问题领域无关切快速随机的搜索能力。2. 搜索从群体出发，具有潜在的并行性，可以进行多个个体的,同时比较.3. 搜索使用评价函数启发，过程简单4. 使用概率机制进行迭代，具有随机性。5. 具有可扩展性，容易与其他算法结合。,21,clc;,Clear all;,Global bitlength,Golbal boundsbegin,Global boundsend,Bounds=-2 2;,Precision=0.0001;,Boundbegin=bounds(:,1);,Boundsend=bounds(:,2);,bitlength=ceil(log2(boundsend-boundsbegin)./precision);,Popsize=50;,Generationnmax=12;,Pcrossover=0.90;,Pmutation=0.09;,求,22,Population=round(rand(popsize,bitlength);,fitvalue, cumsump=fitnessfun(population);,Generation=1;,While generationgenerationnmax+1,for j=1:2:popsize,seln=selection(population, cumsump);,scro=crossover(population,seln,pcrossover);,scnew(j,:)=scro(1,:);,scnew(j+1,:)=scro(2,:);,smnew(j,:)=mutation(scnew(j,:),pmutation);,end,Population=smnew,fvalue,cumsump=fitnessfun(population);,fmax,nmax=max(fitvalue);,Fmean=mean(fitvalue);,Ymax(generation)=fmax;,23,Ymean(generation)=fmean;,X=transform2to10(population(nmax,:);,Xx=boundsbegin+x*(boundsend-boundsbegin)/(power,(boundsend),bitlength)-1);,xmax(generation)=xx;,Generation=generation+1;,End,Generation=generation-1;,Bestpopulation=xx,Besttargetfunvalue=targetfun(xx);,Figure(1);,Hand1=plot(1:generation,ymax);,Set(hand1,linestyle,-,linewidth,1.8,marker,*,markersize,6);,Hold on,24,Hand2=plot(1:generation,ymean);,Set(hand2,linestyle,-,linewidth,1.8,marker,h,markersize,6),Xlabel(进化代数);ylabel(最大/平均适应度）；,xlim(1 generationnmax);,Legend(最大适应度，平均适应度);,Box off;hold off,25,Function scro=crossover(population,seln,pc);,Bitlength=size(population,2);,Pcc=ifcroifmut(pc);,If pcc=1,chb=round(rand*（bitlength-2)+1;,scro(1,:)=,population(seln(1),1:chb) population(seln(2),chb+1:bitlength) ;,scro(2,:)=,population(seln(2),1:chb) population(seln(1),chb+1:bitlength) ;,Else,scro(1,:)=population(seln(1),:);,scro(2,:)=population(seln(2),:);,end,26,Function fitvalue,cumsump=fitnessfun(population),Global bitlength,Golbal boundsbegin,Global boundsend,Popsize=size(population,1);,For i=1:popsize,x=transform2to10(population(i,:);,Xx=boundsbegin+x*(boundsend-boundsbegin)/(power,(boundsend),bitlength)-1);,Fitvalue(i)=targetfun(xx);,End,Fitvalue=fitvalue+230;,Fsum=sum(fitvalue);,Pperpopulation=fitvalue/fsum;,适应度函数,27,For i=2:popsize,cumsump(i)= cumsump(i-1)+pperpopulation(i);,End,Cumsump=cumsump;,28,新种群变异函数,Function snnew=mutation(snew,pmutation);,Bitlength=size(snew,2);,Snnew=snew;,Pmm=ifcroifmut(pmutation);,If pmm=1,chb=round(rand*(bitlength-1)+1;,snnew(chb)=abs(snew(chb)-1);,end,判断遗传运算是否需要进行交叉和变异的函数,Function pcc=ifcroifmut(mut0rcro);,Test(1:100)=0;,l=round(100*mut0rcro);,Test(1:l)=1;,N=round(rand*99)+1;,Pcc=test(n);,29,新种群选择函数,Function seln=selection(population,cumsump);,For i=1:2,r =rand;,prand=cumsump-r;,j=1;,while prand(j)0,j=j+1;,end,seln(i)=j,end,30,将二进制数转为十进制数函数,Function x=transform2to10(population),Bitlength=size(population,2);,X=population(bitlength),For i=1:bitlength-1,x=x+population(bitlength-i)*power(2,i);,end,目标函数,Function y=targetfun(x),Y=200*exp(-0.05*x).*sin(x);,31,遗传算法的缺点,1、遗传算法的编程实现比较复杂,首先需要对问题进行编码,找到最优解之后还需要对问题进行解码,2、另外三个算子的实现也有许多参数,如交叉率和变异率,并且这些参数的选择严重影响解的品质,而目前这些参数的选,择大部分是依靠经验. 3、算法对初始种群的选择有一定的依赖性，能够结合一些,启发算法进行改进。 4、算法的并行机制的潜在能力没有得到充分的利用，这也,是当前遗传算法的一个研究热点方向。,32,