苗曉鋒,劉志偉

1(榆林職業(yè)技術(shù)學(xué)院神木校區(qū) 信息中心,神木 719300)

2(西北工業(yè)大學(xué) 信息中心,西安 710072)

差分進(jìn)化(Differental Evolution,DE)是由Price 和Storn[1]首先提出的一種簡單高效的基于群體的隨機(jī)搜索算法.作為遺傳算法的一個分支,DE 的性能在很大程度上受到其控制參數(shù)(收縮因子和雜交概率)的影響[2,3].選擇不同的策略和控制參數(shù)會導(dǎo)致不同的算法性能,尤其會在很大程度上決定最終所能獲得最優(yōu)解的求解效率和質(zhì)量[4].而選擇適當(dāng)?shù)膮?shù)值是一個與待求解問題自身特征相關(guān)的問題,通常由使用者根據(jù)主觀經(jīng)驗決定.許多研究都嘗試更好地解決這個問題,例如自適應(yīng)控制參數(shù)DE(SADE)[4],模糊DE(FADE)[5],自適應(yīng)DE(SaDE)[6]和相鄰搜索自適應(yīng)DE(SaNSDE)[7]等改進(jìn)DE 算法.

本文引入一種可根據(jù)進(jìn)化代數(shù)實時調(diào)整變異策略步長的動態(tài)變異算子,以變異策略的改變來優(yōu)化DE 性能,并將采用了這種動態(tài)變異算子的IDE(Improved DE)算法和已有的SADE[4],古典進(jìn)化規(guī)劃(CEP)[8]和快速進(jìn)化規(guī)劃(FEP)[8]等既有算法進(jìn)行了仿真比較研究.

1 差分進(jìn)化算法

差分進(jìn)化(DE)算法是一種基于種群和定向搜索策略的遺傳算法[1].它的求解過程與其它仿生算法類似,都是從一個隨機(jī)生成的初始解種群開始,模仿生物進(jìn)化過程中基因變異和雜交的過程進(jìn)行迭代求解,直至找到最終最優(yōu)解.

DE 有多種最基本的形式[1],最著名的一種是標(biāo)準(zhǔn)DE 即“DE/rand/1/bin”.該算法工作時首先隨機(jī)生成一組初始解,然后通過變異和雜交操作產(chǎn)生一組對應(yīng)的試驗解,再根據(jù)最優(yōu)適應(yīng)值函數(shù)判斷哪些試驗解能作為下一代解種群成員,然后迭代進(jìn)行以上操作,直至所得到當(dāng)前解種群的精度達(dá)到要求時即停止求解循環(huán).

首先,定義Xri,G(i=1,2,···,Np)是第G代種群的解向量,其中NP是種群的大小,

變異操作：每個G代種群中的解Xri,G變異生成一個試驗解Vi,G,定義如下

其中,i=1,2,···,Np,r1,r2和r3是集合{ 1,2,···,Np}中任意互不相等隨機(jī)整數(shù),F是縮放系數(shù).

雜交操作：如同其它遺傳算法一樣,DE 也利用雜交算子結(jié)合兩個不同的解來生成試驗解,該試驗解定義如下：

其中,j=1,2,···,D(D是問題維數(shù)).

其中,CR 是預(yù)先定義好的雜交概率,randj(0,1)是(0,1)范圍內(nèi)的任意隨機(jī)數(shù),k∈{1,2,···,D}也是隨機(jī)數(shù).

選擇操作：決定Ui,G和Xi,G二者當(dāng)中哪一個成為下一代G+1 種群的成員.對求最優(yōu)值問題而言,能得到更好目標(biāo)值的解將被選中繼續(xù)進(jìn)行迭代運(yùn)算.

2 根據(jù)搜索空間大小動態(tài)調(diào)整變異算子的算法

經(jīng)典DE 算法的性能很大程度上受到其控制參數(shù)(收縮因子和雜交概率）的影響,不同的參數(shù)選擇和變異策略會導(dǎo)致不同的算法性能.

在已有研究成果中,Yao 和Liu[9]提出了一種引入三角變異算子的DE,可以在算法的收斂速度和魯棒性兩者間取得較好的平衡.He 等[10]采用了輔助種群和放大因子F的自動計算.Shi[11]提出了結(jié)合DE 和分布估計的DE/EDA 算法.Liu 和Lampinen[3]提出了一種模糊自適應(yīng)DE(FADE）,它使用一個模糊邏輯控制器設(shè)置雜交與變異概率.Brest 等[5]研究了采用自適應(yīng)控制參數(shù)的DE(SADE）.SADE 采用自適應(yīng)控制機(jī)制調(diào)整參數(shù)F 和CR.Qin 和Suganthan[4]提出了一種自適應(yīng)DE(SaDE),研究參數(shù)CR 和變異策略的適應(yīng)性.Yang 等人[6]提出了鄰域搜索策略DE(NSDE),它利用服從高斯和柯西分布的隨機(jī)數(shù)生成參數(shù)F,而不是預(yù)定義常數(shù)F.基于SaDE 和NSDE,Yang 等人[6]提出了另一個版本的DE(SaNSDE）,它吸收了SaDE 和NSDE 的優(yōu)點.苗曉鋒等[12]提出了一種基于混合策略的HDE.雖然以上方法都采用加權(quán)因子的方法來控制變異步長,但很難解決待求解問題被自身特征支配的缺陷.

本文提出了一種新的動態(tài)變異算子,即根據(jù)當(dāng)前搜索空間的大小動態(tài)調(diào)整局部搜索的步長,算子定義如下：

其中,xj是解個體x的第j維向量,aj(t)和bj(t)分別是當(dāng)前搜索空間第j維的最小值和最大值.rand()是[0,1]區(qū)間上的隨機(jī)數(shù),PS 是種群規(guī)模大小,t= 1,2,…,指進(jìn)化代數(shù).

采用了該算子的IDE 算法流程如下：

Begin WhileNE＜MAXNEdo Fori= 1 toPSdo根據(jù)式(1)和式(2)生成一個試驗向量;計算試驗向量的適應(yīng)值;在Xi和試驗向量中選擇具有更好適應(yīng)度的一個進(jìn)入下一代種群;

其中,PS是種群規(guī)模,best 是當(dāng)前最優(yōu)解,NE是函數(shù)運(yùn)行次數(shù),MAXNE是函數(shù)運(yùn)行最大次數(shù).

在IDE 算法中,bj(t)-aj(t)可以被視為當(dāng)前種群搜索空間變異步長的放大率.在進(jìn)化初期,初始搜索空間大,步長bj(t)-aj(t)也大,此時較大的步長有利于覆蓋全局搜索,便于發(fā)現(xiàn)潛在的更優(yōu)解,同時加快算法收斂.隨著代數(shù)的增加,種群將逐漸收斂到當(dāng)前最優(yōu)值附近,此時當(dāng)前種群的搜索空間和步長bj(t)-aj(t)均變小.在這種情況下,較小的bj(t)-aj(t)值將更有利于在小范圍局部搜索.

通過對著名的基準(zhǔn)測試函數(shù)simple Sphere’s problem 進(jìn)行求解,并選取當(dāng)前解第一維b(t)-a(t)的變化進(jìn)行記錄,結(jié)果如圖1所示.

圖1 b(t)-a(t)值的收斂過程

End For根據(jù)式(4)計算aj(t)和bj(t);根據(jù)式(3)對最優(yōu)個體best 進(jìn)行變異操作;if best(t+1)的適應(yīng)值優(yōu)于best 的適應(yīng)值best = best(t+1);if end End While End

可見,在進(jìn)化開始時b(t)-a(t)值和最優(yōu)適應(yīng)值很大,在進(jìn)化的最后階段,最優(yōu)適應(yīng)值和b(t)-a(t)很小,

算法迅速收斂.

3 基準(zhǔn)函數(shù)測試試驗

為了測試算法性能,選擇了三個單峰函數(shù)(f1-f3)和一個多峰函數(shù)(f4)來進(jìn)行MATLAB 環(huán)境下的仿真求解實驗.表1中給出了所有基準(zhǔn)測試函數(shù)、變量維數(shù)、定義域及其全局最優(yōu)解.

表1 測試函數(shù)

我們將常用的CEP、FEP、SADE 和IDE 四種算法進(jìn)行比較,四種算法分別對四個測試函數(shù)進(jìn)行求解運(yùn)算.參數(shù)設(shè)置如下：

種群規(guī)模PS設(shè)置為50,控制參數(shù)CR和F分別設(shè)置為0.9 和0.5,函數(shù)調(diào)用最大次數(shù)MAXNE分別設(shè)置為150 000 (f1和f4),200 000 (f2),500 000 (f3).

表2中給出了測試函數(shù)的求解結(jié)果,其中Mean 表示上一代最優(yōu)解的平均值,STD 代表標(biāo)準(zhǔn)方差.

顯然,在同等條件下,SADE 對于前三個單峰函數(shù)的求解精度平均優(yōu)于CEP 和FEP 多達(dá)e+24 倍、e+20 倍和e+12 倍,對第四個多峰函數(shù)的求解精度平均優(yōu)于兩種算法e+15 和e+13 倍.而IDE 的求解精度又遠(yuǎn)優(yōu)于SADE,上述優(yōu)勢分別達(dá)到了e+27、e+25 和e+16 倍.只是在最后一個多峰函數(shù)上,IDE 和SADE 的求解精度數(shù)量級相同,但它的當(dāng)前最優(yōu)解的值比SADE 的值更接近于最終全局最優(yōu)解.

其中IDE 對測試函數(shù)f1和f3求解時的收斂過程分別如圖2和圖3所示,可見其收斂過程也非常迅速,并未陷入局部最優(yōu).

表2 測試結(jié)果

4 結(jié)論與展望

本文提出了一種改進(jìn)的IDE 算法,該方法可以根據(jù)當(dāng)前搜索空間的大小動態(tài)調(diào)整變異步長.四個著名的基準(zhǔn)測試函數(shù)求解實驗表明,所提出的IDE 算法在同等條件下求解精度大大優(yōu)于CEP、FEP 和SADE.今后的工作是嘗試更多的進(jìn)化和參數(shù)設(shè)置策略,以研究其對DE 算法性能的影響.

圖2 改進(jìn)DE 求解f1 時的收斂過程

圖3 改進(jìn)DE 求解f3 時的收斂過程