遗传算法及其matlab的应用优秀PPT.ppt

《遗传算法及其matlab的应用优秀PPT.ppt》由会员分享，可在线阅读，更多相关《遗传算法及其matlab的应用优秀PPT.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数学建模专题之遗传算法 主创：徐朋 沈若尧 杨梦出日期：2014年7月19日 报告提纲n一、遗传算法原理n二、遗传算法本身n三、遗传算法程序n四、遗传算法应用1、遗传算法基本原理 遗传算法类似于自然进化，通过作用于种群中个体的染色体上的基因，找寻好的染色体来求解问题。与自然界相像遗传算法对求解问题的本身一窍不通，它所须要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体通过繁殖有更多的机会传个下一代。个体 解 染色体 解的编码 适应性 适应函数值 繁殖（交叉）通过交叉原则产生一组新的解 种群 选定的一组解一、遗传算法原理2、基本遗传算法的组成 （1）编码 GA

2、是通过某种编码机制把对象抽象为由特定符号按确定依次排成的串。正如探讨生物遗传是从染色体着手，而染色体则是由基因排成的串。SGA运用二进制串进行编码。（2）解码 解码的目的是为了将不直观的二进制数据串还原成十进制 （3）交配 “交配运算”是运用单点或多点进行交叉的算子 （4）突变 “突变运算”是运用基因位进行基因突变，避开在算法迭代后期出现种群过早收敛。遗传算法理论（5）倒位 倒位是指一个染色体某区段正常排列依次发生180度的颠倒，造成染色体内的DNA序列重新排列，它包括臂内倒位和臂间倒位。（6）个体适应度评估 个体适应度大的个体更简洁被遗传给下一代。通常，求目标函数最大值的问题可以干脆把目标函

3、数作为未检测个体适应度大小的函数。遗传算法理论（7）复制 复制运算是依据个体适应度大小确定其下代遗传的可能性。若设种群个体总数为 ，个体 的适应度为 ，则个体 被选的概率 遗传算法理论（8）轮盘选择法 轮盘选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n，个体i 的适应度为 Fi，则个体i 被选中遗传到下一代群体的概率为：遗传算法理论 轮盘选择法的实现步骤（1）计算群体中全部个体的适应度函数值（须要解码）；（2）利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；（3）接受模拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下

4、一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。3、遗传算法的特点和优势 遗传算法总是在找寻优解,而不像图搜寻那样并非总是要求优解,而一般是设法尽快找到解,所以遗传算法又是一种优化搜寻算法。遗传算法的搜寻过程是从空间的一个点集(种群)到另一个点集(种群)的搜寻,而不像图搜寻那样一般是从空间的一个点到另一个点地搜寻。因而它实际是一种并行搜寻,适合大规模并行计算,而且这种种群到种群的搜寻有实力跳出局部最优解。4、遗传算法的改进 遗传欺瞒问题：在遗传算法进化过程中，有时会产生一些超常的个体，这些个体因竞争力太突出而限制了选择运算过程，从而影响算法的全局优化性能，导致算法获得某个局部最优

5、解。二、遗传算法本身n1、编码n 设某一参数的取值范围为（L，U），运用长度为k的二进制编码表示该参数，则它共有 种不同的编码，该参数编码时的对应关系为n 000000000000000000=0 Ln 000000000000000001=1 L+n 000000000000000010=2 L+2n .n n =编码时如何确定二进制数串的位数m 为二进制数串位数；为要求的精度2、解码设某一个体的二进制编码为 ，则对应的解码公式为 3、交配n（1）交配形式 S1=01001011,S2=10010101交换其后四位基因，如图所示，交换后S1=01000101，S2=10011011，可以看成

6、原染色体S1和S2的子染色体。01001011 10010101 01000101 10011011 图：染色体基因交配范例（2）交配的确定n交配染色体数量的确定n 交配染色体的数量等于染色体总量乘以交配概率。n交配染色体对象的确定n 假如有m个个体，就用计算机产生【0,1】区间的m个随机数，在随机数中小于交配率的两两进行交配。4、突变 突变就是变更染色体某个突变就是变更染色体某个(些些)位上的基位上的基因，因，二进制编码，就是二进制编码，就是0 变变1，1变变0。例如例如,设染色体设染色体 s=11001101将其第三位上的将其第三位上的0变为变为1,即即 s=11001101 111011

7、01=s。s也可以看做是原染色体也可以看做是原染色体s的子代染色的子代染色体。体。5、个体适应度评估n（1）评价个体适应度 将染色体串进行反编码（解码），转换成真实值，即 ，k=1,2,3,.评价目标函数f()。将目标函数值转换成适应度。eval（）=f()，k=1,2,3,.2）依照适应度值进行新种群的复制 计算染色体 的适应度值 eval（）=f（），k=1,2,3,计算种群的适应度值总和 F=计算每个染色体被复制的概率 计算每个染色体被复制的累积概率 （3）、新种群复制 新种群的复制依照轮盘选择法来计算，利用计算机模拟轮盘选择法，假设计算机产生10个0,1区间的随机数，假如随机数大于 小

8、于 ,所以 被选中；综上轮盘选择法的机理：染色体的适应度大意味着 ,区间跨度就大，随机数发生器产生的匀整随机数就有更或许率落在此区间内，这样具有较或许率的染色体更有机会复制制下一代。三、遗传算法的程序n1、遗传算法的设计原则n2、遗传算法工具箱GAn3、代码源程序1、遗传算法的设计原则遗传算法基本流程框图 生成初始种群计算适应度选择-复制交叉变异生成新一代种群终止?结束2算法中的一些限制参数n（1）种群的规模 n 种群规模太小，很明显会出现近亲交配现象，产生变态基因；种群规模太大，结果难以收敛且奢侈资源，稳健性下降。种群规模建议值为0100。n（2）变异概率n 变异概率太小，种群多样性下降太快

9、，易导致有效基因丢失且不易修补；变异概率太大，虽然可以保证多样性，但是高阶模式被破坏概率增加。所以变异概率一般取0.00010.2。（3）交配概率 交配概率是生成新种群最重要的手段，交配概率太大易破坏已有有利模式，随机性增大，易错失最优个体；交配概率太小不能有效更新种群。所以交配概率一般取0.40.99。（4）进化代数 进化代数越小，算法不易收敛，种群还没有成熟；代数太大，算法已娴熟，不能再接着收敛，接着进化没有意义。所以进化代数一般取100500。（5）种群初始化 初始种群的生成是随机的。赐予初始种群之前，应先进行区间估计，以免初始种群偏离全局最优解的编码空间，也可以为算法减轻负担。2、遗传

10、算法工具箱GAn （1）GA工具箱核心函数用法n 1函数 ga （对目标函数进行遗传计算）n 函数 ga 的语法格式n x,fval,reason=ga(fitnessfun,nvars,options)n 其中，x为经过遗传进化以后自变量最佳染色体返回值；fval 为最佳染色体的适应度；reason为算法停止的缘由；fitnessfun 为适应度句柄函数；nvars 为目标函数自变量的个数；options 为算法的属性设置，该属性是通过函数gaoptimset赐予的。n n2函数 gaoptimset 函数gaoptimset 的语法格式为Options=gaoptimset(Propert

11、yName1,PropertyValue1,PropertyName2,PropertyValue2.)函数 gaoptimset 实现功能为，设置遗传算法的参数和句柄函数。3Genetic Algorithm and Direct Search Toolbox 适应度函数设计实例1 求解目标函数的最小值，语法格式如下：function f=fitnessfcn(x)x为自变量向量 f=f(x);实例2 假如有约束条件（包含自变量的取值范围），对于求解函数最小值问题，可以用如下语法形式：function f=fitnessfcn(x)if(x3)表示有约束 x-1和x=-3，f=inf;els

12、e f=f（x）;end 实例3 假如有约束条件（包括自变量的取值范围），对于求解函数最大值问题，可以运用如下语法格式：function f=fitnessfcn(x)If(x3)f=inf;else f=-f(x);留意，这里是f=-f（x）而不是f=f(x)end 若目标函数作为适应度函数，则最终得到的目标函数值为 fval ,而不是 fval。3、代码源程序n（1）编码 function bin_gen,bits=encoding(min_var,max_var,scale_var,popsize)bits=ceil(log2(max_var-min_var)./scale_var);b

13、in_gen=randint(popsize,sum(bits);n（2）解码n function var_gen,fitness =decoding(funname,bin_gen,bits,min_nvar,max_var)nnum_var=length(bits);npopsize=size(bin_gen,1);nscale_dec=(max_var-min_var)./(2.bits-1);nbits=cumsum(bits);nbits=0 bits;nfor i=1:num_varnbin_vari=bin_gen(:,bits(i)+1:bits(i+1);nvari=sum(

14、ones(popsize,1)*2.(size(bin_vari,2)-1:-n1:0).*bin_vari,2).*scale_dec(i)+min_var(i);nendnvar_gen=var1,:;nfor i=1:popsizenfitness(i)=eval(funname,(var_gen(i,:);nendn解码函数的关键在于先由二进制数求得对应的十进制数D,并依据下式求得实际决策变量值X:nX=D scale_dec+min_varn（3）选择nfunction evo_gen,best_indiv,max_fitness =selection(old_gen,fit-nne

15、ss)npopsize=length(fitness);nmax_fitness,index1 =max(fitness);min_fitness,index2 =nmin(fitness);nbest_indiv=old_gen(index1,:);nindex=1:popsize ;index(index1)=0;index(index2)=0;nindex=nonzeros(index);nevo_gen=old_gen(index,:);nevo_fitness=fitness(index,:);nevo_popsize=popsize-2;nps=evo_fitness/sum(ev

16、o_fitness);npscum=cumsum(ps);nr=rand(1,evo_popsize);nselected=sum(pscum*ones(1,evo_popsize)ones(evo_pop-nsize,1)*r)+1;nevo_gen=evo_gen(selected,:);在该算子中,接受了最优保存策略和比例选择法相结合的思路,即首先找出当前群体中适应值最高和最低的个体,将最佳个体best_indiv 保留并用其替换掉最差个体。为保证当前最佳个体不被交叉、变异操作所被坏,允许其不参与交叉和变异而干脆进入下一代。然后将剩下的个体evo_gen 按比例选择法进行操作。所谓比例选

17、择法,也叫轮盘算法,是指个体被选中概率与该个体的适应值大小成正比。将这两种方法相结合的目的是:在遗传操作中,不仅能不断提高群体的平均适应值,而且能保证最佳个体的适应值不减小。（4）交叉n function new_gen=crossover(old_gen,pc)n nouse,mating=sort(rand(size(old_gen,1),1);nmat_gen=old_gen(mating,:);npairs=size(mat_gen,1)/2;nbits=size(mat_gen,2);ncpairs=rand(pairs,1)pc;ncpoints=randint(pairs,1,1

18、,bits);ncpoints=cpairs.*cpoints;nfor i=1:pairsn new_gen(2*i-2*i,:)=mat_gen(2*i-1 2*i,1:ncpoints(i)mat_gen(2*I 2*i-1,cpoints(i)+1:bits);nend（5）变异nfunction new_gen=mutation(old_gen,pm)nmpoints=find(rand(size(old_gen)pm);nnew_gen=old_gen;nnew_gen(mpoints)=1-old_gen(mpoints);（6）注释 取种群大小popsize,搜寻精度scale

19、_var,交叉概率pc,变异概率pm。下界(min_var)上界(max_var)搜寻精度scale_var 长度bits 初始种群bin_gen 最佳个体best_indiv 个体编码串cpairs 交叉点cpoints 变异点mpoints四、遗传算法的应用1、遗传算法的应用领域（1）组合优化 （2）函数优化（3）自动限制 （4）生产调度（5）图像处理 （6）机器学习（7）人工生命 （8）数据挖掘 2、应用举例案例一 无约束目标函数最大值遗传算法求解策略 max f(x)=200 ，x -2,2 主程序nclc;nclear all;nclose all;nglobal BitLength

20、nglobal boundsbeginnglobal boundsendnbounds=-2 2;nprecision=0.0001;nboundsbegin=bounds(:,1);nboundsend=bounds(:,2);nBitLength=ceil(log2(boundsend-boundsbegin)./precision);npopsize=50;nGenerationnmax=200;npcrossover=0.90;npmutation=0.09;npopulation=round(rand(popsize,BitLength);nFitvalue,cumsump=fitn

21、essfun(population);nGeneration=1;nwhile GenerationGenerationnmax+1n for j=1:2:popsizenseln=selection(population,cumsump);nscro=crossover(population,seln,pcrossover);nscnew(j,:)=scro(1,:);nscnew(j+1,:)=scro(2,:);nsmnew(j,:)=mutation(scnew(j,:),pmutation);nsmnew(j+1,:)=mutation(scnew(j+1,:),pmutation)

22、;n endnpopulation=smnew;nFitvalue,cumsump=fitnessfun(population);nfmax,nmax=max(Fitvalue);nfmean=mean(Fitvalue);nymax(Generation)=fmax;nymean(Generation)=fmean;nx=transform2to10(population(nmax,:);nxx=boundsbegin+x*(boundsend-boundsbegin)/(power(boundsend),BitLength)-1);nxmax(Generation)=xx;nGenerat

23、ion=Generation+1;nendnGeneration=Generation-1;nBestpopulation=xx;nBesttargetfunvalue=targetfun(xx);nfigure(1);nhand1=plot(1:Generation,ymax);nset(hand1,linestyle,-,linewidth,1.8,marker,*,markersize,6)nhold on;nhand2=plot(1:Generation,ymean);nset(hand2,color,r,linestyle,-,linewidth,1.8,.nmarker,h,mar

24、kersize,6)nxlabel(进化代数);ylabel(最大/平均适应度);xlim(1 Generationnmax);nlegend(最大适应度平均适应度);nbox off;hold off;nfunction scro=crossover(population,seln,pc)nBitLength=size(population,2);npcc=IfCroIfMut(pc);nif pcc=1nchb=round(rand*(BitLength-2)+1;nscro(1,:)=population(seln(1),1:chb)population(seln(2),chb+1:Bi

25、tLength);nscro(2,:)=population(seln(2),1:chb)population(seln(1),chb+1:BitLength);nelsenscro(1,:)=population(seln(1),:);nscro(2,:)=population(seln(2),:);nendnfunction Fitvalue,cumsump=fitnessfun(population)nglobal BitLengthnglobal boundsbeginnglobal boundsendnpopsize=size(population,1);nfor i=1:popsi

26、zenx=transform2to10(population(i,:);nxx=boundsbegin+x*(boundsend-boundsbegin)/(power(boundsend),BitLength)-1);nFitvalue(i)=targetfun(xx);nendnFitvalue=Fitvalue+230;nfsum=sum(Fitvalue);nPperpopulation=Fitvalue/fsum;ncumsump(1)=Pperpopulation(1);nfor i=2:popsizen cumsump(i)=cumsump(i-1)+Pperpopulation

27、(1);nend ncumsump(popsize)=1;ncumsump=cumsump;nfunction snnew=mutation(snew,pmutation)nBitLength=size(snew,2);nsnnew=snew;npmm=IfCroIfMut(pmutation);nif pmm=1n chb=round(rand*(BitLength-1)+1;n snnew(chb)=abs(snew(chb)-1);nend程序运行结果nx=1.3749 y=183.1409案例二 多约束非线性规划问题的求解 n例：运用工具箱GA解决多约束非线性规划问题 min f(x)=()s.t.1.5+=0 -0|g210)n f=100;nElse nf=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);nend n运行结果：=-9.1208 =1.0867 BestFval=0.0327提问与被提问问题n提问问题1、模拟退火算法有什么缺陷和局限性？2、轮盘选择法的机理。n被提问问题1、遗传算法倒位的条件？答：倒位类似于突变，突变概率本身就很小，所以倒位概率也很小。