差分进化算法-入门

1基本差分进化算法的基本思想

DE算法是一种基于实数编码的用于优化函数最小值的进化算法，是在求解有关切比雪夫多项式的问题时提出来的，是基于群体差异的进化计算方法。它的整体结构类似于遗传算法，一样都存在变异、交叉和选择操作，但是它又不同于遗传算法。与基本遗传算法的主要区别在于变异操作上，如：

1、传统的遗传算法采用二进制编码，而差分进化算法采用实数编码。 2、在遗传算法中通过两个父代个体的交叉产生两个子个体，而在差分进化算法中通过第两个或几个个体的差分矢量做扰动来产生新个体。

3、在传统的遗传算法中，子代个体以一定概率取代其父代个体，而在差分进化中新产生的个体只有当它比种群中的个体优良时才替换种群中的个体。

变异是DE算法的主要操作，它是基于群体的差异向量来修正各个体的值，其基本原理是通过把种群中两个个体的向量差加权后，按一定的规划与第三个个体求和来产生新个体，然后将新个体与当代种群中某个预先决定的个体相比较，如果新个体的目标值优于与之相比较的个体的目标值，则在下一代中就用新个体取代，否则，旧个体仍保存下来。

差分进化算法其基本思想是：首先由父代个体间的变异操作构成变异个体；接着按一定的概率，父代个体与变异个体之间进行交叉操作，生成一试验个体；然后在父代个体与试验个体之间根据适应度的大小进行贪婪选择操作，保留较优者，实现种群的进化。 2 差分进化算法的基本操作

设当前进化代数为t，群体规模为NP，空间维数为D，当前种群为

X(t)x,x,t1t2,xtNP，xx,xtiti1ti2,,xTtiD为种群中的第i个个体。在进化过程

中，对于每个个体xit依次进行下面三种操作。 2.1 变异操作

对于每个个体xit按下式产生变异个体vit(vit1,vit2,tT,viD)，则

ttttvijxrF(xx) j1,2,jrjr123j,D (1)

tT是群,xr)3Dttt其中xr(x,x,rr11112tTttt，,xr)x(x,xr2r21r22,1DtTttt和,xr)x(x,xr3r31r32,2D体中随机选择的三个个体，并且r1r2r3i；xrt1j，xrt2j和xrt3j分别为个体r1，r2和r3的第j维分量；F为变异因子，一般取值于[0,2]。这样就得到了变异个体vit。

学习文档 仅供参考

2.2 交叉操作

由变异个体vit和父代个体xit得到试验个体uit(uit1,uit2,tT,uiD)，则

tvij if rand[0 1]CR or jj_randt (2) uijtxij if rand[0 1]CR and jj_randCR是范围在[0,1]间的常数，其中，称为交叉因子，rand[0,1]是[0,1]间的随机数；CR值越大，发生交叉的可能性就越大；j_rand是在[1,D]随机选择的一整数，

它保证了对于试验个体uit至少要从变异个体vit中获得一个元素。以上的变异操作和交叉操作统称为繁殖操作。 2.3 选择操作

差分进化算法采用的是“贪婪”选择策略，即从父代个体xit和试验个体uit中选择一个适应度值最好的作为下一代的个体xit+1，选择操作为：

tttx if fitness (x)fitness(uiii)t1xit (3)

ui otherwise其中，fitness()为适应度函数，一般以所要优化的目标函数为适应度函数。本文的适应度函数如无特殊说明均为目标函数且为求函数极小值。 3 差分进化算法的算法流程

由前面对基本差分进化算法的基本原理的了解，我们可以得到差分进化算法的算法流程设计如下。

3.1 基本差分进化算法的基本步骤

(1) 初始化参数：种群规模NP；缩放因子F；变异因子CR；空间维数D；进化代数t0。

t,(2) 随机初始化初始种群X(t)x1t,x2t,xNP，其中xitxit1,xit2,t,xiD。

T(3) 个体评价：计算每个个体的适应度值。

(4) 变异操作：按(1)式对每个个体进行变异操作，并得到变异个体vit。 (5) 交叉操作：按(2)式对每个个体进行交叉操作，得到试验个体uit。 (6) 选择操作：按(3)式从父代个体xit和试验个体uit中选择一个作为下一代个体。

学习文档 仅供参考

t1,(7) 终止检验：由上述产生的新一代种群X(t1)x1t1,x2t1,xNP设X(t+1)，

t1中的最优个体为xbest，如果到达最大进化代数或满足误差要求，则停止进化并输t1出xbest为最优解，否则令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=[];

%随机产生初始种群

for i=1:N for j=1:D

x(i,j)=a1(j)+rand*(b1(j)-a1(j)); end end t=1;

trial=zeros(1,D); cost=zeros(1,N);

cost(1)=fitness(x(1,:),D); Pb=cost(1); Xb=x(1,:);

%计算每个个体的适应度值及当前种群的最优值 for i=2:N

cost(i)=fitness(x(i,:),D); if(cost(i)<=Pb) Pb=cost(i);

Xb=x(i,:); end end tic

sum=0; for z=1:U

while(tfor i=1:N

%对每个个体进行变异操作，得变异个体 while 2>1

a=floor(rand*N)+1; if a~=i break; end end

while 2>1

b=floor(rand*N)+1; if b~=i&b~=a

学习文档 仅供参考

break; end end

while 2>1

c=floor(rand*N)+1; if c~=i&c~=a&c~=b break; end end

for k=1:D

v(k)=x(c,k)+F*(x(a,k)-x(b,k)); end

%对每个个体进行交叉操作，得试验个体 jrand=floor(rand*D+1); for k=1:D

if(randtrial(k)=x(i,k); end

if trial(k)if trial(k)>b1(k) trial(k)=b1(k); end end

%对每个个体进行选择操作，得下一代个体 score=fitness(trial(:),D); if(score<=cost(i))

x(i,1:D)=trial(1:D); cost(i)=score; end

if cost(i)<=Pb Pb=cost(i);

Xb(1:D)=x(i,1:D); end end t=t+1; end

y(z)=Pb;

学习文档 仅供参考

%计算平均适应最优值 sum=Pb+sum; end

Pbavr=sum/U;

%U次中的最差值和最好值 Pbmax=y(1); Pbmin=y(1); for z=1:U

if Pbmaxif Pbmin>y(z) Pbmin=y(z); end end toc

disp('***************************************') Tmax y

Pbmax Pbmin Pbavr

disp('***************************************')

%适应度函数

%--------------------------------------------- function eval=fitness(x,D) sol=x; eval=0;

for i=1:D-1

eval=eval+(sol(i)^2-10*cos(2*pi*sol(i))+10); end

%---------------------------------------------

学习文档 仅供参考