差分進化算法-入門

1、差分進化算法-入門差分進化算法-入門11基本差分進化算法1基本差分進化算法的基本思想DE算法是一種基于實數(shù)編碼的用于優(yōu)化函數(shù)最小值的進化算法，是在求解有關(guān)切比雪夫多項式的問題時提出來的，是基于群體差異的進化計算方法。它的整體結(jié)構(gòu)類似于遺傳算法，一樣都存在變異、交叉和選擇操作，但是它又不同于遺傳算法。與基本遺傳算法的主要區(qū)別在于變異操作上，如：1、傳統(tǒng)的遺傳算法采用二進制編碼，而差分進化算法采用實數(shù)編碼。2、在遺傳算法中通過兩個父代個體的交叉產(chǎn)生兩個子個體，而在差分進化算法中通過第兩個或幾個個體的差分矢量做擾動來產(chǎn)生新個體。3、在傳統(tǒng)的遺傳算法中，子代個體以一定概率取代其父代個體，而在差分進化中

2、新產(chǎn)生的個體只有當(dāng)它比種群中的個體優(yōu)良時才替換種群中的個體。變異是DE算法的主要操作，它是基于群體的差異向量來修正各個體的值，其基本原理是通過把種群中兩個個體的向量差加權(quán)后，按一定的規(guī)劃與第三個個體求和來產(chǎn)生新個體，然后將新個體與當(dāng)代種群中某個預(yù)先決定的個體相比較，如果新個體的目標(biāo)值優(yōu)于與之相比較的個體的目標(biāo)值，則在下一代中就用新個體取代，否則，舊個體仍保存下來。差分進化算法其基本思想是：首先由父代個體間的變異操作構(gòu)成變異個體；接著按一定的概率，父代個體與變異個體之間進行交叉操作，生成一試驗個體；然后在父代個體與試驗個體之間根據(jù)適應(yīng)度的大小進行貪婪選擇操作，保留較優(yōu)者，實現(xiàn)種群的進化。2 差分

3、進化算法的基本操作設(shè)當(dāng)前進化代數(shù)為，群體規(guī)模為，空間維數(shù)為，當(dāng)前種群為，為種群中的第個個體。在進化過程中，對于每個個體依次進行下面三種操作。2.1 變異操作對于每個個體按下式產(chǎn)生變異個體，則 (1)其中，和是群體中隨機選擇的三個個體，并且；，和分別為個體，和的第維分量；為變異因子，一般取值于。這樣就得到了變異個體。2.2 交叉操作由變異個體和父代個體得到試驗個體，則 (2)其中，是間的隨機數(shù)；是范圍在間的常數(shù)，稱為交叉因子，值越大，發(fā)生交叉的可能性就越大；是在隨機選擇的一整數(shù)，它保證了對于試驗個體至少要從變異個體中獲得一個元素。以上的變異操作和交叉操作統(tǒng)稱為繁殖操作。2.3 選擇操作差分進化算

4、法采用的是“貪婪”選擇策略，即從父代個體和試驗個體中選擇一個適應(yīng)度值最好的作為下一代的個體，選擇操作為： (3)其中，為適應(yīng)度函數(shù)，一般以所要優(yōu)化的目標(biāo)函數(shù)為適應(yīng)度函數(shù)。本文的適應(yīng)度函數(shù)如無特殊說明均為目標(biāo)函數(shù)且為求函數(shù)極小值。3 差分進化算法的算法流程由前面對基本差分進化算法的基本原理的了解，我們可以得到差分進化算法的算法流程設(shè)計如下。3.1 基本差分進化算法的基本步驟(1) 初始化參數(shù)：種群規(guī)模；縮放因子；變異因子；空間維數(shù)；進化代數(shù)。(2) 隨機初始化初始種群，其中。(3) 個體評價：計算每個個體的適應(yīng)度值。(4) 變異操作：按(1)式對每個個體進行變異操作，并得到變異個體。(5) 交叉

5、操作：按(2)式對每個個體進行交叉操作，得到試驗個體。(6) 選擇操作：按(3)式從父代個體和試驗個體中選擇一個作為下一代個體。(7) 終止檢驗：由上述產(chǎn)生的新一代種群，設(shè)X(t+1)中的最優(yōu)個體為，如果達到最大進化代數(shù)或滿足誤差要求，則停止進化并輸出為最優(yōu)解，否則令t=t+1 ,轉(zhuǎn)(3)。3.2 基本差分進化算法的流程圖差分進化算法流程圖4 基本差分進化算法的MATLAB描述function Pb=DE%參數(shù)初始化D=input('請輸入空間維數(shù)D=');N=input('請輸入種群規(guī)模N=');F=input('請輸入縮放因子F=');CR=

6、input('請輸入交叉因子CR=');U=input('請輸入運行的次數(shù)U=');Tmax=input('請輸入最大迭代次數(shù)Tmax=');%變量限制a1=ones(1,30)*(-5.12); b1=ones(1,30)*(5.12);eps=1e-9;x=;v=;y=;%隨機產(chǎn)生初始種群for i=1:N for j=1:D x(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(

7、1);Xb=x(1,:);%計算每個個體的適應(yīng)度值及當(dāng)前種群的最優(yōu)值for i=2:N cost(i)=fitness(x(i,:),D); if(cost(i)<=Pb) Pb=cost(i); Xb=x(i,:); endendticsum=0;for z=1:Uwhile(t<Tmax)for 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 whi

8、le 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(rand<CR|jrand=k) trial(k)=v(k); else trial(k)=x(i,k); end if trial(k)<a1(k) trial(k)=a1(k); end if trial(k)>b1(k) trial(k)=b1

9、(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;endy(z)=Pb;%計算平均適應(yīng)最優(yōu)值sum=Pb+sum;endPbavr=sum/U;%U次中的最差值和最好值Pbmax=y(1);Pbmin=y(1);for z=1:U if Pbmax<y(z) Pbmax=y(z); end if Pbmin>y(z) Pbmin=y(z); endendtocdisp('*'