差分进化算法-入门

差分进化算法-入门基本差分进化算法1基本差分进化算法的基本思想DE算法是一种基于实数编码的用于优化函数最小值的进化算法，是在求解有关切比雪夫多项式的问题时提出来的，是基于群体差异的进化计算方法。它的整体结构类似于遗传算法，一样都存在变异、交叉和选择操作，但是它又不同于遗传算法。与基本遗传算法的主要区别在于变异操作上，如：1、传统的遗传算法采用二进制编码，而差分进化算法采用实数编码。2、在遗传算法中通过两个父代个体的交叉产生两个子个体，而在差分进化算法中通过第两个或几个个体的差分矢量做扰动来产生新个体。3、在传统的遗传算法中，子代个体以一定概率取代其父代个体，而在差分进化中新产生的个体只有当它比种群中的个体优良时才替换种群中的个体。变异是DE算法的主要操作，它是基于群体的差异向量来修正各个体的值，其基本原理是通过把种群中两个个体的向量差加权后，按一定的规划与第三个个体求和来产生新个体，然后将新个体与当代种群中某个预先决定的个体相比较，如果新个体的目标值优于与之相比较的个体的目标值，则在下一代中就用新个体取代，否则，旧个体仍保存下来。差分进化算法其基本思想是：首先由父代个体间的变异操作构成变异个体；接着按一定的概率，父代个体与变异个体之间进行交叉操作，生成一试验个体；然后在父代个体与试验个体之间根据适应度的大小进行贪婪选择操作，保留较优者，实现种群的进化。2差分进化算法的基本操作设当前进化代数为t，群体规模为NP，空间维数为D，当前种群为12(),,,tttNPXtxxx，12,,,TttttiiiiDxxxx为种群中的第i个个体。在进化过程中，对于每个个体tix依次进行下面三种操作。2.1变异操作对于每个个体tix按下式产生变异个体12(,,,)ttttTiiiiDvvvv，则123()1,2,,DttttijrjrjrjvxFxxj(1)其中111112(,,,)ttttTrrrrDxxxx，222212(,,,)ttttTrrrrDxxxx和333312(,,,)ttttTrrrrDxxxx是群体中随机选择的三个个体，并且123rrri；1trjx，2trjx和3trjx分别为个体1r，2r和3r的第j维分量；F为变异因子，一般取值于[0,2]。这样就得到了变异个体tiv。2.2交叉操作由变异个体tiv和父代个体tix得到试验个体12(,,,)ttttTiiiiDuuuu，则tijifrand[01]CRorjj_randxifrand[01]CRandjj_randtijtijvu(2)其中，[0,1]rand是[0,1]间的随机数；CR是范围在[0,1]间的常数，称为交叉因子，CR值越大，发生交叉的可能性就越大；_jrand是在[1,]D随机选择的一整数，它保证了对于试验个体tiu至少要从变异个体tiv中获得一个元素。以上的变异操作和交叉操作统称为繁殖操作。2.3选择操作差分进化算法采用的是“贪婪”选择策略，即从父代个体tix和试验个体tiu中选择一个适应度值最好的作为下一代的个体1t+ix，选择操作为：1ifitness()fitness()therwisetttiiititixfxuxuo(3)其中，()fitness为适应度函数，一般以所要优化的目标函数为适应度函数。本文的适应度函数如无特殊说明均为目标函数且为求函数极小值。3差分进化算法的算法流程由前面对基本差分进化算法的基本原理的了解，我们可以得到差分进化算法的算法流程设计如下。3.1基本差分进化算法的基本步骤(1)初始化参数：种群规模NP；缩放因子F；变异因子CR；空间维数D；进化代数0t。(2)随机初始化初始种群12(),,,tttNPXtxxx，其中12,,,TttttiiiiDxxxx。(3)个体评价：计算每个个体的适应度值。(4)变异操作：按(1)式对每个个体进行变异操作，并得到变异个体tiv。(5)交叉操作：按(2)式对每个个体进行交叉操作，得到试验个体tiu。(6)选择操作：按(3)式从父代个体tix和试验个体tiu中选择一个作为下一代个体。(7)终止检验：由上述产生的新一代种群11112(1),,,tttNPXtxxx，设X(t+1)中的最优个体为1tbestx，如果达到最大进化代数或满足误差要求，则停止进化并输出1tbestx为最优解，否则令t=t+1,转(3)。3.2基本差分进化算法的流程图满足条件生成初始群体NY变异交叉选择输出结果差分进化算法流程图4基本差分进化算法的MATLAB描述function[Pb]=DE%参数初始化D=input('请输入空间维数D=');N=input('请输入种群规模N=');F=input('请输入缩放因子F=');CR=input('请输入交叉因子CR=');U=input('请输入运行的次数U=');Tmax=input('请输入最大迭代次数Tmax=');%变量限制a1=ones(1,30)*(-5.12);b1=ones(1,30)*(5.12);eps=1e-9;x=[];v=[];y=[];%随机产生初始种群fori=1:Nforj=1:Dx(i,j)=a1(j)+rand*(b1(j)-a1(j));endendt=1;trial=zeros(1,D);cost=zeros(1,N);cost(1)=fitness(x(1,:),D);Pb=cost(1);Xb=x(1,:);%计算每个个体的适应度值及当前种群的最优值fori=2:Ncost(i)=fitness(x(i,:),D);if(cost(i)=Pb)Pb=cost(i);Xb=x(i,:);endendticsum=0;forz=1:Uwhile(tTmax)fori=1:N%对每个个体进行变异操作，得变异个体while21a=floor(rand*N)+1;ifa~=ibreak;endendwhile21b=floor(rand*N)+1;ifb~=i&b~=abreak;endendwhile21c=floor(rand*N)+1;ifc~=i&c~=a&c~=bbreak;endendfork=1:Dv(k)=x(c,k)+F*(x(a,k)-x(b,k));end%对每个个体进行交叉操作，得试验个体jrand=floor(rand*D+1);fork=1:Dif(randCR|jrand==k)trial(k)=v(k);elsetrial(k)=x(i,k);endiftrial(k)a1(k)trial(k)=a1(k);endiftrial(k)b1(k)trial(k)=b1(k);endend%对每个个体进行选择操作，得下一代个体score=fitness(trial(:),D);if(score=cost(i))x(i,1:D)=trial(1:D);cost(i)=score;endifcost(i)=PbPb=cost(i);Xb(1:D)=x(i,1:D);endendt=t+1;endy(z)=Pb;%计算平均适应最优值sum=Pb+sum;endPbavr=sum/U;%U次中的最差值和最好值Pbmax=y(1);Pbmin=y(1);forz=1:UifPbmaxy(z)Pbmax=y(z);endifPbminy(z)Pbmin=y(z);endendtocdisp('***************************************')TmaxyPbmaxPbminPbavrdisp('***************************************')%适应度函数%---------------------------------------------functioneval=fitness(x,D)sol=x;eval=0;fori=1:D-1eval=eval+(sol(i)^2-10*cos(2*pi*sol(i))+10);end%---------------------------------------------