基于搜索空間大小的動態變異算子差分進化算法①

苗曉鋒,劉志偉

1(榆林職業技術學院神木校區 信息中心,神木 719300)

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

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

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

1 差分進化算法

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

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

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

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

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

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

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

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

選擇操作：決定Ui,G和Xi,G二者當中哪一個成為下一代G+1 種群的成員.對求最優值問題而言,能得到更好目標值的解將被選中繼續進行迭代運算.

2 根據搜索空間大小動態調整變異算子的算法

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

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

本文提出了一種新的動態變異算子,即根據當前搜索空間的大小動態調整局部搜索的步長,算子定義如下：

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

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

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

其中,PS是種群規模,best 是當前最優解,NE是函數運行次數,MAXNE是函數運行最大次數.

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

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

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

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

可見,在進化開始時b(t)-a(t)值和最優適應值很大,在進化的最后階段,最優適應值和b(t)-a(t)很小,

算法迅速收斂.

3 基準函數測試試驗

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

表1 測試函數

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

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

表2中給出了測試函數的求解結果,其中Mean 表示上一代最優解的平均值,STD 代表標準方差.

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

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

表2 測試結果

4 結論與展望

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

圖2 改進DE 求解f1 時的收斂過程

圖3 改進DE 求解f3 時的收斂過程