差分進(jìn)化算法-入門

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

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

3、的進(jìn)化。2 差分進(jìn)化算法的基本操作設(shè)當(dāng)前進(jìn)化代數(shù)為t，群體規(guī)模為NP，空間維數(shù) 為D，當(dāng)前種群為 X(t) x1t ,x2t ,L ,xtNP ， xit xit1,xit2,L ,xitD 為種群中的第 i 個(gè)個(gè)體。 在進(jìn)化過程 中，對(duì)于每個(gè)個(gè)體 xit 依次進(jìn)行下面三種操作 。2.1 變異操作對(duì)于每個(gè)個(gè)體 x it按下式產(chǎn)生 變異個(gè)體 vit (vit1,vit2,L ,vitD)T ，則vitj xrt1j F(xrt2j xrt3j ) j 1,2,L ,D (1其中 xrt1(xrt11, xtr12 ,L ,xrt1D )T ， xrt2tt(xr21,xr22,L ,xrt2D

4、)T 和 xtr3tt(xr31,xr32,L ,xr3D ) 是群體中隨機(jī)選擇的三個(gè)個(gè)體，并且 r1i ； xrt1 j ， xtr2 j和 xtr3j 分別為個(gè)體 r1， r2和 r3 的第 j 維分量； F 為變異因子，一般取值于 0,2 。這樣就得到了變異個(gè)體 vit2.2 交叉操作由變異個(gè)體 vit 和父代個(gè)體 x it得到試驗(yàn)個(gè)體 uit (uit1,uit2,L ,uitD)T ，則tuitjvitj if rand0 1 CR or j j_rand xitj if rand0 1 CR and j j_rand其中，rand 0,1是0,1間的隨機(jī)數(shù)； CR是范圍在 0,1間

5、的常數(shù)，稱為交叉因子，CR值越大，發(fā)生交叉的可能性就越大； j _ rand 是在1,D 隨機(jī)選擇的一整數(shù)， 它保證了對(duì)于試驗(yàn)個(gè)體 uit至少要從變異個(gè)體 vit 中獲得一個(gè)元素 。以上的變異操 作和交叉操作統(tǒng)稱為繁殖操作。2.3 選擇操作差分進(jìn)化算法采用的是 “貪婪”選擇策略，即從父代個(gè)體 xit 和試驗(yàn)個(gè)體 uit中選擇一個(gè)適應(yīng)度值最好的作為下一代的個(gè)體x it+ 1 ，選擇操作為：t1xixit if f itness (xit ) fitness(uit ) uit otherwise(3)其中， fitness( ) 為適應(yīng)度函數(shù)，一般以所要優(yōu)化的目標(biāo)函數(shù)為適應(yīng)度函數(shù)。本 文的適應(yīng)度

6、函數(shù)如無特殊說明均為目標(biāo)函數(shù) 且為求函數(shù)極小值 。3 差分進(jìn)化算法的算法流程由前面對(duì)基本差分進(jìn)化算法的基本原理的了解， 我們可以得到差分進(jìn)化算法 的算法流程設(shè)計(jì)如下。3.1 基本差分進(jìn)化算法的基本步驟CR；空間維數(shù) D ；(1) 初始化參數(shù)：種群規(guī)模 NP ；縮放因子 F ；變異因子 進(jìn)化代數(shù) t 0 。(2)隨機(jī)初始化初始種群 X(t) x1t , xt2 ,L ,xtNP ，其中 xitxit1,xit2,L ,xitD T 。(3)個(gè)體評(píng)價(jià)：計(jì)算每個(gè)個(gè)體的適應(yīng)度值。(4)變異操作：按 (1) 式對(duì)每個(gè)個(gè)體進(jìn)行變異操作，并得到變異個(gè)體tvi 。(5)交叉操作：按 (2) 式對(duì)每個(gè)個(gè)體進(jìn)行交

7、叉操作，得到試驗(yàn)個(gè)體tui 。選擇操作：按(3)式從父代個(gè)體 xit 和試驗(yàn)個(gè)體 uit中選擇一個(gè)作為下一代個(gè)體。則停止進(jìn)化并輸中的最優(yōu)個(gè)體為 xbtes1t ，如果達(dá)到最大進(jìn)化代數(shù)或滿足誤差要求， 出 xbtes1t為最優(yōu)解，否則令 t=t+1 ,轉(zhuǎn)(3)。3.2 基本差分進(jìn)化算法的流程圖差分進(jìn)化算法流程圖4 基本差分進(jìn)化算法的 MATLAB 描述function Pb=DE%參數(shù)初始化D=input(' 請(qǐng)輸入空間維數(shù) D=');N=input(' 請(qǐng)輸入種群規(guī)模 N=');Tmax=');F=input(' 請(qǐng)輸入縮放因子 F=')

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

9、st(1);Xb=x(1,:);% 計(jì)算每個(gè)個(gè)體的適應(yīng)度值及當(dāng)前種群的最優(yōu) 值for i=2:Ncost(i)=fitness(x(i,:),D);if(cost(i)<=Pb)Pb=cost(i);Xb=x(i,:);end end tic sum=0; for z=1:Uwhile(t<Tmax) for i=1:N%對(duì)每個(gè)個(gè)體進(jìn)行變異操作，得變異個(gè)體while 2>1a=floor(rand*N)+1;if a=i break;endend while 2>1b=floor(rand*N)+1;if b=i&b=a break;endend while 2

10、>1c=floor(rand*N)+1;if c=i&c=a&c=b break;endendfor k=1:Dv(k)=x(c,k)+F*(x(a,k)-x(b,k); end%對(duì)每個(gè)個(gè)體進(jìn)行交叉操作，得試驗(yàn)個(gè)體 jrand=floor(rand*D+1);for k=1:Dif(rand<CR|jrand=k)trial(k)=v(k); elsetrial(k)=x(i,k); end if trial(k)<a1(k)trial(k)=a1(k);endif trial(k)>b1(k)trial(k)=b1(k); end end%對(duì)每個(gè)個(gè)體進(jìn)行選擇操作，得下一代個(gè)體score=fitness(trial(:),D);if(score<=cost(i)x(i,1:D)=trial(1:D);cost(i)=score;endif cost(i)<=PbPb=cost(i);Xb(1:D)=x(i,1:D);endendt=t+1;endy(z)=Pb;%計(jì)算平均適應(yīng)最優(yōu)值 sum=Pb+sum;endPbavr=sum/U;%U 次中的最差值和最好值Pbmax=y(1);Pbmin=y(1);for z=1:Uif Pbmax<y(z) Pbmax=y(z);endif Pbmin&