差分進化算法的研究進展

李 斌

（河南建筑職業(yè)技術(shù)學(xué)院，河南 鄭州 450064）

差分進化算法的研究進展

李 斌

（河南建筑職業(yè)技術(shù)學(xué)院，河南 鄭州 450064）

差分進化算法是一類當(dāng)前較為強大的隨機實參數(shù)優(yōu)化算法，已成功解決很多實際問題。它具有全局優(yōu)化性能好、結(jié)構(gòu)簡單易于實現(xiàn)、控制參數(shù)少和搜索能力強等優(yōu)點，差分進化算法吸引了眾多進化算法研究者的關(guān)注。文中詳細(xì)概述了差分進化算法的基本概念、特點、改進和應(yīng)用現(xiàn)狀，就DE算法的進一步研究進行了探討和展望。

差分進化；進化算法；遺傳算法

1 引言

根據(jù)達爾文的生物進化理論，自然界的物種會隨著客觀環(huán)境的變化而發(fā)生變異，各個物種在競爭環(huán)境中生存，優(yōu)勝劣汰，使得生物不斷進化。為了求解復(fù)雜優(yōu)化問題，一些研究人員嘗試借鑒自然界物種進化的思想來開展優(yōu)化算法研究，從而開啟了一個重要研究方向——進化計算（Evolutionary Computation，簡稱EC）。進化計算具有穩(wěn)健性、易實現(xiàn)性和全局搜索能力強等特點，同時不依賴待求問題的種類和性質(zhì)，因此在眾多領(lǐng)域倍受關(guān)注。

類似于其他的進化計算算法，差分進化（Differential Evolution，簡稱DE）算法也是一種基于種群的全局隨機搜索算法[1]，它最初是由Storn和Price為求解切比雪夫多項式擬合問題于1995年提出的。1996年5月在日本舉行的第一屆國際進化優(yōu)化方法競賽（International Contest on Evolutionary Optimization， ICEO）中，DE算法表現(xiàn)突出，獲得了第三名的成績。1997年的第二屆國際進化優(yōu)化方法競賽中Price通過大量優(yōu)化實驗證明了DE是一種性能優(yōu)異的進化算法。從此，DE算法得到更多研究者的關(guān)注。自2005年以來，在IEEE Conference on Evolution Computation（CEC）會議關(guān)于實參優(yōu)化、多目標(biāo)優(yōu)化、動態(tài)不確定性優(yōu)化等多次競賽中，DE具有非常優(yōu)異的表現(xiàn)。

DE算法是一種基于種群的智能優(yōu)化方法，不依賴問題的特征信息，主要借助于種群個體之間的差分信息對個體形成擾動來探索整個種群空間，并利用貪婪競爭機制進行優(yōu)化，尋求問題最優(yōu)解。DE算法采用實數(shù)編碼，首先在搜索空間內(nèi)隨機產(chǎn)生初始群體，使用變異操作、交叉操作生成新的個體，但與一般的進化算法不同的是，差分進化算法采用一對一的淘汰機制來更新進化群體，降低了進化操作的復(fù)雜性。不同的是差分進化算法把一定比例的多個個體的差分信息作為個體的擾動量，使得算法在跳躍距離和搜索方向上具有自適應(yīng)性[2]。在進化的早期，因為種群中個體的差異性較大使得擾動量較大，從而使得算法能夠在較大范圍內(nèi)搜索，具有較強的探索能力（exploration）；而到了進化的后期，當(dāng)算法趨向于收斂時，種群中個體的差異性較小，算法在個體附近搜索，這使得算法具有較強的局部開采能力（exploitation）[2]。

鑒于差分進化算法具有控制參數(shù)少、原理相對簡單、易于理解和實現(xiàn)的優(yōu)點，再加上其表現(xiàn)出來的高可靠性、強魯棒性以及良好的優(yōu)化性能，目前已經(jīng)成為進化計算研究領(lǐng)域的熱點。它廣泛應(yīng)用于很多領(lǐng)域，如控制系統(tǒng)與機器人、化學(xué)工程、模式識別與圖像處理、人工神經(jīng)網(wǎng)絡(luò)、生物信息學(xué)和信號處理等取得了驚人的效果。

2 差分進化算法基本原理

DE的基本思想是：利用從種群中隨機選擇的兩個個體向量的差分量作為第三個隨機基準(zhǔn)向量的擾動量，得到變異向量，然后變異向量與基準(zhǔn)向量（或稱為目標(biāo)向量）進行交叉操作，生成試驗向量。最后基準(zhǔn)向量和試驗向量競爭，較優(yōu)者保存在下一代群體中。這樣，差分進化算法逐代改善群體質(zhì)量，引導(dǎo)種群聚焦到最優(yōu)解位置。

圖1給出了差分進化算法的主要步驟，包括種群初始化，以及選擇多個個體進行變異操作產(chǎn)生變異個體，變異個體與目標(biāo)個體進行交叉操作，目標(biāo)個體與試驗個體競爭選擇操作等。從圖1中我們可以看出，DE算法執(zhí)行簡單，易于實現(xiàn)。

圖1 DE算法的主要步驟

2.1 初始化

個體每一維上的取值可按下式產(chǎn)生：

2.2 變異

在DE算法中，種群內(nèi)個體的差分向量經(jīng)過縮放之后，與種群內(nèi)另外的相異個體相加得到變異向量。根據(jù)變異向量生成方法不同，形成了多種變異策略[3]。目前被廣泛采用的五種變異策略如下[1]：

2.3 交叉

變異操作完成后，對目標(biāo)向量和變異向量進行交叉操作生成試驗向量，DE算法有兩種交叉方式：二項式交叉（用bin表示）和指數(shù)交叉（用exp表示）。以二項式交叉具體說明如下：

通過隨機選擇，使試驗向量至少有一個分量由變異向量貢獻。二項式交叉操作的方程為：

2.4 選擇

3 差分進化算法的改進

在各種應(yīng)用領(lǐng)域和多次進化大賽中，差分進化算法已經(jīng)展現(xiàn)出驚人的魅力。然而，DE算法不可避免地存在搜索停滯和早熟收斂、搜索性能對參數(shù)具有依賴性、算法在有限情況下很難保證獲得全局最優(yōu)解等問題，因此從多方面深入分析算法的運行機理，并提出相應(yīng)的改進DE算法性能的調(diào)整策略，從而達到平衡算法的探索能力與開發(fā)能力的目的，依然是當(dāng)前進化算法研究的重要領(lǐng)域。

3.1 控制參數(shù)調(diào)整策略的改進

DE算法的控制參數(shù)包括縮放因子F、交叉率CR以及種群規(guī)模NP。DE算法性能的優(yōu)劣很大程度上取決于其控制參數(shù)的選擇[4]。

1）種群規(guī)模NP：如果種群規(guī)模NP較小，算法可能收斂快，但是會導(dǎo)致算法早熟；相反，NP過大，可以增加種群的多樣性，增加搜索到最優(yōu)解的概率，但會導(dǎo)致計算量加大，收斂速度較慢。

2）縮放因子F：縮放因子影響對基向量的擾動程度，F(xiàn)較大時，擾動較大導(dǎo)致搜索步長的取值在一個更大的范圍內(nèi)，能夠在更大范圍內(nèi)尋求有潛力的解，從而提高種群的多樣性，但是削弱了算法的局部搜索能力；F較小，擾動量小，搜索范圍較小，有利于進化的快速進行，提高算法的收斂速度。

3）交叉率CR：交叉率對種群的多樣性具有重要的影響，決定種群中有多少個體可能被改變。CR較小時，種群中被改變的個體較少，當(dāng)前種群中解的特征被較多地保留下來，有利于進化過程的穩(wěn)定進行；CR較大時，會引起種群中更多個體發(fā)生改變，使種群多樣性增強，有利于搜索到最優(yōu)解。

Liu和Lampinen提出了一種基于模糊控制的適應(yīng)差分進化算法FADE，通過模糊邏輯控制器來調(diào)節(jié)參數(shù)F和CR，仿真結(jié)果顯示該算法在優(yōu)化高維問題時的性能遠遠優(yōu)于傳統(tǒng)DE算法[5]。

Qin等提出一種新的自適應(yīng)差分進化（SaDE）算法，F(xiàn)和CR借鑒前期產(chǎn)生優(yōu)質(zhì)解的經(jīng)驗進行自適應(yīng)調(diào)整[6]。該算法中F的設(shè)置服從均值為0.5、標(biāo)準(zhǔn)方差為0.3的正態(tài)分布N（0.5，0.32），并應(yīng)用于當(dāng)前種群的每一差分向量，從而平衡整個優(yōu)化過程的探索（F較大時）與開發(fā)（F較?。┠芰ΑR的值服從均值為CRm，標(biāo)準(zhǔn)方差為Std的正態(tài)分布N（CRm， Std2）。將CRm初始化為0.5，此時Std應(yīng)設(shè)置為一個很小的值保證CR的取值為[0，1]，因此將Std設(shè)置為0.1。SaDE算法中的自適應(yīng)機制中也涉及參數(shù)的調(diào)節(jié)，如正態(tài)分布的標(biāo)準(zhǔn)方差。算法中對問題不太敏感的參數(shù)代替敏感度較高的參數(shù)，因此自適應(yīng)DE算法能夠獲得比傳統(tǒng)DE算法更好的性能。

Zhang和Sanderson[7]提出一種新的適應(yīng)差分進化算法（JADE）。在JADE算法中，對每個個體，分別應(yīng)用標(biāo)準(zhǔn)正態(tài)分布和柯西分布采樣確定交叉概率CR和縮放因子F。

3.2 操作算子策略的改進

除基本DE所介紹的5個變異策略外，研究人員對其他一些變異策略進行了研究。

Fan和Lampinen提出三角變異策略[8]：

該算法利用隨機選擇的三個個體中最好個體信息，引導(dǎo)試驗向量向其靠近，該方法可視為一種局部搜索策略。為了進一步在收斂速度和搜索能力之間尋求一種平衡，算法使用一個概率來控制三角變異算子的使用頻率。

Zhang和Sanderson提出DE/current-to-pbest策略[7]，即JADE：

Liang等[9]提出利用適應(yīng)度歐式距離比值改進算法的性能，用于優(yōu)化多模函數(shù)問題。

3.3 混合差分進化算法

混合技術(shù)是指將兩個或多個算法的優(yōu)點結(jié)合在一起，在特定問題求解范圍內(nèi)，形成一種新的算法，近年來正成為優(yōu)化算法的研究熱點。研究者對DE與其他算法相混合的技術(shù)進行了大量的研究，包括與其他智能優(yōu)化算法以及局部搜索方法的融合。

與D E相混合的智能優(yōu)化算法有粒子群優(yōu)化（PSO）、蟻群算法（ACO）、人工免疫算法（AIS）、模擬退火（SA）等。其中，DE與PSO混合的研究最多，Hendtlass首次將DE與PSO進行融合，提出當(dāng)后代獲得較好的適應(yīng)值時更新粒子的位置，DE算法在指定的間隔對粒子群進行作用。Xin等對PSO與DE相混合進行了詳盡的分析和總結(jié)[10]。Capanio等在DE框架中將PSO和另外兩種局部搜索算法相結(jié)合，利用PSO在初始階段快速改善具有較差適值的解，并將其包含在DE種群中，使這些解引導(dǎo)DE搜索，兩種搜索方式按一定概率與DE算法相結(jié)合[11]。文獻[12]提出基于一種新的混合差分粒子群啟發(fā)式優(yōu)化算法的電子商務(wù)物流配送優(yōu)化方案。

4 總結(jié)與展望

DE算法的提出最初是為了解決連續(xù)領(lǐng)域的優(yōu)化問題，作為智能優(yōu)化技術(shù)的一個重要的分子，DE算法已經(jīng)引起優(yōu)化計算領(lǐng)域研究人員的普遍關(guān)注。目前DE算法已經(jīng)廣泛地應(yīng)用于許多領(lǐng)域，在算法改進和應(yīng)用上得到了快速的發(fā)展，成為進化計算領(lǐng)域新的研究熱點。但DE算法在其理論分析，算法改進和應(yīng)用研究等方面仍有廣闊的值得挖掘的研究空間，需要加強并進行深入研究。加強理論方面的研究，為其改進和實際應(yīng)用提供依據(jù)，這非常具有挑戰(zhàn)性和吸引力，在這方面還需要做大量的研究。DE算法的改進研究，它包括對其控制參數(shù)（種群規(guī)模NP、縮放因子F和交叉率CR）的研究，算子（差分變異、交叉率和選擇）以及種群拓?fù)浣Y(jié)構(gòu)等的研究，從平衡算法的探索與開發(fā)能力的角度出發(fā)，考慮種群多樣性以及個體適應(yīng)值在算法運行過程中的變化情況，引入適應(yīng)性調(diào)節(jié)機制，提出高效穩(wěn)健的協(xié)調(diào)方法，仍是DE算法的重要研究內(nèi)容。

[1]Price K，Storn R，Lampinen J.Differential Evolution：A Practical Approach to Global Optimization [M].New York： Springer-Verlag， 2005.

[2]吳志峰.差異演化算法及其應(yīng)用研究[D].北京：北京交通大學(xué)，2009.

[3]張航，王偉，鄭玲等.一種基于密度聚類的小生境差分進化算法[J].計算機工程與應(yīng)用，2008，44（23）：42-45.

[4]Mandal K K， Chakraborty N.Parameter study of differential evolution based optimal scheduling of hydrothermal systems [J].Journal of Hydroenvironment Research，2012，7（1）：72-80.

[5]Liu J， LampinenJ.A fuzzy adaptive differential evolution algorithm[J].Soft Computing，2005，9（6）：448-462.

[6]Qin.K，Huang VL，Suganthan P N.Differential evolution algorithm with strategy adaptation for global numerical optimization [J].IEEE Transactions on Evolutionary Computation， 2009，13（2）：398-417.

[7]Zhang J Q， Sanderson A C.JADE：adaptive differential evolution with optional external archive[J].IEEE Transactions on Evolutionary Computation，2009，13（5）：945-958.

[8]H.Y.Fan and J.Lampinen.A trigonometric mutation operation to differential evolution[J].Journal of Global Optimization，2003，27（1）：l05-129.

[9]Liang J J，Qu B Y，Mao X B，et al.Differential evolution based on fitness Euclidean-distance ratio for multimodal optimization[J].Neurocomputing，2014，137（5）：252-260.

[10]Xin B，Chen J，Zhang J，et al.Hybridizing differential evolution and particle swarm optimization to design powerful optimizers： A review and taxonomy[J].IEEE Transactions on systems， Man & Cybernetics Part C，2012， 42（5）：744-767.

[11]Caponio A，Neri F，Tirronen V.Super-fit control adaptation in memetic differential evolution frameworks[J].Soft Computing，2009，13（8）：811-831.

[12]沈濟南，梁芳，鄭明輝.一種新的混合差分粒子群優(yōu)化算法及其應(yīng)用[J].四川大學(xué)學(xué)報（工程科學(xué)版），2014.46（6）：38-43.

李斌（1974—），男（回族），河南建筑職業(yè)技術(shù)學(xué)院，高級講師，電氣、物理方向

2017-08-23