一種基于混合策略的差分進化算法研究

苗曉鋒 劉志偉

1(榆林職業技術學院神木校區信息中心 陜西 神木 719300)2(西北工業大學信息中心 陜西 西安 710072)

0 引 言

差分進化DE是由Price和Storn[1]首先提出的一種簡單而強大的基于種群的隨機搜索技術。DE的性能在很大程度上取決于變異策略的選擇和相關參數的設置[2-3]，不同的策略和參數設置導致了不同的算法性能，尤其是參數值很大程度上決定了最終所能獲得最優解的質量和求解搜索的效率[4]。選擇適當的參數值與問題特性相關，往往需要依靠使用者的既有經驗。許多研究都嘗試解決這一問題，如模糊DE(FADE)[5]、自適應DE(SaDE)[6]、自適應控制參數DE(SADE)[4]和相鄰搜索自適應DE(SaNSDE)[7]等。

本文提出了一種基于混合策略的差分進化算法HDE，即結合反向學習機制和自適應控制參數的DE。通過求解兩個單峰函數和三個多峰函數所進行的測試實驗，將HDE與已有的ODE[3]、SADE[4]、CEP[8]和FEP[8]算法進行了性能比較。

1 差分進化算法

差分進化(DE)算法是一種基于種群和定向搜索策略的優化方法[1]。如同其他進化算法一樣，從一個隨機生成的初始解種群開始，模仿生物進化時基因變異和雜交的特點進行迭代求解，直至找到最終解。

DE有幾種最基本的形式[1]，最流行的一種是“DE/rand/1/bin”。該算法基于以下工作模式，即首先隨機生成初始試驗解，然后通過變異和雜交操作產生新的試驗解，再通過選擇操作決定哪些試驗解進入下一代種群成為候選解。反復進行變異、雜交和選擇的迭代操作，直至所得到當前解的精度達到要求時停止求解。

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

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

Vi,G=Xr1,G+F(Xr2,G-Xr3,G)

(1)

式中：i=1,2,…,Np；r1、r2和r3是集合{1,2,…,Np}中任意互不相等隨機整數；F是縮放系數。

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

Ui,G=(U1i,G,U2i,G,…,UDi,G)

式中：j=1,2,…,D(D是問題維數)，

(2)

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

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

2 改進設計

經典DE算法的性能很大程度上依賴于變異策略和相關參數值F和CR的選擇，不同的變異策略和參數選擇會導致不同的性能表現。

Fan等[9]提出了一種新的DE，它引入三角變異算子，以在算法收斂速度和魯棒性之間取得較好的平衡，從而提高DE的性能。Ali等[10]引入了輔助種群和放大因子F的自動計算。Sun等[11]提出了結合DE和分布估計的DE/EDA算法。Liu等[5]提出了一種模糊自適應DE(FADE)，它使用一個模糊邏輯控制器設置雜交與變異概率。Brest等[4]研究了具有自適應控制參數的DE(SADE)。SADE采用自適應控制機制調整參數F和CR。Qin等[6]提出了一種自適應DE(SaDE)，研究參數CR和變異策略的適應性。Yang等[12]引入了鄰域搜索策略DE(NSDE)，用服從高斯和柯西分布的隨機數生成參數F，而不是預定義常數F。基于SaDE和NSDE，Yang等[7]提出了另一個版本的DE(SaNSDE)，它吸收了SaDE和NSDE的優點。Rahnamayan等[3]提出了一種基于反向的DE(ODE)來提高算法收斂速度。它基于反向學習的模式，同時評估當前解和相反解，從而增加了找到更接近全局最優解的機會。ODE的實驗研究表明，它比經典DE更快更魯棒。

2.1 反向學習

反向學習(OBL)已被證明是一種行之有效的搜索方法。在求某個給定問題的解x時，我們初始考慮的x值，并不一定足夠精確，而是基于經驗或完全隨機的猜測。我們可以同時使用x的相反值來嘗試得到一個更好的解x*，這樣可以使下一代的x更快逼近最優解。相反解x*可以計算如下：

x*=a+b-x

(3)

式中：x∈R且在區間[a,b]上。

同樣，這個定義可以擴展到更高的維度，如:

(4)

OPij=aj(t)+bj(t)-Pij

(5)

式中：Pij是種群P中第i個個體的第j維向量，OPi是Pi的反向個體，aj(t)和bj(t)分別是當前搜索空間第j維的最小值和最大值，而t指進化代數。

2.2 自適應控制參數

如何選擇合適的控制參數值通常是一個與問題本身特征相關的任務。一般使用試錯模式以調整控制參數，但需要多次優化運行。Brest等[4]提出了一種新機制來調整控制參數F和CR。這種新的方法為每個Pi定義了Fi和CRi，每一代參數的自動調整機制如下:

(6)

(7)

式中：r1、r2、r3和r4是4個在[0,1]上的獨立隨機數；參數ε1和ε2分別代表了調整F和CR因子的概率。根據文獻[4]中的建議，將ε1和ε2設為0.1，Fl和Fu分別設為0.1和0.9。因此，新F以隨機方式從[0.1,1]中獲取一個值，新的CR從[0,1]中獲取一個值。

3 混合DE算法

本文提出了一種基于混合策略的差分進化算法HDE，它結合了反向學習和自適應控制參數機制。其中，反向學習可以減少計算時間開銷而自適應控制參數可以減少求解過程與問題自身的相關度。HDE的算法流程如下：

Begin

po=反向概率;

best_fitness_value_so_far=當前最優適應值;

VTR=到達值;

MAXNFC=函數最大調用次數(NFC);

while(best_fitness_value_so_far>VTR and NFC<=MAXNFC)

for i=1 to Np

根據式(6)和式(7)計算Fi和CRi;

從當前種群P選取任意三個個體Pi1,Pi2和Pi3,

其中i≠i1≠i2≠i3;

Vi=Pi1+Fi×(Pi2-Pi3);

for j=1 to D

if (rand(0,1)

Ui,j=Vi,j;

else

Ui,j=Pi,j;

for end

評估Ui適應度;

if (f(Ui)

else

for end

if(rand(0,1)

在當前種群中更新區間[aj(t),bj(t)]的邊界;

for i=1 to Np

根據式(5)計算Pi的反向個體OPi;

評估OPi適應度;

for end

在P和OP中選擇n個最適應個體作為下一代種群成員;

while end

End

4 基準函數測試

為了比較算法性能，在常用的全局優化問題中選擇了2個單峰函數(f1-f2)和3個多峰函數(f3-f5)來進行MATLAB環境下的仿真求解實驗。表1給出了所有基準測試函數、變量維數、定義域及其全局最優解。

表1 測試函數

4.1 ODE和HDE的比較

首先將ODE和HDE的優化性能進行比較。參考文獻[3]的測試方案，我們采用相同的參數設置和比較度量標準如下：

1) 種群規模NP=100；

2)F和CR自適應調整；

3) 反向概率po=0.3；

4) 變異策略為DE/rand/1/bin；

5) 最大NFC值MAXNFC=1e+6；

6) 最終到達值VTR=1e-8。

為了比較HDE和ODE的收斂速度，通過測量函數調用次數(NFC)來進行度量和比較，較小的NFC值意味著更快的收斂速度。運行終止標準是在達到最大調用次數前，算法找到一個小于到達值(VTR)的解。為了比較收斂的速度，我們使用基于NFC的加速率參數AR，定義如下：

(8)

當AR>1時，意味著HDE快于ODE。

再定義成功運行率SR如下：

(9)

其中較大的SR意味著該算法魯棒性更強。

圖1給出了5個測試函數調用求解的平均成功率SR和平均加速率AR的最終結果。從SR結果來看，ODE對f1、f2和f4的求解都取得了成功，但是對f3和f5求解的最終值未能全部達到要求的精度，而HDE對5個函數的求解取得100%成功率，這表明HDE的求解性能優于ODE，HDE比ODE更魯棒。加速率AR的值始終大于1，說明對5個函數進行求解時，HDE的收斂速度始終快于ODE。AR總平均值為1.176，意味著HDE比ODE收斂速度平均快17.6%。

圖1 ODE和HDE的比較結果

4.2 SADE、CEP、FEP和HDE的比較

我們再將常用的SADE、CEP、FEP和HDE進行比較研究，參數使用相同的設置。其中，最大調用次數值(MAXNFC)：1 500×100(代數×NP，f1、f3和f4)，2 000×100(f2和f5)。

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

表2 SADE、CEP、FEP和HDE的比較結果

顯然，在同等條件下，HDE和SADE在所有的測試用例實驗中,求解的最優值精度都優于CEP和FEP。其中，SADE對于f1和f2函數的求解值精度平均優于CEP和FEP多達1e+24倍和1e+20倍，而HDE又優于SADE 1e+1倍和1e+3倍。對f3和f5的求解中，HDE和SADE都取得了相同的全局最終最優解0。對f4的求解中，HDE和SADE求得的最優解值精度相同，但HDE的解比SADE的解更接近全局最終最優解。其中HDE對f1和f4求解時的收斂過程分別如圖2和圖3所示，可見其收斂過程也非常迅速，并未陷入局部最優。

圖2 HDE求解f1時的收斂過程

5 結 語

本文提出了一種混合了反向學習和自適應控制參數機制的新差分進化算法HDE。通過在5個著名的基準測試函數上進行性能測試比較實驗。結果表明，本文算法HDE在求解測試函數時的性能表現明顯優于ODE、SADE、CEP和FEP。今后的工作重點是進一步改進該算法，以使其具備更加廣泛的適用性。