遗传算法及其MATLAB实现ppt课件.ppt

,遗传算法及其matlab实现,报告人,遗传算法生物学基础,遗传算法是模拟自然界生物进化过程与机制求解极值问题的一类自组织，自适应人工智能技术，其基本思想是模拟自然界遗传机制和生物进化论而形成的一种过程搜索最优解的算法。在自然界，由于组成生物群体中各个个体之间的差异，对所处环境有不同的适应和生存能力，遵照自然界生物进化的基本原则，适者生存、优胜劣汰，将要淘汰那些最差个体，通过交配将父本优秀的染色体和基因遗传给子代，通过染色体核基因的重新组合产生生命力更强的新的个体与由它们组成的新群体。在特定的条件下，基因会发生突变，产生新基因和生命力更强的新的个体；但突变是非遗传的，随着个体不断更新，群体不断朝着最优化方向前进，遗传算法是真实模拟自然界生物进化机制进行寻优的。,1、个体编码2、初始群体的产生3、适应度计算4、新种群的选择复制5、新种群的交配（交叉运算)6、新种群的变异运算,算 法 步 骤,算 法 流 程 图,遗传算法步骤,以一个案例来说明遗传算法的具体过程：,函数的三维图形,1、个体编码,遗传算法的对象运算是表示个体的符号串，所以必须把变量编码为一种符号串,即将变量转换成二进制数串。数串的长度取决于所要求的精度。例如，变量x的区间是（L，U），要求的精度是小数点后四位，也就意味着每个变量应该被分成至少 个部分。对一个变量的二进制数串位数用以下公式计算： 本例精度要求保留小数点后四位，则目标函数的俩个自变量x1及x2所构成的染色体串位数m1=18，m2=15，即本例中任何一染色体串为33位，前18位表示x1后15位表示x2。,染色体编码,2、初始群体的产生,遗传算法是对群体进行的进化操作，需要给其准备一些起始搜索点的初始群体数据初始群体太小时会产生病态基因，且造成有效等位基因先天缺乏初始群体太大会导致结果难以收敛且浪费资源，稳健性下降建议值0100,假设初始种群中有10个个体，其染色体可随机生成如下： U1=000001010100101001 101111011111110 U2=001110101110011000 000010101001000 U3=111000111000001000 010101001000110 U4=100110110100101100 000000010111001 U5=000010111101100010 001110001101000 U6=111110101011011000 000010110011001 U7=110100010111110001 001100111011101 U8=001011010111111100 010110011001100 U9=111110001011101100 011101000111101 U10=111101001110101010 000010101101010相应的十进制实际值x1,x2为： U1=2.687969,5.361653 , U2=0.474101,4.170144 U3=10.419457,4.661461 , U4=6.159951,4.109598 U5=-2.301286,4.477282 , U6=11.788084,4.174346 U7=9.342067,5.121702 , U8=-0.330256,4.694977 U9=11.671267,4.873501 , U10=11.446273,4.171908,3、适应度计算,遗传算法以个体适应度来评定各个个体的优劣程度从而决定其遗传机会的大小,对一个染色体数串的适应度的评价由下列三个步骤组成。将染色体串进行反编码（解码），转换成真实值，即评价目标函数将目标数值转为适应度值。对于极大值问题，适应度可作为目标函数值：,在遗传算法中，评价函数扮演自然进化中环境的角色，它通过染色体的适应度对其进行评价。上述染色体的适应度如下：eval（U1）=f（-2.687969,5.361653）=19.805119同理可得，eval（U2）=17.370896eval（U3）=9.590546eval（U4）=29.406122eval（U5）=15.686091eval（U6）=11.900541eval（U7）=17.958717eval（U8）=19.763109 eval（U9）=26.401669eval（U10）=10.252480,依照染色体的适应度值进行新种群的复制，步骤如下：计算染色体 的适应度值计算种群的适应度值总和计算每个染色体被复制的概率计算每个染色体被复制的累积概率,4、新种群的选择复制,依照轮盘选择法，转动轮盘10次（假设种群的染色体），每次选择一个作为新种群的染色体，这样，适应度越大的就越有机会复制到下一代,依照轮盘选择法，转动轮盘10次，每次选择一个作为新种群的染色体。假设10次产生的01随机数序列如下： 0.301431 0.322062 0.766503 0.881893 0.350871 0.538392 0.177618 0.343242 0.032685 0.197577根据以上的计算方法，可以先计算出种群中每个染色体的适应度和概率，如表所列：,种群每条染色体的适应度、被复制概率和被复制的累积概率,第一个随机数为0.301431，大于Q3小于Q4，所以U4被选中；第二个随机数为0.322062，大于Q3小于Q4，所以U4再次被选中；第十个随机数为0.197577，大于Q1小于Q2，所以U2被选中；依照轮盘转法，新种群的染色体组成如下： U1=100110110100101101 000000010111001 U2=100110110100101101 000000010111001 U3=001011010100001100 010110011001100 U4=111110001011101100 011101000111101 U5=100110110100101101 000000010111001 U6=110100010111110001 001100111011101 U7=001110101110011000 000010101111000 U8=100110110100101101 000000010111001 U9=000001010100101001 101111011111110 U10=00111010110011000 000010101001000 这种轮盘选择法的机理是：染色体的适应度大意味着 , 区间跨度就大，随机数发生器发生的均匀随机数就会有更大的概率落在较大长度的 , 区间里，这样具有较大 值的染色体自然更有机会复制到下一代。,5、新种群的交配（交叉运算),交配染色体数量的确定 交配染色体的数量等于染色体总量乘以交配概率。这里假设交配概率 为0.25，染色体总量为10条，所以 参加交配的染色体数量为2.5条。符号 表示取整，这里取整数2，即交配的染色体数目为2条。交配染色体对象的确定用计算机产生0,1区间的10个随机数如下：0.625721 0.266823 0.288644 0.295114 0.1632740.567461 0.085940 0.392865 0.770714 0.548656,交叉运算是遗传算法中产生新个体的主要操作过程，它以某一概率相互交互两个个体之间的部分染色体先对群体进行随机配对，其次随机设置交叉点位置，最后再相互交换配对染色体之间的部分基因交叉概率一般取0.40.99,假定其分别对应U1U10这10个个体，则其中低于交配概率0.25的U5和U7参加交配。这样操作的原因是：交配概率越低，低于交配概率以下的随机数的数量就越少，所以参加交配的染色体数量与交配概率可能会成正比。在交配池发生交配 染色体U5和U7被选中作为交配的父辈，交配点的选择以随机数产生。交配的种类有单点交配和多点交配，这里取单点交配。计算机随机生成一个介于032的整数。假设所产生的整数为1，那么两个染色体自1位置开始分割，在染色体1位置右端部分进行交换而生成新的子辈染色体，即U5=1 0011 0110 1001 0110 1000 0000 1011 1001U7=0 0111 0101 1100 1100 0000 0101 0100 1000U5*=1 0111 0101 1100 1100 0000 0101 0100 1000U7*=0 0011 0110 1001 0110 1000 0000 1011 1001,6、新种群的变异运算,依照突变运算规则并假设突变几率 为0.01，亦即种群内所有基因都有0.01的概率进行突变。本例中共有3310=330个基因，即希望每一代中有3.3个突变基因，每个基因的突变几率是相等的。因此，将产生330个介于01之间的随机数，然后将该随机数小于0.01者选出，并将其对应的基因值加以翻转，假设330次中产生01之间的随机数，其值小于0.01者如右表所列。 右表第一列显示的是具体在哪些染色体以及在染色体的什么位置进行了突变。例如第一行表示的是在第4条染色体第6个基因上发生了突变。,变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进行改变，是产生新个体的一种操作方法首先确定出各个个体的基因变异位置，然后依照某一概率将变异点的原有基因值取反,基因突变位置,在突变后，最终新种群的染色体组成如下：U1=100110110100101101 000000010111001U2=100110110100101101 000000010111001U3=001011010100001100 010110011001100U4=111111001011101100 011101000111101U5=101110101110011000 000010101001010U6=110100010111110001 001100111011101U7=100110110100101101 000000010111001U8=100110110100101101 000000010111001 U9=000001010100101001 000000010111001U10=001110101110011000 000010101001010,新一代的对应实际值x1,x2和适应度值如下：eval（U1）=f（6.159951,4.109598）=29.406122eval（U2）=29.406122eval（U3）=19.763190eval（U4）=5.702781 eval（U5）=19.910251eval（U6）=17.958717 eval（U7）=29.406122eval（U8）=29.406122 eval（U9）=19.805119 eval（U10）=17.370896 至此，已完成遗传算法的第一代流程。依此迭代，在第451代得到对应最大目标函数值的染色体： =111110000000111000 111101001010110相应实际值x1,x2=11.631407，5.724824，适应度值eval（U）=38.818208,用MATLAB语言实现遗传算法,1、编码以及产生初始种群 使用二进制编码，通常根据搜索精度（sca_var)、决策变量上界（range(2)的和下界（range(1)来确定各个二进制字符串的长度（bit_n)，搜索精度为sca_var=(range (2)-range(1)/(2bit_n-1),，然后再随即产生一个初始种群(be_gen)，其规模为popusize，下面用函数encoding来实现编码和产生的初始种群： function be_gen,bit_n=encoding(sca_var,range(1),range(2),popusize) bit_n=ceil(log2(range(2)-range(1)/sca_var); be_gen=randint(popusize,sum(bit_n);,用MATLAB语言实现遗传算法,2、译码 个体种群be_gen要通过解码才能够转换成原问题空间的决策变量构成的种群vgen，才可计算各个适应度。另外，译码需首先求出二进制数对应的十进制数decimal，然后根据公式求出实际决策变量X：X=range(1)+decimal*sca_dec.通常可以用decoding函数来实现译码过程：functionvgen,fitness=decoding(fcn,be_gen,bit_n,range(1),range(2)popusize=size(be_gen,1); n_var=length(bit_n);sca_dec=(range(2)-range(1)/(2bit_n-1);,bit_n=cumsun(bit_n);bit_n=0 bit_n;for i=1:n_varbe_var(i)=be_gen(:,bits(i)+1:bit_n(i +1);var(i)= range( 1)( i )+sum(ones(popusize,1)*2.(size(be_var(i),2)- 1:- 1:0).*be_var(i),2).*sca_dec(i);endvgen=var(1,:);for i=1:popusizefitness(i )=eval(fcn,(var_gene(i,:) );end,用MATLAB语言实现遗传算法,3、选择 选择算子中，先找出当前群体中适应度最高和最低的个体，将最佳个体bes_ind保留并替换最差个体，直接进入下一代，将剩余个体evol_gen按适应值比例选择法进行操作。即1计算个体适应值2计算适应值在群体适应值总合所占的比例，来表示该个体被选中的概率，可用下面函数实现选择算子：function evol_gen, bes_ind,max_fitness=selection(old_gen, fitness)min_fitn,expo(b)=min(fitn);max_fitn,expo(a)=max_(fitn);popusize=length(fitness);bes_ind=old_gen(expo(a),:);expo=1:popusize;expo(expo(a)=0;expo(expo(b)=0;expo=nonzeros(expo);evol_gen=old_gen(expo,:);,evol_fitness=fitness(expo,:);evol_popusize=popusize- 2;posel=evol_fitness/sum(evol_fitness);poselcum=cusum(posel);r=rand(1,evol_popusize);selected=1+sum(poselcum*ones(1, evol_popusize)ones(evol_popusize,1)*r);evol_gen=evol_gen(selection,:);,用MATLAB语言实现遗传算法,4、交叉 通常使用一点交叉法，就是按交叉概率pc(0pc1)实施交叉操作，两个个体编码串（string)在交叉位置处（crossp)相互交换各自的部分编码从而形成新的一对个体，程序如下：function new_gen=recombination(old_gen,pc)nouse,match=sort(rand(size(old_gen,1),1);match_gen=old_gen(match,:);pairs=size(match- gen,1)/2;bit_n=size(match_gene,2);string=rand(pairs,1)pc;crossp=randint(string,1,1,bit_n);crossp=string.*crossp;for i=1:pairsnew_gen(2* i- 1 2* i,: )=match_gen(2* i- 1 2* i ,1:crossp(i) ) match_gen(2* i 2* i - 1,crossp(i)+1:bin_n);,用MATLAB语言实现遗传算法,5、变异 变异操作通过按照变异概率（mp)随机反转某位等位基因的二进制字符的值来实现。程序如下function new_gen=mutation(old_gen, pm )mpoints=find(rand(size(old_gen)pm);new_gen=old_gen;new_gen(mpoints)=1- old_gen(mpoints);end,遗传算法应用案例,待求解问题：函数图像如下：,遗传算法源程序求解最大值：% 主程序：用遗传算法求解y=200*exp (-0.05*x).*sin(x)在-2 2区间上的最大值clc;clear all;close all;global BitLengthglobal boundsbeginglobal boundsendbounds=-2 2;% 一维自变量的取值范围,遗传算法应用案例,recision=0.0001; % 运算精度boundsbegin=bounds(:,1);boundsend=bounds(:,2);% 计算如果满足求解精度至少需要多长的染色体BitLength=ceil(log2(boundsend-boundsbegin) ./ precision);popsize=50; % 初始种群大小Generationnmax=12; % 最大代数pcrossover=0.90; % 交配概率pmutation=0.09; % 变异概率,% 产生初始种群population=round(rand(popsize,BitLength);% 计算适应度,返回适应度Fitvalue和累积概率cumsumpFitvalue,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); smnew(j+1,:)=mutation(scnew(j+1,:),pmutation); end population=smnew; % 产生了新的种群 % 计算新种群的适应度 Fitvalue,cumsump=fitnessfun(population); % 记录当前代最好的适应度和平均适应度 fmax,nmax=max(Fitvalue); fmean=mean(Fitvalue); ymax(Generation)=fmax; ymean(Generation)=fmean;,% 记录当前代的最佳染色体个体 x=transform2to10(population(nmax,:); % 自变量取值范围是-2 2,需要把经过遗传运算的最佳染色体整合到-2 2区间 xx=boundsbegin+x*(boundsend-boundsbegin)/(power(boundsend),BitLength)-1); xmax(Generation)=xx; Generation=Generation+1endGeneration=Generation-1;Bestpopulation=xxBesttargetfunvalue=targetfun(xx)% 绘制经过遗传运算后的适应度曲线。一般地，如果进化过程中种群的平均适应度与最大适% 应度在曲线上有相互趋同的形态，表示算法收敛进行得很顺利，没有出现震荡；在这种前% 提下，最大适应度个体连续若干代都没有发生进化表明种群已经成熟。,遗传算法应用案例,figure(1);hand1=plot(1:Generation,ymax);set(hand1,linestyle,-,linewidth,1.8,marker,*,markersize,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;,% 子程序：新种群交叉操作,函数名称存储为crossover.mfunction scro=crossover(population,seln,pc);BitLength=size(population,2);pcc=IfCroIfMut(pc); % 根据交叉概率决定是否进行交叉操作，1则是，0则否if pcc=1 chb=round(rand*(BitLength-2)+1; % 在1,BitLength-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,遗传算法应用案例,% 子程序：计算适应度函数, 函数名称存储为fitnessfunfunction Fitvalue,cumsump=fitnessfun(population);global BitLengthglobal boundsbeginglobal boundsendpopsize=size(population,1); % 有popsize个个体for i=1:popsize x=transform2to10(population(i,:); % 将二进制转换为十进制 % 转化为-2,2区间的实数xx=boundsbegin+x*(boundsend-boundsbegin)/(power(boundsend),BitLength)-1); Fitvalue(i)=targetfun(xx); % 计算函数值，即适应度end% 给适应度函数加上一个大小合理的数以便保证种群适应值为正数Fitvalue=Fitvalue+230;,% 计算选择概率fsum=sum(Fitvalue);Pperpopulation=Fitvalue/fsum;% 计算累积概率cumsump(1)=Pperpopulation(1);for i=2:popsize cumsump(i)=cumsump(i-1)+Pperpopulation(i);endcumsump=cumsump;,遗传算法应用案例,% 子程序：新种群变异操作，函数名称存储为mutation.mfunction snnew=mutation(snew,pmutation);BitLength=size(snew,2);snnew=snew;pmm=IfCroIfMut(pmutation); % 根据变异概率决定是否进行变异操作，1则是，0则否if pmm=1 chb=round(rand*(BitLength-1)+1; % 在1,BitLength范围内随机产生一个变异位 snnew(chb)=abs(snew(chb)-1);end,% 子程序：判断遗传运算是否需要进行交叉或变异, 函数名称存储为IfCroIfMut.mfunction pcc=IfCroIfMut(mutORcro);test(1:100)=0;l=round(100*mutORcro);test(1:l)=1;n=round(rand*99)+1;pcc=test(n);,运行结果,最大适应度值在进化过程中变化幅度不大，这是因为自变量取值区间跨度较小，而种群为50条染色体数量较多，较多的染色体和较小的搜索区间让算法最大初始适应度值有更多的机会直接落在理论最优解附近。,遗传算法应用案例,% 子程序：新种群选择操作, 函数名称存储为selection.mfunction 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,% 子程序：将2进制数转换为10进制数,函数名称存储为transform2to10.mfunction x=transform2to10(Population);BitLength=size(Population,2);x=Population(BitLength);for i=1:BitLength-1 x=x+Population(BitLength-i)*power(2,i);End% 子程序：对于优化最大值或极大值函数问题，目标函数可以作为适应度函数% 函数名称存储为targetfun.mfunction y=targetfun(x); % 目标函数y=200*exp (-0.05*x).*sin(x);,MATLAB遗传算法工具箱,.函数ga语法格式：x,fval,reason=ga(fitnessfun,nvars,options)功能：实现对目标函数进行遗传运算2.函数gaoptimset语法格式：options= gaoptimset(propertyname1, propertyvalue1, (propertyname2, propertyvalue2 (propertyname3, propertyvalue3.)功能：实现设置遗传算法的参数和句柄函数,鉴于遗传算法本质上是一种启发式的随机运算算法程序经常重复运行多次才能得到理想结果。鉴于此，可以将前一次运行得到的最后种群作为下一次运行的初始种群，如此操作会得到更好的结果。,工具箱核心函数的用法,遗传算法特点,特点 算法仅用到与搜索空间中检查过的点相联系的适应值。不管求解问题本身,通过执行同样的、惊人简单的复制、杂交和偶尔的变异操作来完成它的搜索。在实际应用中,遗传算法能遗传算法能够快速有效地搜索复杂、高度非线性和多维空间,出人意外的是它并不知道问题本身的任何信息,也不了解适应值度量。遗传算法成功的关键在于符号串表示和遗传操作的设计。,局限性 需要注意的是，对于约束条件相对比较复杂，导致可行解不太容易找到（解空间中可行解对应区域的边界不规则），直接用普通的交叉、变异操作可能会很容易导致产生的大量解不可行，,答辩(被提问）,1、怎么确定是否停止迭代？答：终止代数T是表示遗传算法运行结束条件的一个参数，它表示遗传算法运行到指定的进化代数之后就停止运行，并将当前群体中的最佳个体作为所求问题的最优解输出。常用的判定遗传算法的终止条件还有下面两种：连续几代个体平均适应度的差异小于某一个极小的阈值群体中所有个体适应度的方差小于某一极小的阈值,2、书上只举例了两条染色体时如何交配那么两条以上如何配置？答：目前常用的配对策略是随机配对，即将群体中的M个个体以随机的方式组成【M/2】对配对个体组，交叉操作是在这些配对个体组中的两个个体之间进行的。3、遗传算法的局限性？答：见最后一页PPT,参考文献：周明，孙树东.遗传算法原理及应用.北京：国防工业出版社.1996.6,答辩（提问）,1、怎样判断选择、交叉、变异的顺序，可以改变顺序吗？答：选择肯定是要放在前面的，因为“被交叉”和“被变异”的染色体都要经过“选择”这一操作才能被选出来啊，至于交叉和变异，大部分人的做法都是先交叉再变异，但是我也看过一些文献是先变异再交叉的，这个应当具体问题具体分析了。,2、模拟退火算法的局限性答：找到最优解耗时长 求解需要更困难的参数调整,结 束,