遗传算法及其改进措施

1、优化算法大作业一、题目本文利用遗传算法，依次完成下面三个目标函数的寻优：1Generalized Rosen brocks valley Function2 Generalized Rastrigin's Function3 Schaffers Function二、本文思路遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法，本文利用遗传算法分别对上述三种函数进行全局寻优，具体思路如下：1. 编码与解码 1) 编码：假设某一参数的取值范围是umin , umax，我们用长度为l的二进制编码符号串来表示该参数，则它总共能够产生 2l 种不同的编码，编码的长

2、度越长，对应的精度越高。l 第一题变量的取值范围是-2.048,2.048，本文采取十位数的编码，那么精度为：l 第二题变量的取值范围是-5.12,5.12，本文采取的是十二位数的编码，那么精度为：l 第三题变量的取值范围是-4,4，本文采取的是十三位数的编码，那么精度为：2) 解码：假设某一个个体的编码是，那么对应的解码公式为：2. 个体适应度评价1) 当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设 定个体的适应度F(X)就等于相应的目标函数值f(X)，即：Fx=fx-Cmin fx>Cmin0 fxCmin其中是函数最小值估计。2) 对于求目标函数最小值的优化问题，理论

3、上只需简单地对其增加一个负号就可将其转化为求目标函数最大值的优化问题，即Fx=Cmax-fx fx<Cmax0 fxCmax其中是函数的最大值估计。3. 复制、交叉、变异1) 比例算子：个体被选中并遗传到下一代的概率与个体的适应度成正比，本文采取的的赌轮盘选择法选，该方法较容易实现，易于编程。2) 交叉算子：交叉是遗传算法产生新个体的主要手段，通过交叉子代的基因值不同于父代，从而可以出现适应度更高的个体，本文采用的是单点交叉算子。3) 变异算子：变异也是产生新个体的一种方法，对于遗传算法中二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将基因值变

4、为1，反之，若原有的基因值为1，则变异操作将其变为0。三、程序流程对于一个需要进行优化的实际问题，一般可按下述步骤构造遗传算法：第一步：确定决策变量及各种约束条件，即确定出个体的表现型X和问题的解空间；第二步：建立优化模型，即确定出目标函数的类型及数学描述形式或量化方法；第三步：确定表示可行解的染色体编码方法，即确定出个体的基因型x及遗传算法的搜索空间；第四步：确定解码方法，即确定出由个体基因型x到个体表现型X的对应关系或转换方法；第五步：确定个体适应度的量化评价方法，即确定出由目标函数值到个体适应度的转换规则；第六步：设计遗传算子，即确定选择运算、交叉运算、变异运算等遗传算子的具体操作方法。

5、第七步：确定遗传算法的有关运行参数，即M,G,Pc,Pm等参数。具体程序流程图见下图所示：图1遗传算法流程图四、优化过程1. 第一题图2 Rosen brock函数图像图3 遗传算法迭代寻优过程程序运行结果如下：最优点函数取值2. 第二题图4：Rastrigin函数图像图5：遗传算法迭代寻优过程程序运行结果如下：最优点函数取值3. 第三题图6 Schaffer函数图像图7 遗传算法迭代寻优过程程序运行结果如下：最优点函数取值由仿真结果可知，随着进化过程的进行，群体中适应度较低的一些个体被逐渐淘汰掉，而适应度较高的一些个体会越来越多，并且它们都集中在所求问题的最优点附近，从而搜索到问题的最优解。

6、五、问题的发现与改进1. 问题一：局部最优解从第三题的函数图像中可以看出，该函数有无限多个局部极大值点，只有一个全局最优点,此函数最导致峰周围有一圈脊，上面的取值均为0.990283。从上面的优化过程可以看出，当随机选定初始种群后，随着迭代次数的增加，种群最终都集中在了这一圈脊上，也就是寻优过程陷入了局部最优点，并没有找到函数的的最优点。对于遗传算法中的上述问题，我们采用的解决方案如下。解决方法1：等值线法初始种群的选取对函数能不能找到最优点有着重要的影响，本文通过分析函数的等值线缩小初始种群的随机产生范围，从而让种群朝着全局最优点进化。在Matlab下画出函数的等值线如下图：图8 目标函数的

7、等值线图从图中可以看出，以中心最优点为圆心，围绕着中心点分布着多条等值线，从中心的红色区域向外到蓝色区域，目标函数值先减小再增加最后又减小，所以本文以中间红色区域到蓝色区域中选取合适的等值线截面，并在该面上随机产生初始种群，这样可以有效防止迭代陷入局部最优解。改进后的寻优结果：图9 改进后的遗传算法寻优过程图6中的最终种群进化到了函数一圈“脊”上，但是这只是函数的局部最优点，而从图9可以清楚地看到，种群进化到最后都集中在了中心凸起点的附近，这也是函数的最大值点，可见改进后的遗传算法有效的解决了局部最优点的问题，顺利找到了函数的全局最优解。解决方法2：模拟退火算法模拟退火算法是模仿了自然界退火现

8、象，利用了物理中固体物质的退火过程与一般问题的相似性，从某一初始温度开始，伴随着温度的不断下降，结合概率突跳特性在解空间中随机寻找全局最优解，它能有效的克服寻优陷入局部最小值的优化方法。其具体算法原理本文不详述，只给出采用模拟退火算法的实现过程如下图所示：图10 模拟推过算法实现过程相关参数选择为：初始温度Temperature=30步长因子StepFactor=0.002容差Tolerance=1e-7马可夫链长度MarkovLength=1000衰减参数DecayScale=0.95程序运行结果为（程序见附录）：最优点函数取值寻优过程如下：图11 模拟退火算法的寻优过程从上面的寻优结果可以

9、看出，模拟退火算法解决了本例中遗传算法寻优陷入局部最优解的问题，最终找到了Schaffer Function函数的全局唯一最优解。问题二：寻优速度 基本的遗传算法中产生优良个体的主要手段是同过交叉重组，但这样并不能保证产生新个体的速度，即迭代寻优的速度很慢，考虑到为了保证较高的精度，本文的基因编码分别是十位、十二位与十三位，那么对于二元函数，染色体的长度就是二十、二十四与二十六，因此可以在交叉重组时，将较长的染色体分为若干段，并对每一小段进行两两配对交叉重组，这样相当于每个染色体在一次的迭代过程中参与了几次交叉重组，大大加快了新个体的产生速度。本文即将染色体分为了两段，进行交叉重组（程序见附录

10、），加快了寻优速度。六 程序附录1 遗传算法主程序%遗传算法主程序%clear %清除普通变量，不清除全局变量clfpopsize=80; %种群大小chromlength=26; %字符串长度（个体染色体长度）pc=0.6;pm=0.001;% global Numv=2;pop=initpop(popsize,chromlength)for i=1:200 %200为迭代次数 objvalue=calobjvalue(pop); %计算函数值 fitvalue=calfitvalue(objvalue); %计算个体适应度 avefitvalue(i)=sum(fitvalue)/pops

11、ize; newpop=selection(pop,fitvalue);% 选择 newpop=crossover_multiv(newpop,pc); newpop=mutation(newpop,pm); bestindividual,bestfit=best(pop,fitvalue); z(i)=max(bestfit) %个体适应度的最大值 n(i)=i; x(i)=decodechrom(bestindividual,1,chromlength/2)*8/8191-4 %将二进制的数转换为十进制数然后归一化到0-10之间 y(i)=decodechrom(bestindividua

12、l,(chromlength/2+1),chromlength/2)*8/8191-4 pop=newpop;endfigure(1);i=1:1:200;hold on;plot(i,avefitvalue)plot(i,z)xlabel('迭代次数');ylabel('函数值');legend('种群平均适应度','种群最大适应度');figure(2);plot3(x,y,z,'r+')hold onx1=-4:0.1:4;x2=-4:0.1:4;xx,yy=meshgrid(x1,x2);z1=xx.2+y

13、y.2;z=0.5-(sin(sqrt(z1).2-0.5)./(1+0.001*(z1).2);mesh(xx,yy,z)grid on;2 种群初始化函数%初始化%function pop=initpop(popsize,chromlength)pop=round(rand(popsize,chromlength);3计算个体适应度函数%计算个体的适应度function fitvalue=calfitvalue(objvalue) %这里的objvalue是一个列向量global Cmin; Cmin=0;% display(objvalue);px,py=size(objvalue);

14、%这里px是种群大小，py=1 for i=1:px if objvalue(i)+Cmin>0 %计算出的目标函数值小于0则适应度为0 temp=Cmin+objvalue(i); else temp=0.0; end fitvalue(i)=temp;end% display(fitvalue);fitvalue=fitvalue' %将行向量转化为列向量4选择复制函数%选择复制%function newpop=selection(pop,fitvalue)totalfit=sum(fitvalue); %求所有适应度之和fitvalue=fitvalue/totalfit%

15、单个个体被选择的概率fitvalue=cumsum(fitvalue) %累计概率 px,py=size(pop);ms=sort(rand(px,1)fitin=1;newin=1;while newin<=px if (ms(newin)<fitvalue(fitin) newpop(newin,:)=pop(fitin,:); newin=newin+1; else fitin=fitin+1; endend5交叉重组函数%交叉重组%function newpop=crossover_multiv(pop,pc)px,py=size(pop); pop1=ones(px,py

16、); pop2=pop; for i=1:2:px-1 if(rand<pc) cpoint=round(rand*(py-1) % cpoint为交叉点 pop1(i,:)=pop2(i,1:cpoint) pop2(i+1,cpoint+1:py) pop1(i+1,:)=pop2(i+1,1:cpoint) pop2(i,cpoint+1:py) else pop1(i,:)=pop2(i,1:py) %若不交叉 则直接复制到下一代 pop1(i+1,:)=pop2(i+1,1:py) end endnewpop=pop1;6变异函数%变异函数%function newpop=mu

17、tation(pop,pm)px,py=size(pop);newpop=ones(size(pop);for i=1:px if(rand<pm) mpoint=round(rand*py); if mpoint<=0 mpoint=1; end newpop(i,:)=pop(i,:); if any(newpop(i,mpoint)=0 newpop(i,mpoint)=1; else newpop(i,mpoint)=0; end else newpop(i,:)=pop(i,:); endend7 模拟退火算法functionBestX,BestY=SimulateAnn

18、ealing1clear;clc;%要求最优值的目标函数，搜索的最大区间XMAX=4;YMAX=4;MarkovLength=1000; %马可夫链长度DecayScale=0.95; %衰减参数StepFactor=0.002 %步长因子Temperature=30Tolerance=1e-7;AcceptPoints=0.0; %Metropolis过程中总的接收点个数rnd=rand;PreX=-XMAX*rand;PreY=-YMAX*rand;PreBestX=PreX;PreBestY=PreY;PreX=-XMAX*rand;PreY=-YMAX*rand;BestX=PreX;

19、BestY=PreY;%每迭代一次退火一次 知道满足迭代条件为止mm=abs(ObjectFunction(BestX,BestY)-ObjectFunction(PreBestX,PreBestY);k=0;while mm>Tolerance Temperature=DecayScale*Temperature AcceptPoints=0.0; %在当前温度T下迭代马尔科夫链长度的次数 for i=0:1:MarkovLength %第一步：在此点附近随机选取下一点 p=0; while p=0; NextX=PreX+StepFactor*XMAX*(rand-0.5) Next

20、Y=PreY+StepFactor*YMAX*(rand-0.5) if p=(NextX >= -XMAX && NextX <= XMAX && NextY >= -YMAX && NextY <= YMAX)% 随机点如果在设定范围内 则跳出while循环 p=1; end end %第二步：检查是否为全局最优点 if(ObjectFunction(BestX,BestY)>ObjectFunction(NextX,NextY) PreBestX=BestX; PreBestY=BestY; %先把上一个最优点保留下来 BestX=NextX; BestY=NextY; %此为新的最优解 end %第三步：进行Metroplis过程 if(ObjectFunction(PreX,Pre