遗传算法解决完美.docx

用遗传算法解决二元多峰函数的优化问题1 .实验目的1.1 了解并掌握遗传算法的原理，流程以及编码方式；1.2 自编遗传算法程序对Rastrigin函数进行优化并对运行结果进行分析。1.3 利用遗传算法gatool的图形用户界面GUI,进行Rastrigin函数优化；2 ,实验条件2.1 硬件环境：Inter(R)Core(TM)DuoCPUT55501.83GHz1.83GHz,2G内存2.2 软件环境：WindowsXP,MAT1.AB7.0,gatool3 .实验原理3.1 遗传算法简介：遗传算法(GerIetiCAIgorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国MiChigan大学JHolland教授于1975年首先提出来的，并出版了颇有影响的专著AdaptationinNaturalandArtificialSystems，GA这个名称才逐渐为人所知，JHolland教授所提出的GA通常为简单遗传算法(SGA)o遗传算法是一类借鉴生物界的进化规律(适者生存，优胜劣汰遗传机制)演化而来的随机化搜索方法。其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。遗传算法是从代表问题可能潜在的解集的一个种群(population)开始的，而一个种群则由经过基因(gene)编码的一定数目的个体(individual)组成。每个个体实际上是染色体(ChromOSOme)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现(即基因型)是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代(generation)演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度(fitness)大小选择(selection)个体，并借助于自然遗传学的遗传算子(geneticoperators)进行组合交叉(crossover)和变异(mutation),产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码(decoding),可以作为问题近似最优解。3.2 遗传算法的基本运算过程：初始化:设置进化代数计数器t=0,设置最大进化代数N,随机生成n个个体作为初始群体popo(2)个体评价:计算群体POP中各个个体的适应度。(3)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。(4)交叉运算；将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。(5)变异运算:将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。6)群体PoP经过选择、交叉、变异运算之后得到下一代群体pop。(7)终止条件判断:以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。图1：遗传算法流程图攵又4实验技术方案4.1 自编程的遗传算法寻找Rastrigin函数的最小值4.1.1 Rastrigin函数具有两个独立变量的Rastrigin函数定义为：Ras(x,x2)=20+xr+x22-10(cos271x2+cos211x)维数为2,取值区间为-55-5,5,最小值为finin=0oRastrigin函数图形如下：图2：RaStrigirl函数图形4.1.2 编码方式(1)对给定上下界和求解精度，利用函数length=ceil(log2(up-low)prec+1)求得单个变量的编码长度，在此题中2个变量的上下界一样，故编码长度也一样(2)用encode函数随机产生n个长度为2×length的二进制代码作为初始种群的个体(3)用decode函数将个体的二进制代码解码得出xl,x2,代入fun函数求得函数值，根据BoltZmann选择，T=999求得个函数值的适应度，累加适应度构成一个赌轮，即在面积为一的赌轮中，函数值越小的个体被选中的概率越大。保存每一代的最小值为finin<)(4)执行select函数利用赌轮选择n个新个体作为新的种群。(5)执行CrOSSOVer函数，当产生的随机数小于交叉概率时，选择一个个体，对选择的两个个体随机产生一个位置作为交叉点，将其后面的代码进行交换。(6)执行mutation函数，当产生的随机数小于变异概率时，选择一个个体，随机产生一个位置作为变异点，将该点的编码置1或置0。(7)重复执行解码，求适应度，选择，交叉，变异几个步骤直到完成N代演化。(8)运行结束输出最小函数值fhin为最终优化值。4.1.3 运行结果分析(1)当n=20,N=100,prco=0.4,PmUt=O.1时，运行结果如下。表1：n=20,N=100,prco=0.4,PmUt=O.1时，运行结果运行次数12345(xl,x2)0.90771.00901.9040-0.0353-1.9939-0.0309-0.9945-0.9939-1.9871-0.0251fmin3.49275.63454.17231.99024.1058图3：第一次运行结果图RaStrigin函数的当前最小值与迭代次数的示意图,1111122.20181614»121086廿卅卅卅卅卅出HHm附件卅卅卅出出出卅420102030405060708090100gen由表1和图3我们可以一看出，遗传算法求解此时已经陷入局部最小值，求解的值和全局最小值fmin=0相差甚远，所以我们要对种群数量n、迭代次数N、交叉概率prco以及变异率pmut进行调整。(2)n,N不变，prco,PmUt变化，运行5次平均finin运行结果如下。表2：n=20,N=100,prco»PmU变化时，运行结果0.20.40.60.15.37564.17234.59510.24.86496.65543.65750.34.63172.06463.30320.43.33852.07473.58860.53.98981.48962.78700.61.73222.11382.8853图4：n=20,N=100,prco=0.6,PmU=O.6时，运行结果图RaStngin函数的当前最小值与迭代次数的示意图1 4Iiiiiiiiii12 支-+13 -HimiIH-8-6-4-1Hl11Iii4-+-HlIliI用用HlIHHl2-H+-IIHHIHIHHHHHn-QIlllllllll0102030405060708090100gen由表2和图4我们可以一看出：当增加交叉率时，遗传算法求解的最小值得到了进一步的改善；当变异率增大时，遗传算法求解的最小值也得到了很大程度的改善。所以我们适当的增大交叉率和变异率时，可以比较有效的跳出局部最优解，更好的逼近最优解。(3)prco=0.6,pmut=0.6,n,N变化，运行5次平均fmin运行结果如下。表3：prco=0.7,pmut=0.6,n,N变化时，运行结果1002003004001000.31930.36190.43420.15392000.43740.16130.10950.10753000.54920.09600.10330.08504000.44220.14190.04300.0670图5：n=400,N=400prco=0.7,PmU=O.6时，运行结果图RaStngin函数的当前最小值与迭代次数的示意图由表3和图5我们可以一看出：当增加种群个数时，遗传算法求解的最小值更加逼近全局最小值。并且对于n>300时，继续增加n对结果影响不大，只增加运行所需要的时间；当迭代次数增大时，遗传算法求解的最小值也得到了很大程度的改善。并且由图4可以看出当N>100时，继续增加N对结果影响不大，只增加运行所需要的时间。所以我们选择n=200,N=100,prco=0.7,pmut=0.6,可以更好的逼近最优解。4.2运用遗传算法gatool的图形用户界面GUl对Rastrigin函数优化4.2. Igatool使用介绍：(I)Fitnessfunction：欲求最小值的目标函数。输入输入适应度函数的形式为fitnessfun,其中fitnessfun.m是计算适应度函数的M文件。符号产生一个对于函数fitnessfun的函数句柄。图形界面如图6所示。图6：遗传算法工具图形界面4.2.1 Numberofvariable：适应度函数输入向量的长度。单击“Start”按钮，运行遗传算法，将在"Statusandresult"窗口中显示出相应的运行结果。在“Option”窗格中可以改变遗传算法的选项。为了查看窗格中所列出的各类选项，可以单击与之相连的符号“+”。4.2.2 运行gatool对Rastrigin函数进行优化(1)在命令行键入gatool,打开遗传算法工具。(2)在遗传算法工具相应的栏目中，输入“rastriginsfbn"：在"Numberofvariable,文本框中，输入"2"。（3）选择复选框中的最佳适应度和最佳个体的图形选项（4）单击“Start”按钮，运行遗传算法。4.2.3 结果分析有说明可知gatool默认种群为20,迭代次数为100。运行五次其结果如下:表4：gatool运行结果运行次数12345frnin0.00310.99500.00200.00640.0027图7：第一次运行每代适应度函数最佳值与平局值的对数图形Best:0.99503Mean:1.037910,8n-BASSW1.-I11一“"-,-Z8-"*2030405060708090100Generationo°1.l-StOP10图9：第三次运行每代适应度函数最佳值与平局值的对数图形,Best:0.0020445Mean:0.03326310FGeneration图11：第五次运行每代适应度函数最佳值与平局值的对数图形.Best:0.0064006Mean:0.02155410102030405060708090100Generation用gatool的运行结果和自编程n=20,N=100,prco=0.4,PmUt=O.1时，运行结果对比可以看出：在同样的设定参数下gatool的运算精度和时间效率比自编程序要高很多，所以我们自己编写的遗传算法还有很大的改进空间，需要不断地改进。5附件遗传算法代码：gat.mfunction=fun(n,N,pcro,pmut)%遗传算法主函数%用以实现求给定函数fun在给定区间low,up上的极大值%pcro交叉概率,pmut变异概率,N为迭代次数,n为种群low=-5;/区间下限up=5;%区间上限T=999;%Boltzmann选择prec=0.0001;%要求结果精度Iength=Ceil(log2(up-low)prec+l);%求得单个变量编码长度pop=encode(length,n);%用解码函数求得初始种群，n为种群个体个数fmin=inf;%最优解xlmin=0;x2min=0;gen=0;%代数初始化forgen=0:Nfval=zeros(1,n);%初始化函数值fit=zeros(l,n);%初始化适应度ppl=zeros(l,n);%BoItzmann选择fori=l:nxl,x2=decode(pop(i,:),low,up,length);%利用解码函数解码个体fval(i)=fun(xl,x2);%求个体的函数值iffval(i)<fminfmin=fval(i);%精英保留xlmin-xl;x2min=x2;endendplot(gen,fmin,r÷,);holdon;pause(1N*5);xlabel('gen,);ylabel(,y,);title(,Rastrigin函数的当前最小值与迭代次数的示意图');fori=l:nppi(i)=lexp(fval(i)T);endpp2=sum(ppl);fit=pplpp2;%个体的适应度q(l)=fit(l);fori=2:n的累加个体适应度形成赌轮q(i)=q(i-l)+fit(i);endpop=select(pop,q,n);%选择pop-crossover(pop,pcro,n,length);%交叉pop-mutation(pop,pmut,n,length);%变异%下一代end%输出最小值以及此时的自变量fmin,xmin=xlmin,x2mincro.mfunctionpopnew=crossover(pop,pcro,n,length)%交叉函数%pcro为交叉概率k=l;i=0;while(k<=n)rk=randO;ifrk<pcrob(i÷l)=k;i=i÷l;endk=k+l;ifi=2pos=cei1(randO*length);%随机产生交叉点fori=pos:lengthc=pop(b(l),i);pop(b(l),i)=pop(b(2),i);%对xl的交叉点之后的编码进行交换pop(b(2),i)=c;endpos=ceil(randO*length)+length;%随机产生交叉点fori=pos:2*lengthc=pop(b(l),i);pop(b(l),i)=pop(b(2),i);%对x2的交叉点之后的编码进行交换pop(b(2),i)=c;endi=0endendpopnew=pop;enco.mfunctionpop-encode(length,n)外编码函数pop=randint(n,2*length);%产生初始种群,2变量，故乘2deco,mfunctionxl,x2=decode(a,low,up,length)外解码函数%a为待解码个体,将个体分成两端后分别解码得到两个变量的值strl=0;str2=0;fori=l:lengthifa(length+l-i)strl=strl÷27i-l);%求解二进制字符串代表的十进制数值endendxl=low+strl*(up-low)/(2length-1);%求解解码后的十进制数fori=l:lengthifa(2*length+l-i)str2=str2+2(i-l);endendx2=low+str2*(up-low)/(2length-1);muta.mfunctionpopnew=mutation(pop,pmut,n,length)%变异函数%pmut为变异概率k=l;whilek<=nrk=randO;ifrk<pmutpos=fix(randO*2*length)+1;%随机产生变异点pop(k,pos)="pop(k,pos);%对变异点进行变异endk=k+l;endpopnew=pop;sei.mfunctionpopnew=select(pop,q,n)%选择函数%pop为待选择原始种群%q为每个个体适应度累计概率，即赌轮区间，n为种群个体数m=l;fork=l:nr=randO;for1=2:nif(q(1-1)<=r)&&(r<=q(1)为赌轮选择m=l;break;endpopnew(k,:)-pop(m,:);endfun.mfunctionz=fun(xl,x2)外目标函数z=20+xl.2+x2.2-10*(cos(2*i*xl)+cos(2*pi*x2);