遗传算法及其matlab应用.pptx

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

1、 报告提纲一、遗传算法原理二、遗传算法本身三、遗传算法程序四、遗传算法应用第1页/共47页1、遗传算法基本原理 遗传算法类似于自然进化，通过作用于种群中个体的染色体上的基因，寻找好的染色体来求解问题。与自然界相似遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体通过繁殖有更多的机会传个下一代。个体 解 染色体 解的编码 适应性 适应函数值 繁殖（交叉）通过交叉原则产生一组新的解 种群 选定的一组解一、遗传算法原理第2页/共47页2、基本遗传算法的组成 （1）编码 GA是通过某种编码机制把对象抽象为由特定符号按一定顺序排

2、成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。SGA使用二进制串进行编码。（2）解码 解码的目的是为了将不直观的二进制数据串还原成十进制 （3）交配 “交配运算”是使用单点或多点进行交叉的算子 （4）突变 “突变运算”是使用基因位进行基因突变，避免在算法迭代后期出现种群过早收敛。第3页/共47页遗传算法理论（5）倒位 倒位是指一个染色体某区段正常排列顺序发生180度的颠倒，造成染色体内的DNA序列重新排列，它包括臂内倒位和臂间倒位。（6）个体适应度评估 个体适应度大的个体更容易被遗传给下一代。通常，求目标函数最大值的问题可以直接把目标函数作为未检测个体适应度大小的函数。第

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

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

5、算法的全局优化性能，导致算法获得某个局部最优解。第9页/共47页二、遗传算法本身1、编码 设某一参数的取值范围为（L，U），使用长度为k的二进制编码表示该参数，则它共有 种不同的编码，该参数编码时的对应关系为 000000000000000000=0 L 000000000000000001=1 L+000000000000000010=2 L+2 .111111111111111111=U =第10页/共47页编码时如何确定二进制数串的位数m 为二进制数串位数；为要求的精度第11页/共47页2、解码设某一个体的二进制编码为 ，则对应的解码公式为 第12页/共47页3、交配（1）交配形式 S1

6、=01001011,S2=10010101交换其后四位基因，如图所示，交换后S1=01000101，S2=10011011，可以看成原染色体S1和S2的子染色体。01001011 10010101 01000101 10011011 图：染色体基因交配范例第13页/共47页（2）交配的确定交配染色体数量的确定 交配染色体的数量等于染色体总量乘以交配概率。交配染色体对象的确定 如果有m个个体，就用计算机产生【0,1】区间的m个随机数，在随机数中小于交配率的两两进行交配。第14页/共47页4、突变 突变就是改变染色体某个(些)位上的基因，二进制编码，就是0 变1，1变0。例如,设染色体 s=110

7、01101将其第三位上的0变为1,即 s=11001101 11101101=s。s也可以看做是原染色体s的子代染色体。第15页/共47页5、个体适应度评估（1）评价个体适应度 将染色体串进行反编码（解码），转换成真实值，即 ，k=1,2,3,.评价目标函数f()。将目标函数值转换成适应度。eval（）=f()，k=1,2,3,.第16页/共47页2）依照适应度值进行新种群的复制 计算染色体 的适应度值 eval（）=f（），k=1,2,3,计算种群的适应度值总和 F=计算每个染色体被复制的概率 计算每个染色体被复制的累积概率 第17页/共47页（3）、新种群复制 新种群的复制依照轮盘选择法来

8、计算，利用计算机模拟轮盘选择法，假设计算机产生10个0,1区间的随机数，如果随机数大于 小于 ,所以 被选中；综上轮盘选择法的机理：染色体的适应度大意味着 ,区间跨度就大，随机数发生器产生的均匀随机数就有更大概率落在此区间内，这样具有较大概率的染色体更有机会复制制下一代。第18页/共47页三、遗传算法的程序1、遗传算法的设计原则2、遗传算法工具箱GA3、代码源程序第19页/共47页1、遗传算法的设计原则遗传算法基本流程框图 生成初始种群计算适应度选择-复制交叉变异生成新一代种群终止?结束第20页/共47页2算法中的一些控制参数（1）种群的规模 种群规模太小，很明显会出现近亲交配现象，产生变态基

9、因；种群规模太大，结果难以收敛且浪费资源，稳健性下降。种群规模建议值为0100。（2）变异概率 变异概率太小，种群多样性下降太快，易导致有效基因丢失且不易修补；变异概率太大，虽然可以保证多样性，但是高阶模式被破坏概率增加。所以变异概率一般取0.00010.2。第21页/共47页（3）交配概率 交配概率是生成新种群最重要的手段，交配概率太大易破坏已有有利模式，随机性增大，易错失最优个体；交配概率太小不能有效更新种群。所以交配概率一般取0.40.99。（4）进化代数 进化代数越小，算法不易收敛，种群还没有成熟；代数太大，算法已熟练，不能再继续收敛，继续进化没有意义。所以进化代数一般取100500。

10、（5）种群初始化 初始种群的生成是随机的。赋予初始种群之前，应先进行区间估计，以免初始种群偏离全局最优解的编码空间，也可以为算法减轻负担。第22页/共47页2、遗传算法工具箱GA （1）GA工具箱核心函数用法 1函数 ga （对目标函数进行遗传计算）函数 ga 的语法格式 x,fval,reason=ga(fitnessfun,nvars,options)其中，x为经过遗传进化以后自变量最佳染色体返回值；fval 为最佳染色体的适应度；reason为算法停止的原因；fitnessfun 为适应度句柄函数；nvars 为目标函数自变量的个数；options 为算法的属性设置，该属性是通过函数ga

11、optimset赋予的。第23页/共47页2函数 gaoptimset 函数gaoptimset 的语法格式为Options=gaoptimset(PropertyName1,PropertyValue1,PropertyName2,PropertyValue2.)函数 gaoptimset 实现功能为，设置遗传算法的参数和句柄函数。第24页/共47页3Genetic Algorithm and Direct Search Toolbox 适应度函数设计实例1 求解目标函数的最小值，语法格式如下：function f=fitnessfcn(x)x为自变量向量 f=f(x);实例2 如果有约束条

12、件（包含自变量的取值范围），对于求解函数最小值问题，可以用如下语法形式：function f=fitnessfcn(x)if(x3)表示有约束 x-1和x=-3，f=inf;else f=f（x）;end 第25页/共47页实例3 如果有约束条件（包括自变量的取值范围），对于求解函数最大值问题，可以使用如下语法格式：function f=fitnessfcn(x)If(x3)f=inf;else f=-f(x);注意，这里是f=-f（x）而不是f=f(x)end 若目标函数作为适应度函数，则最终得到的目标函数值为 fval ,而不是 fval。第26页/共47页3、代码源程序（1）编码 fun

13、ction bin_gen,bits=encoding(min_var,max_var,scale_var,popsize)bits=ceil(log2(max_var-min_var)./scale_var);bin_gen=randint(popsize,sum(bits);第27页/共47页（2）解码 function var_gen,fitness =decoding(funname,bin_gen,bits,min_var,max_var)num_var=length(bits);popsize=size(bin_gen,1);scale_dec=(max_var-min_var).

14、/(2.bits-1);bits=cumsum(bits);bits=0 bits;for i=1:num_varbin_vari=bin_gen(:,bits(i)+1:bits(i+1);vari=sum(ones(popsize,1)*2.(size(bin_vari,2)-1:-1:0).*bin_vari,2).*scale_dec(i)+min_var(i);endvar_gen=var1,:;for i=1:popsizefitness(i)=eval(funname,(var_gen(i,:);end解码函数的关键在于先由二进制数求得对应的十进制数D,并根据下式求得实际决策变量

15、值X:X=D scale_dec+min_var第28页/共47页（3）选择function evo_gen,best_indiv,max_fitness =selection(old_gen,fit-ness)popsize=length(fitness);max_fitness,index1 =max(fitness);min_fitness,index2 =min(fitness);best_indiv=old_gen(index1,:);index=1:popsize ;index(index1)=0;index(index2)=0;index=nonzeros(index);evo_

16、gen=old_gen(index,:);evo_fitness=fitness(index,:);evo_popsize=popsize-2;ps=evo_fitness/sum(evo_fitness);pscum=cumsum(ps);r=rand(1,evo_popsize);selected=sum(pscum*ones(1,evo_popsize)ones(evo_pop-size,1)*r)+1;evo_gen=evo_gen(selected,:);第29页/共47页 在该算子中,采用了最优保存策略和比例选择法相结合的思路,即首先找出当前群体中适应值最高和最低的个体,将最佳个体

17、best_indiv 保留并用其替换掉最差个体。为保证当前最佳个体不被交叉、变异操作所被坏,允许其不参与交叉和变异而直接进入下一代。然后将剩下的个体evo_gen 按比例选择法进行操作。所谓比例选择法,也叫轮盘算法,是指个体被选中概率与该个体的适应值大小成正比。将这两种方法相结合的目的是:在遗传操作中,不仅能不断提高群体的平均适应值,而且能保证最佳个体的适应值不减小。第30页/共47页（4）交叉 function new_gen=crossover(old_gen,pc)nouse,mating=sort(rand(size(old_gen,1),1);mat_gen=old_gen(mati

18、ng,:);pairs=size(mat_gen,1)/2;bits=size(mat_gen,2);cpairs=rand(pairs,1)pc;cpoints=randint(pairs,1,1,bits);cpoints=cpairs.*cpoints;for i=1:pairs new_gen(2*i-2*i,:)=mat_gen(2*i-1 2*i,1:cpoints(i)mat_gen(2*I 2*i-1,cpoints(i)+1:bits);end第31页/共47页（5）变异function new_gen=mutation(old_gen,pm)mpoints=find(ran

19、d(size(old_gen)pm);new_gen=old_gen;new_gen(mpoints)=1-old_gen(mpoints);第32页/共47页（6）注释 取种群大小popsize,搜索精度scale_var,交叉概率pc,变异概率pm。下界(min_var)上界(max_var)搜索精度scale_var 长度bits 初始种群bin_gen 最佳个体best_indiv 个体编码串cpairs 交叉点cpoints 变异点mpoints第33页/共47页四、遗传算法的应用1、遗传算法的应用领域（1）组合优化 （2）函数优化（3）自动控制 （4）生产调度（5）图像处理 （6）

20、机器学习（7）人工生命 （8）数据挖掘 第34页/共47页2、应用举例案例一 无约束目标函数最大值遗传算法求解策略 max f(x)=200 ，x -2,2 主程序clc;clear all;close all;global BitLengthglobal boundsbeginglobal boundsendbounds=-2 2;precision=0.0001;boundsbegin=bounds(:,1);boundsend=bounds(:,2);BitLength=ceil(log2(boundsend-boundsbegin)./precision);popsize=50;第35

21、页/共47页Generationnmax=200;pcrossover=0.90;pmutation=0.09;population=round(rand(popsize,BitLength);Fitvalue,cumsump=fitnessfun(population);Generation=1;while GenerationGenerationnmax+1 for j=1:2:popsizeseln=selection(population,cumsump);scro=crossover(population,seln,pcrossover);scnew(j,:)=scro(1,:);s

22、cnew(j+1,:)=scro(2,:);smnew(j,:)=mutation(scnew(j,:),pmutation);smnew(j+1,:)=mutation(scnew(j+1,:),pmutation);end第36页/共47页population=smnew;Fitvalue,cumsump=fitnessfun(population);fmax,nmax=max(Fitvalue);fmean=mean(Fitvalue);ymax(Generation)=fmax;ymean(Generation)=fmean;x=transform2to10(population(nm

23、ax,:);xx=boundsbegin+x*(boundsend-boundsbegin)/(power(boundsend),BitLength)-1);xmax(Generation)=xx;Generation=Generation+1;end第37页/共47页Generation=Generation-1;Bestpopulation=xx;Besttargetfunvalue=targetfun(xx);figure(1);hand1=plot(1:Generation,ymax);set(hand1,linestyle,-,linewidth,1.8,marker,*,marke

24、rsize,6)hold on;hand2=plot(1:Generation,ymean);set(hand2,color,r,linestyle,-,linewidth,1.8,.marker,h,markersize,6)xlabel(进化代数);ylabel(最大/平均适应度);xlim(1 Generationnmax);legend(最大适应度平均适应度);box off;hold off;第38页/共47页function scro=crossover(population,seln,pc)BitLength=size(population,2);pcc=IfCroIfMut(p

25、c);if pcc=1chb=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);elsescro(1,:)=population(seln(1),:);scro(2,:)=population(seln(2),:);end第39页/共47页function Fitvalue,cumsump=fitnessfun

26、(population)global BitLengthglobal boundsbeginglobal boundsendpopsize=size(population,1);for i=1:popsizex=transform2to10(population(i,:);xx=boundsbegin+x*(boundsend-boundsbegin)/(power(boundsend),BitLength)-1);Fitvalue(i)=targetfun(xx);end第40页/共47页Fitvalue=Fitvalue+230;fsum=sum(Fitvalue);Pperpopulat

27、ion=Fitvalue/fsum;cumsump(1)=Pperpopulation(1);for i=2:popsize cumsump(i)=cumsump(i-1)+Pperpopulation(1);end cumsump(popsize)=1;cumsump=cumsump;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(sn

28、ew(chb)-1);end第41页/共47页程序运行结果x=1.3749 y=183.1409第42页/共47页案例二 多约束非线性规划问题的求解 例：运用工具箱GA解决多约束非线性规划问题 min f(x)=()s.t.1.5+=0 -0|g210)f=100;Else f=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);end 运行结果：=-9.1208 =1.0867 BestFval=0.0327第44页/共47页提问与被提问问题提问问题1、模拟退火算法有什么缺陷和局限性？2、轮盘选择法的机理。被提问问题1、遗传算法倒位的条件？答：倒位类似于突变，突变概率本身就很小，所以倒位概率也很小。第45页/共47页第46页/共47页感谢您的观看！第47页/共47页