范宇凌

（華僑大學(xué)工學(xué)院，泉州 362021）

0 引言

差分進(jìn)化算法（Differential Evolution，DE）是一種通過模擬種群進(jìn)化差異的啟發(fā)式隨機(jī)搜索算法[1]。Storn和Price最初設(shè)想是解決Chebyshev多項(xiàng)式問題，后來發(fā)現(xiàn)較之其他進(jìn)化算法，DE算法在解決復(fù)雜的全局優(yōu)化問題方面的性能更加突出，過程也更為簡單，受控參數(shù)少，適應(yīng)性強(qiáng)。目前在解決實(shí)際優(yōu)化問題方面得到了廣泛的應(yīng)用，例如過程模擬、工程設(shè)計(jì)優(yōu)化、經(jīng)濟(jì)和環(huán)境分配優(yōu)化等[2]。

此外，DE算法的性能高度依賴于變異策略和控制參數(shù)。例如，種群規(guī)模NP，放縮因子F和交叉常量CR。通常來說，DE算法解決不同的優(yōu)化問題所需的最合適的變異策略和控制參數(shù)是不同的。即使對于一個(gè)特定的優(yōu)化問題，在進(jìn)化過程中所需的最佳策略和控制參數(shù)可能會(huì)有所不同。特別是在解決各類優(yōu)化問題，使用傳統(tǒng)的反復(fù)實(shí)驗(yàn)法來確定最佳策略和參數(shù)雖是有效的，但是耗時(shí)。

為了解決上述問題，國內(nèi)外學(xué)者對標(biāo)準(zhǔn)差分進(jìn)化算法（DE）提出了眾多改進(jìn)，大致包含以下幾個(gè)方面：控制參數(shù)的自適應(yīng)，變異策略的改進(jìn)，多策略的使用以及從維持種群多樣性角度出發(fā)進(jìn)行的算法改進(jìn)。例如，jDE算法提出一種自適應(yīng)控制參數(shù)的差分進(jìn)化算法[3]；SaDE算法采用一種適應(yīng)性變異策略和參數(shù)[4]；王勇設(shè)計(jì)了一種多策略和參數(shù)組合的試驗(yàn)池的差分進(jìn)化算法[5]；JADE算法提出一種基于“current-to-pbest/1”變異策略和自適應(yīng)參數(shù)的差分進(jìn)化算[6]；DE-DPS算法提出一種動(dòng)態(tài)選擇最佳的參數(shù)組合的差分進(jìn)化算法[7]；CoBiDE算法引入了協(xié)方差矩陣學(xué)習(xí)和雙峰式分布參數(shù)調(diào)整對差分進(jìn)化算法進(jìn)行改進(jìn)[8]；EPSDE算法提出一種變異策略和參數(shù)集合的差分進(jìn)化算法[9]；MPEDE算法提出了一種基于多種群的方法來實(shí)現(xiàn)多策略和參數(shù)組合的差分進(jìn)化算法[10]，其將種群分成多個(gè)子種群，利用子種群與相應(yīng)的策略和參數(shù)集合相結(jié)合，來增強(qiáng)種群多樣性與改善種群單一策略帶來的不利影響，然而沒考慮到種群的是否出現(xiàn)停滯和早熟，以及收斂速度會(huì)降低的情況。

考慮到算法的整體優(yōu)化效果，為了進(jìn)一步提高算法的收斂性和魯棒性，以及子種群的停滯現(xiàn)象，本文結(jié)合種群進(jìn)化的進(jìn)程速度來實(shí)現(xiàn)策略加權(quán)，提出了一種增強(qiáng)全局搜索能力的差分進(jìn)化算法（MPWDE）。本文首先簡單介紹了標(biāo)準(zhǔn)差分進(jìn)化算法的原理和步驟，接下來詳細(xì)闡述了算法的改進(jìn)工作，包括種群變化，變異策略的改進(jìn)，構(gòu)造加權(quán)變異策略和動(dòng)態(tài)遞增參數(shù)，并在基準(zhǔn)測試函數(shù)上對MPWDE算法實(shí)現(xiàn)30和50維的仿真測試且與其他算法作了比較，最后對本文的工作進(jìn)行了總結(jié)。

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

1.1 初始化

設(shè)種群規(guī)模為NP，可行解空間的維數(shù)為D，用XG來表示進(jìn)化到G代時(shí)的種群，記為每一個(gè)個(gè)體是由D維參數(shù)構(gòu)成，可表示為：

其中分別表示上界和下界。

1.2 變異操作

變異操作是差分進(jìn)化算法中最重要的步驟，在這一階段，父代種群中的個(gè)體通過變異策略產(chǎn)生變異個(gè)體在DE中常用的差分策略為隨機(jī)選取種群中兩個(gè)不同個(gè)體將其向量縮放后與待變異個(gè)體進(jìn)行向量合成，即：

其中，F(xiàn)為縮放因子，其取值通常在[0,1]內(nèi)，控制偏差向量的放大作用；第一部分為隨機(jī)選取的待擾動(dòng)基向量，第二部分是對第一部分起擾動(dòng)作用的差分向量。

1.3 交叉操作

交叉操作的主要作用是生成的變異個(gè)體與原種群里面的個(gè)體進(jìn)行交叉操作，從而生成新的交叉?zhèn)€體。DE算法采用的是二項(xiàng)式交叉方案，交叉操作如下：

其中，randb是[0,1]間的隨機(jī)數(shù)；CR是范圍為[0,1]的常數(shù)，稱為交叉常量，CR的取值范圍越大，發(fā)生交叉的可能就越大，CR=0表示沒有交叉；randr(j)是在[1,D]隨機(jī)選擇整數(shù)。

1.4 選擇操作

選擇操作主要采用優(yōu)勝劣汰的貪婪選擇模式，使得子代個(gè)體總是優(yōu)于或等于父代個(gè)體，當(dāng)且僅當(dāng)新的向量個(gè)體ui的適度值要比目標(biāo)向量個(gè)體的適度值更好時(shí)，新的向量個(gè)體ui才會(huì)被種群接受。否則，xi仍保留在下一代種群中，并在下一次迭代計(jì)算中繼續(xù)作為目標(biāo)向量執(zhí)行變異及交叉操作，從而使種群始終向最優(yōu)解的方向進(jìn)化。選擇操作如下：

式中 f(X)為所要優(yōu)化的目標(biāo)函數(shù)。

2 一種增強(qiáng)全局搜索能力的差分進(jìn)化算法

2.1 種群多樣性

根據(jù)標(biāo)準(zhǔn)DE算法的原理，隨著迭代次數(shù)的增加，個(gè)體間的差異性逐漸減小，形成“聚集”現(xiàn)象，導(dǎo)致在搜索全局最優(yōu)時(shí)過早收斂，而使算法陷入局部最優(yōu)。本文引入了整體種群劃分子種群的思維，通過每一次迭代中子種群的進(jìn)化結(jié)果來劃分下一代子種群的個(gè)體數(shù)量，所以多種群方法更能保證種群的多樣性，避免種群的單一性促使算法早熟。

假設(shè)整體種群為Pop，Popi為Pop的子種群，NPi為Popi的種群規(guī)模，λi為子下種群規(guī)模比例，下面給出其定義：

其中，λi的取值范圍分布在[0,1]之間。

本文中多種群的規(guī)劃為：首先把整體種群分成三個(gè)子種群分別為 Pop1、Pop2、Pop3，Pop1種群規(guī)模比Pop2、Pop3種群規(guī)模大，每一子種群采用不同的變異策略，統(tǒng)計(jì)子種群經(jīng)過每一次種群進(jìn)化后edp_num1、edp_num2和edp_num3（保留下優(yōu)良個(gè)體維數(shù)的總和），根據(jù)種群個(gè)體的維數(shù)D,可得出子種群優(yōu)良率rate1、rate2和rate3。將三個(gè)子種群的種群優(yōu)良率進(jìn)行比較得出優(yōu)良率高的策略，下一次進(jìn)化過程中分配的種群規(guī)模為NP1。

2.2 加權(quán)變異策略

變異策略是DE算法的核心，根據(jù)變異機(jī)制的不同，產(chǎn)生多種策略。為區(qū)分不同的DE變異策略，一般表示為DE/X/Y/Z，其中DE代表差分進(jìn)化算法；X表示待擾動(dòng)的基向量，它既可以是當(dāng)前種群中的隨機(jī)向量（rand），也可以是當(dāng)前種群的最優(yōu)向量（best）；Y 表示差分向量個(gè)數(shù)；Z指代所采取的交叉模式。本文通過三個(gè)子種群在進(jìn)化過程中采樣不同的變異策略來保證種群個(gè)體的多樣性。從以往改進(jìn)過的DE經(jīng)典算法中學(xué)習(xí)，選出三個(gè)使用較為廣泛的策略：

（1）“DE/current-to-best/1”

式（2）中所有參與變異的向量均以隨機(jī)的方式被選擇，因此能夠在全局進(jìn)行尋優(yōu)，但是由于缺少最優(yōu)解信息，使得式（2）收斂速度較慢。式（3）、（4）通過當(dāng)前最優(yōu)解來尋求全局最優(yōu)解，在進(jìn)化過程雖然能將搜索范圍縮小至最優(yōu)解附近加快算法的收斂速度，但種群多樣性缺失，不能找到最優(yōu)解。為減小式（4）前期搜索范圍狹小，后期收斂速度慢的影響，對式（4）變異策略進(jìn)行修改，建立加權(quán)變異策略機(jī)制。對種群的每一個(gè)體建立兩種變異：局部變異和全局變異，改進(jìn)后的變異策略如下：

局部變異：

其中，表示Pop1種群中的最佳個(gè)體，XGbest表示Pop種群中的最佳個(gè)體，r1、r2∈(1,NP1)。

結(jié)合這兩種變異模式，采用隨機(jī)變化的變量w∈(0,1)作為權(quán)重對局部和全局變異成分進(jìn)行加權(quán)平均形成新的變異策略，設(shè)t為當(dāng)前函數(shù)評估次數(shù)，F(xiàn)ES函數(shù)最大評估次數(shù)，可表示為：

其中，wmin、wmax為權(quán)重因子w上下界，且wmin、wmax∈[0,1]。算法開始時(shí)，t=0，w=wmin，隨著當(dāng)前評估次數(shù)的增大，w逐漸增大，最終當(dāng)t=FES達(dá)到最大wmax。算法開始以局部搜索模式為主，然后過渡到全局模式。顯然為了達(dá)到局部變異和全局變異的平衡，合理選擇適當(dāng)?shù)膚min和wmax是非常必要的。本文中wmin=0、wmax=1。

2.3 算法步驟

（1）初始化種種群：根據(jù)公式（5）將種群分成三個(gè)子種群 Pop1、Pop2、Pop3，gen=0，設(shè)置 wmin、wmax的值，迭代次數(shù)置為0。

（2）計(jì)算當(dāng)前種群適度值 f。

（3）根據(jù)公式（6）、（7）、（11）進(jìn)行變異操作。

（4）進(jìn)行交叉選擇操作。

（5）計(jì)算優(yōu)良率rate1、rate2和rate3。

（6）判斷迭代次數(shù)是否到達(dá)最大值，到達(dá)繼續(xù)執(zhí)行步驟（7），反之則重新分配子種群并返回步驟（2）進(jìn)行循環(huán)迭代。

（7）輸出適應(yīng)度值最優(yōu)的個(gè)體。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)設(shè)置

為了驗(yàn)證本文提出的MPWDE算法的性能，采用基準(zhǔn)測試函數(shù)中5個(gè)測試函數(shù)，對該算法進(jìn)行測試。將MPWDE與其他5個(gè)經(jīng)典的DE算法對比，包括jDE、JADE、SaDE、EPSDE、MPEDE。選擇上面幾個(gè) DE算法的原因如下：第一，文獻(xiàn)[3，6]中的JADE和jDE常被引用作為基準(zhǔn)算法；第二，文獻(xiàn)[4，9]中SaDE和EPS?DE包含著幾個(gè)類似的策略；第三，文獻(xiàn)[10]中的MPEDE是目前效果最好的DE算法。這些算法的所有變異策略和控制參數(shù)的設(shè)置都與原始參考文獻(xiàn)中所給出的變異策略和控制參數(shù)相同。為了提供一個(gè)更全面的比較，本文設(shè)置種群規(guī)模NP=250，分別對30維和50維的情況進(jìn)行實(shí)驗(yàn)，且每個(gè)算法對每個(gè)測試函數(shù)獨(dú)立運(yùn)行25次，F(xiàn)ES分別設(shè)置為300000和500000。實(shí)驗(yàn)環(huán)境：操作系統(tǒng)：Win7專業(yè)版64位，CPU：Intel Core i7（3.40GHz），RAM：8GB，語言：MATLAB ，編譯器：MAT?LAB R2014b。

3.2 算法有效性分析

以下是可行解為30維和50維的實(shí)驗(yàn)結(jié)果，如表1和表2所示，表中提供了實(shí)驗(yàn)結(jié)果的平均誤差和標(biāo)準(zhǔn)偏差（在括號中）。標(biāo)記“+”、“-”和“≈”表示比較算法性能明顯好于、明顯差于和近似于MPWDE。

由表1可知，對于測試函數(shù)F1-F5，雖然JADE和MPEDE算法實(shí)驗(yàn)效果表現(xiàn)較好，但是MPWDE的實(shí)驗(yàn)效果更佳，結(jié)果差別更加顯著；在測試函數(shù)F3、F4和F5上，MPWDE的實(shí)驗(yàn)結(jié)果明顯優(yōu)于JADE和MPEDE算法；在測試函數(shù)F1和F2上，MPWDE與對比算法是可比較的。

表1 可行解為30維的標(biāo)準(zhǔn)測試函數(shù)計(jì)算結(jié)果

表2 可行解為50維的標(biāo)準(zhǔn)測試函數(shù)計(jì)算結(jié)果

由表2可知，對于測試函數(shù)F1-F5，F(xiàn)0函數(shù)的實(shí)驗(yàn)效果相近，雖然JADE和MPEDE算法實(shí)驗(yàn)效果在F2和F3表現(xiàn)較好且MPWDE的實(shí)驗(yàn)效果稍遜點(diǎn)，但是MPWDE在F4和F5的實(shí)驗(yàn)效果要優(yōu)于所有對比算法。

通過進(jìn)化曲線評價(jià)算法性能，分析表1、表2的數(shù)據(jù)。進(jìn)化曲線以平均適應(yīng)度誤差值（Average Function Value）為縱軸，評估次數(shù)FES為橫軸，具體分析如圖1-圖6所示。

通過五種經(jīng)典DE算法和MPWDE進(jìn)行對比表明，MPWDE的不管在收斂速度還是在收斂性能方面都具有很強(qiáng)的優(yōu)越性。圖1測試函數(shù)F2，jDE和SaDE策略單一導(dǎo)致種群變異差異較小且出現(xiàn)早熟，ESPDE、JADE和MPEDE均未出現(xiàn)收斂趨勢，但是求解精度不及 MPWDE。圖 4測試函數(shù) F5，jDE、SaDE和 ESPDE均出現(xiàn)早熟，而JADE和MPEDE雖然在迭代中也有機(jī)會(huì)尋找全局最優(yōu)解，但是精度不高且收斂速度遠(yuǎn)比不上MPWDE。從圖5和圖6，MPWDE算法進(jìn)化前期在進(jìn)行全局搜索收斂速度緩慢，后面逐步過渡局部搜索從而提高求解精度。不僅如此，從圖2、圖3和圖4測試函數(shù)可以明顯看出MPWDE的收斂速度和求解精度都是最優(yōu)的。種群多樣性可以從圖1至圖6看出，當(dāng)種群失去多樣性的時(shí)候，算法就會(huì)出現(xiàn)早熟，雖然種群多樣性和收斂速度是矛盾的，但是本文算法不僅控制種群的多樣性，還應(yīng)用了加權(quán)策略使搜索從全局到局部，因而算法在求解精度、收斂速度方面都優(yōu)于另外五種算法。

4 結(jié)語

實(shí)際優(yōu)化問題往往具有未知性、復(fù)雜性、高維等特性，標(biāo)準(zhǔn)差分進(jìn)化算法過程較為簡單、受控參數(shù)少、策略單一，無法不斷地提高自身對外界環(huán)境的適應(yīng)程度，逐步逼近問題的最優(yōu)解。本文從種群多樣性的理論角度出發(fā)，提出了一種增強(qiáng)全局搜索能力的差分進(jìn)化算法，通過多種群機(jī)制有效改善了種群多樣性，引入權(quán)重因子疊加雙變異策略使改進(jìn)后的算法逐步從全局搜索過渡到局部搜索。通過交叉因子動(dòng)態(tài)遞增的調(diào)整策略，避免了復(fù)雜的參數(shù)反饋過程，提高了算法收斂速度，改善了DE算法在收斂速度和搜索魯棒性之間存在的矛盾，通過基準(zhǔn)測試函數(shù)的仿真結(jié)果并與其他算法比較，表明MPWDE有較強(qiáng)的全局搜索能力，能有效避免早熟收斂，在算法的運(yùn)行速度和求解精度方面都有了進(jìn)一步的提高。

圖1 30維F2函數(shù)平均適應(yīng)度誤差曲線

圖2 30維F3函數(shù)平均適應(yīng)度誤差曲線

圖3 30維F4函數(shù)平均適應(yīng)度 誤差曲線

圖4 30維F5函數(shù)平均適應(yīng)度誤差曲線

圖5 50維F4函數(shù)平均適應(yīng)度 誤差曲線

圖6 50維F5函數(shù)平均適應(yīng)度 誤差曲線

[1]Storn R,Price K.Differential Evolution—A Simple and Efficient Heuristic for Global Optimization Over Continuous Spaces[J].Journal of Global Optimization,1997,11（4）:341-359.

[2]劉波,王凌,金以慧,等.差分進(jìn)化算法研究進(jìn)展[J].控制與決策,2007,22（7）:721-729.

[3]Breast,J.,Greiner,S.,Boskovoic,B.,Mernik,M.,Zumer,V..Self-Adapting Control Parameters in Differential Evolution:A Comparative Study on Numerical Benchmark Problem[J].IEEE Transactions on Evolutionary Computation,2006,10（6）:646-657.

[4]Qin,A.K.,Huang,V.L.,Suganthan,P.N..Differential Evolution Algorithm With Strategy Adaptation for Global Numerical Optimization[J].IEEE Transactions on Evolutionary Computation,2009,13（2）:398-417.

[5]Wang,Y.,Cai,Z.,Zhang,Q..Differential Evolution with Composite Trial Vector Generation Strategies and Control Parameters[J].IEEE Transactions on Evolutionary Computation,2011,15（1）:55-66.

[6]Zhang,J.,A.C.,S..JADE:Adaptive Differential Evolution With Optional External Archive[J],IEEE Transactions on Evolutionary Computation,2009,13（5）:945-967.

[7]Sarker,R.A.,Elsayed,S.M.,Ray,T.,Differential Evolution With Dynamic Parameters Selection for Optimization Problems[J].IEEE Transactions on Evolutionary Computation,2014,18（5）:689-707.

[8]Wang,Y.,Li,H-X.,Huang,T.,Li,L.,Different Evolution Based on Covariance Matrix Learning and Bimodal Distribution Parameter Setting[J].Applied Soft Computing,2014,18（1）:232-247.

[9]Mallipeddi,R.,Suganthan,P.N.,Pan,Q.-K.,Tasgetiren,M.F..Differential Evolution Algorithm with Ensemble of Parameters and Mutation strategies[J].Applied Soft Computing,2011,11（2）:1679-1696.

[10]G.H.Wu,R.Mallipeddi,P.N.Suganthan,R.M.Duwairi,R.G.Reynolds,Differential Evolution with Multi-Population Based Ensemble of Mutation Strategies[J].Information Sciences,2016,10（C）:329-345.