苗曉鋒 劉志偉

1(榆林職業(yè)技術(shù)學(xué)院神木校區(qū)信息中心 陜西 神木 719300)2(西北工業(yè)大學(xué)信息中心 陜西 西安 710072)

0 引 言

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

本文提出了一種基于混合策略的差分進(jìn)化算法HDE，即結(jié)合反向?qū)W習(xí)機(jī)制和自適應(yīng)控制參數(shù)的DE。通過(guò)求解兩個(gè)單峰函數(shù)和三個(gè)多峰函數(shù)所進(jìn)行的測(cè)試實(shí)驗(yàn)，將HDE與已有的ODE[3]、SADE[4]、CEP[8]和FEP[8]算法進(jìn)行了性能比較。

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

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

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

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

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

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

(1)

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

雜交操作：如同其他遺傳算法一樣，DE也利用雜交算子結(jié)合兩個(gè)不同的解來(lái)生成試驗(yàn)解，該試驗(yàn)解定義如下：

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

式中：j=1,2,…,D(D是問(wèn)題維數(shù))，

(2)

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

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

2 改進(jìn)設(shè)計(jì)

經(jīng)典DE算法的性能很大程度上依賴(lài)于變異策略和相關(guān)參數(shù)值F和CR的選擇，不同的變異策略和參數(shù)選擇會(huì)導(dǎo)致不同的性能表現(xiàn)。

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

2.1 反向?qū)W習(xí)

反向?qū)W習(xí)(OBL)已被證明是一種行之有效的搜索方法。在求某個(gè)給定問(wèn)題的解x時(shí)，我們初始考慮的x值，并不一定足夠精確，而是基于經(jīng)驗(yàn)或完全隨機(jī)的猜測(cè)。我們可以同時(shí)使用x的相反值來(lái)嘗試得到一個(gè)更好的解x*，這樣可以使下一代的x更快逼近最優(yōu)解。相反解x*可以計(jì)算如下：

x*=a+b-x

(3)

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

同樣，這個(gè)定義可以擴(kuò)展到更高的維度，如:

(4)

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

(5)

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

2.2 自適應(yīng)控制參數(shù)

如何選擇合適的控制參數(shù)值通常是一個(gè)與問(wèn)題本身特征相關(guān)的任務(wù)。一般使用試錯(cuò)模式以調(diào)整控制參數(shù)，但需要多次優(yōu)化運(yùn)行。Brest等[4]提出了一種新機(jī)制來(lái)調(diào)整控制參數(shù)F和CR。這種新的方法為每個(gè)Pi定義了Fi和CRi，每一代參數(shù)的自動(dòng)調(diào)整機(jī)制如下:

(6)

(7)

式中：r1、r2、r3和r4是4個(gè)在[0,1]上的獨(dú)立隨機(jī)數(shù)；參數(shù)ε1和ε2分別代表了調(diào)整F和CR因子的概率。根據(jù)文獻(xiàn)[4]中的建議，將ε1和ε2設(shè)為0.1，F(xiàn)l和Fu分別設(shè)為0.1和0.9。因此，新F以隨機(jī)方式從[0.1,1]中獲取一個(gè)值，新的CR從[0,1]中獲取一個(gè)值。

3 混合DE算法

本文提出了一種基于混合策略的差分進(jìn)化算法HDE，它結(jié)合了反向?qū)W習(xí)和自適應(yīng)控制參數(shù)機(jī)制。其中，反向?qū)W習(xí)可以減少計(jì)算時(shí)間開(kāi)銷(xiāo)而自適應(yīng)控制參數(shù)可以減少求解過(guò)程與問(wèn)題自身的相關(guān)度。HDE的算法流程如下：

Begin

po=反向概率;

best_fitness_value_so_far=當(dāng)前最優(yōu)適應(yīng)值;

VTR=到達(dá)值;

MAXNFC=函數(shù)最大調(diào)用次數(shù)(NFC);

while(best_fitness_value_so_far>VTR and NFC<=MAXNFC)

for i=1 to Np

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

從當(dāng)前種群P選取任意三個(gè)個(gè)體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

評(píng)估Ui適應(yīng)度;

if (f(Ui)

else

for end

if(rand(0,1)

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

for i=1 to Np

根據(jù)式(5)計(jì)算Pi的反向個(gè)體OPi;

評(píng)估OPi適應(yīng)度;

for end

在P和OP中選擇n個(gè)最適應(yīng)個(gè)體作為下一代種群成員;

while end

End

4 基準(zhǔn)函數(shù)測(cè)試

為了比較算法性能，在常用的全局優(yōu)化問(wèn)題中選擇了2個(gè)單峰函數(shù)(f1-f2)和3個(gè)多峰函數(shù)(f3-f5)來(lái)進(jìn)行MATLAB環(huán)境下的仿真求解實(shí)驗(yàn)。表1給出了所有基準(zhǔn)測(cè)試函數(shù)、變量維數(shù)、定義域及其全局最優(yōu)解。

表1 測(cè)試函數(shù)

4.1 ODE和HDE的比較

首先將ODE和HDE的優(yōu)化性能進(jìn)行比較。參考文獻(xiàn)[3]的測(cè)試方案，我們采用相同的參數(shù)設(shè)置和比較度量標(biāo)準(zhǔn)如下：

1) 種群規(guī)模NP=100；

2)F和CR自適應(yīng)調(diào)整；

3) 反向概率po=0.3；

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

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

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

為了比較HDE和ODE的收斂速度，通過(guò)測(cè)量函數(shù)調(diào)用次數(shù)(NFC)來(lái)進(jìn)行度量和比較，較小的NFC值意味著更快的收斂速度。運(yùn)行終止標(biāo)準(zhǔn)是在達(dá)到最大調(diào)用次數(shù)前，算法找到一個(gè)小于到達(dá)值(VTR)的解。為了比較收斂的速度，我們使用基于NFC的加速率參數(shù)AR，定義如下：

(8)

當(dāng)AR>1時(shí)，意味著HDE快于ODE。

再定義成功運(yùn)行率SR如下：

(9)

其中較大的SR意味著該算法魯棒性更強(qiáng)。

圖1給出了5個(gè)測(cè)試函數(shù)調(diào)用求解的平均成功率SR和平均加速率AR的最終結(jié)果。從SR結(jié)果來(lái)看，ODE對(duì)f1、f2和f4的求解都取得了成功，但是對(duì)f3和f5求解的最終值未能全部達(dá)到要求的精度，而HDE對(duì)5個(gè)函數(shù)的求解取得100%成功率，這表明HDE的求解性能優(yōu)于ODE，HDE比ODE更魯棒。加速率AR的值始終大于1，說(shuō)明對(duì)5個(gè)函數(shù)進(jìn)行求解時(shí)，HDE的收斂速度始終快于ODE。AR總平均值為1.176，意味著HDE比ODE收斂速度平均快17.6%。

圖1 ODE和HDE的比較結(jié)果

4.2 SADE、CEP、FEP和HDE的比較

我們?cè)賹⒊Ｓ玫腟ADE、CEP、FEP和HDE進(jìn)行比較研究，參數(shù)使用相同的設(shè)置。其中，最大調(diào)用次數(shù)值(MAXNFC)：1 500×100(代數(shù)×NP，f1、f3和f4)，2 000×100(f2和f5)。

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

表2 SADE、CEP、FEP和HDE的比較結(jié)果

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

圖2 HDE求解f1時(shí)的收斂過(guò)程

5 結(jié) 語(yǔ)

本文提出了一種混合了反向?qū)W習(xí)和自適應(yīng)控制參數(shù)機(jī)制的新差分進(jìn)化算法HDE。通過(guò)在5個(gè)著名的基準(zhǔn)測(cè)試函數(shù)上進(jìn)行性能測(cè)試比較實(shí)驗(yàn)。結(jié)果表明，本文算法HDE在求解測(cè)試函數(shù)時(shí)的性能表現(xiàn)明顯優(yōu)于ODE、SADE、CEP和FEP。今后的工作重點(diǎn)是進(jìn)一步改進(jìn)該算法，以使其具備更加廣泛的適用性。