遗传算法报告.ppt

《遗传算法报告.ppt》由会员分享，可在线阅读，更多相关《遗传算法报告.ppt（39页珍藏版）》请在优知文库上搜索。

1、遗传算法及其MATLAB实现遗传的生物学基础v遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。Darwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些能适应环境的个体特征方能保留下来。Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得

2、以保存下来。遗传算法的概念v遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法。v简单遗传算法有编解码、个体适应度评估和遗传算法三大模块组成，而遗传运算又包括染色体复制、交叉变异等。遗传算法的实现步骤v1.编码v2.解码v3.个体适应度评估v4.复制v5.交配v6.突变v7.倒位遗传算法基本操作流程图 开始产生初始种群（编码、解码）计算个体适应度值 复制 交配 变异满足终止条件？输出最优解 结束YNk2k2v1.编码 遗传算法的编码有浮点编码和二进制编码两种。二进制编码二进制编码符合计算机处理信息的原理，能对染色体进行 遗传，编译和突变等操作。v设某一参数的取值范围为（L，U），长度为k，

3、则它共有 种不同的编码。00000000000000=0L 00000000000001=1 L+00000000000010=2L+2 00000000000011=3L+3 11111111111111=-1U k2k2k212KLUv2.解码 解码的目的是为了将不直观的二进制数据还原成十进制。设二进制 ，则对应的解码公式为例：设有参数x2，3，现用4位二进制数对x进行编码，可 得 条染色体：0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 任意数据代入译码公式，如x=0111 x

4、=2+7*=2.4666667 12321.bbbbbbkkk12)2(11KkiiiLUbLx162472*02*12*12*12321011kiiib12234v3.个体适应度评估 遗传算法依照与适应度成正比的概率来确定各个个体复制到下一代群体 的机会。个体适应度大的个体更容易遗传到下一代。通常，求目标函数最大值问题可以直接把目标函数作为检测个体适应度大小的函数。v4.复制运算复制运算把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代群体中。若设种群众个体总数为N，个体i适应度为fi：先计算出群体中所有个体的适应度的总和 fk

5、 (k=1.2,N);其次计算出每个个体的相对适应度的大小 fI/fK，它即为每个个体被遗传到下一代群体中的概率。每个概率值组成一个区域，全部概率值之和为1；最后再产生一个0到1之间的随机数，依据该随机数出现在上述哪一个概率区域内来确定各个个体被选中的次数。v5交配 对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交配概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交配时，可实行单点交配或多点交配。例如有个体 S1=100101 S2=010111 选择它们的左边3位进行交配操作，则有 S1=010101 S2=100111

6、一般而言，交配概率P。取值为0.250.75。6.突变 突变运算是使用基因位进行基因突变。假设突变几率Pm,即种群内所有基因都有Pm的概率进行突变，每个基因突变几率是均等的。因此将产生一系列随机数，然后将小于Pm的随机数选出，并将其对应的基因值翻转,即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。例如有个体S101011。对其的第1，4位置的基因进行变异，则有 S=001111。单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体

7、。也就是说，变异增加了全局优化的特质 遗传算法实例 问题：求发问题：求发f(x)=x2在在0，31上的上的 最大值最大值。一、初始种群一、初始种群1.编码：用五位二进制表示编码：用五位二进制表示x，有，有x=0 0 0 0 0 0 x=31 1 1 1 1 1 2.初始种群初始种群随机产生随机产生4个个体：个个体：13，24，8，193.适应度适应度f fi i直接用目标函数作为适应度：直接用目标函数作为适应度：f fi i=x=xi i2 24复制概率复制概率Ps染色体被复制的概率（选择率）：染色体被复制的概率（选择率）：p ps=f=fi/f/fi累积概率累积概率 PPk k平均适应度：平

8、均适应度：f f=f=fi/n/n5 5新种群复制新种群复制 编号初始种群位串 参数值x值目标适应值f(x)=x2复制概率率fi/fi累积概率下一代个体数目12340 1 1 0 11 1 0 0 00 1 0 0 0 1 0 0 1 1132489169576643610.140.490.060.310.140.630.691.001201总和平均值最大值11702935761.000.250.494.01.02.0初始种群参数计算二、遗传二、遗传选择后的交配池（下划线部分交叉）交配对象（随机选择）交叉位置（随机选择）新的种群xf(x)=x20 1 1 0 11 1 0 0 01 1 0 0

9、 0 1 0 0 1 1214344220 1 1 0 01 1 0 0 11 1 0 1 1 1 0 0 0 0 12252716144625729256总和平均值最大值1754439729说明：说明：1.复制复制 在种群众，被复制的概率高者多繁殖；低者在种群众，被复制的概率高者多繁殖；低者少繁殖或不繁殖。少繁殖或不繁殖。繁殖（复制）的个体放入交配池中。繁殖（复制）的个体放入交配池中。2.交叉交叉 随机选择交配对象（相同个体不交配），如随机选择交配对象（相同个体不交配），如个体个体1和和2，3 和和4。随机选择交叉点进行交叉。随机选择交叉点进行交叉。3.突变突变 取变异概率取变异概率pe=0

10、.01，表示每，表示每100个体中有一个体中有一个个体的一位发生变异。（暂不变异）个个体的一位发生变异。（暂不变异）新的种群，其平均值和最大值都有很大提高。新的种群，其平均值和最大值都有很大提高。均值：均值：293 439 最大值最大值：576 729 新种群中四个个体，有新种群中四个个体，有2个变好：个变好：25，25；2个变坏：个变坏：12，16。三、再遗传一代三、再遗传一代编号初始种群位串 参数值x值目标适应值f(x)=x2复制概率率fi/fi累积概率下一代个体12340 1 1 0 01 1 0 0 11 1 0 1 11 0 0 0 0122527161446257292560.08

11、0.360.420.140.080.440.861.000121总和平均值最大值17544397291.000.250.42选择后的交配池（下划线部分交叉）交叉对象（随机选择）交叉位置（随机选择）新的种群xf(x)=x21 1 0 0 11 1 0 1 11 1 0 1 1 1 0 0 0 0214311331 1 0 1 11 1 0 0 11 1 0 0 0 1 0 0 1 127252419729625576361总和平均值最大值2291572729 单纯用交叉而没有用变异，则遗传多少代得单纯用交叉而没有用变异，则遗传多少代得不到最优解不到最优解31(1 1 1 1 1)。主要是第三位所

12、有。主要是第三位所有个体都是个体都是0，这样只能得到，这样只能得到27（1 1 0 1 1）次次优解。优解。若在第四位中挑选一个个体进行变异，由若在第四位中挑选一个个体进行变异，由0变成变成1，在进行遗传将会得到最优解。，在进行遗传将会得到最优解。说明：说明：v例2用matlab实现遗产算法求解：maxf(x)=200e(-0.05x)sin(x),x-2,2v%子程序：将二进制数转换为十进制数，函数名称存储为transform2to10.mvfunction x=transform2to10(Population);vBitLength=size(Population,2);vx=Popul

13、ation(BitLength);vfor i=1:BitLength-1vx=x+Population(BitLength-i)*power(2,i);vendv%子程序:对于优化最大值或极大值函数问题，目标函数可以作为适应度函数v%函数名称存储为targetfun.mvfunction y=targetfun(x);%目标函数 vy=200*exp(-0.05*x).*sin(x);v%子程序:计算适应度函数，函数名称存储为fitnessfunvfunctionFitvalue,cumsump=fitnessfun(population);vglobal BitLengthvglobal

14、boundsbeginvglobal boundsendvpopsize=size(population,1);%有popsize个个体vfor i=1:popsizev x=transform2to10(population(i,:);%将二进制转化为十进制v%转化为-2 2区间的实数v xx=boundsbegin+x*(boundsend-boundsbegin)/(power(boundsend),BitLength)-1);v Fitvalue(i)=targetfun(xx);%计算函数值，即适应度vendv%给适应度函数加上一个大小合理的数以便保证种群适应值为正数vFitvalu

15、e=Fitvalue+230;v%计算选择概率vfsum=sum(Fitvalue);vPperpopulation=Fitvalue/fsum;v%计算累积概率vcumsump(1)=Pperpopulation(1);vfor i=2:popsizev cumsump(i)=cumsump(i-1)+Pperpopulation(i);vendvcumsump=cumsump;v%子程序:新种群选择操作，函数名称存储为selection.mvfunction seln=selection(population,cumsump);v%从种群中选择两个个体vfor i=1:2vr=rand;%

16、产生一个随机数vprand=cumsump-r;vj=1;vwhile prand(j)0vj=j+1;vendvseln(i)=j;%选中个体的序号vendv%子程序：判断遗传运算是否进行交叉或变异，函数名称存储为IfCroIfMut.mvfunction pcc=IfCroIfMut(mutORcro);vtest(1:100)=0;vl=round(100*mutORcro);vtest(1:1)=1;vn=round(rand*99)+1;vpcc=test(n);v%子程序，新种群变异操作，函数名称存储为mutation.mvfunction snnew=mutation(snew,pmutation);vBitLength=size(snew,2);vsnnew=snew;vpmm=IfCroIfMut(pmutation);%根据变异概率决定是否进行变异操作，1则是，0则否vif pmm=1vchb=round(rand*(BitLength-1)+1;%在1，BitLength范围内随机产生一个变异位vsnnew(chb)=abs(snew(chb)-1);vendv%