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

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

2、才替換種群中的個(gè)體。變異是DE算法的主要操作，它是基于群體的差異向量來(lái)修正各個(gè)體的值，其基本原理是通過(guò)把種群中兩個(gè)個(gè)體的向量差加權(quán)后，按一定的規(guī)劃與第三個(gè)個(gè)體求和來(lái)產(chǎn)生新個(gè)體，然后將新個(gè)體與當(dāng)代種群中某個(gè)預(yù)先決定的個(gè)體相比較，如果新個(gè)體的目標(biāo)值優(yōu)于與之相比較的個(gè)體的目標(biāo)值，則在下一代中就用新個(gè)體取代，否則，舊個(gè)體仍保存下來(lái)。差分進(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)種群的進(jìn)化。2 差分進(jìn)化算法的基本操作設(shè)當(dāng)前進(jìn)化代數(shù)為，群體

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

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

5、得到試驗(yàn)個(gè)體。(6) 選擇操作：按(3)式從父代個(gè)體和試驗(yàn)個(gè)體中選擇一個(gè)作為下一代個(gè)體。(7) 終止檢驗(yàn)：由上述產(chǎn)生的新一代種群，設(shè)X(t+1)中的最優(yōu)個(gè)體為，如果達(dá)到最大進(jìn)化代數(shù)或滿(mǎn)足誤差要求，則停止進(jìn)化并輸出為最優(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=);F=input(請(qǐng)輸入縮放因子F=);CR=input(請(qǐng)輸入交叉因子CR=);U=input(請(qǐng)輸入運(yùn)行的次數(shù)U=);Tmax=input(請(qǐng)

6、輸入最大迭代次數(shù)Tmax=);%變量限制a1=ones(1,30)*(-5.12); b1=ones(1,30)*(5.12);eps=1e-9;x=;v=;y=;%隨機(jī)產(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(1);Xb=x(1,:);%計(jì)算每個(gè)個(gè)體的適應(yīng)度值及當(dāng)前種群的最優(yōu)值for i=2:N cost(i)=fitness(x(i,:),D); if(cost(i

7、)=Pb) Pb=cost(i); Xb=x(i,:); endendticsum=0;for z=1:Uwhile(t1 a=floor(rand*N)+1; if a=i break; end end while 21 b=floor(rand*N)+1; if b=i&b=a break; end end while 21 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 %對(duì)每個(gè)個(gè)體進(jìn)行交叉操作，得試驗(yàn)個(gè)體 jrand=floor(rand*D+1);

8、 for k=1:D if(randCR|jrand=k) trial(k)=v(k); else trial(k)=x(i,k); end if 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; end if cost(i)=Pb Pb=cost(i); Xb(1:D)=x(i,1:D); end end t=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:U if Pbmaxy(z) Pbmin=y(z); endendtocdisp(*)Tm