差分進化算法的研究進展

李 斌

（河南建筑職業技術學院，河南 鄭州 450064）

差分進化算法的研究進展

李 斌

（河南建筑職業技術學院，河南 鄭州 450064）

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

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

1 引言

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

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

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

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

2 差分進化算法基本原理

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

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

圖1 DE算法的主要步驟

2.1 初始化

個體每一維上的取值可按下式產生：

2.2 變異

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

2.3 交叉

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

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

2.4 選擇

3 差分進化算法的改進

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

3.1 控制參數調整策略的改進

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

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

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

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

Liu和Lampinen提出了一種基于模糊控制的適應差分進化算法FADE，通過模糊邏輯控制器來調節參數F和CR，仿真結果顯示該算法在優化高維問題時的性能遠遠優于傳統DE算法[5]。

Qin等提出一種新的自適應差分進化（SaDE）算法，F和CR借鑒前期產生優質解的經驗進行自適應調整[6]。該算法中F的設置服從均值為0.5、標準方差為0.3的正態分布N（0.5，0.32），并應用于當前種群的每一差分向量，從而平衡整個優化過程的探索（F較大時）與開發（F較小）能力。CR的值服從均值為CRm，標準方差為Std的正態分布N（CRm， Std2）。將CRm初始化為0.5，此時Std應設置為一個很小的值保證CR的取值為[0，1]，因此將Std設置為0.1。SaDE算法中的自適應機制中也涉及參數的調節，如正態分布的標準方差。算法中對問題不太敏感的參數代替敏感度較高的參數，因此自適應DE算法能夠獲得比傳統DE算法更好的性能。

Zhang和Sanderson[7]提出一種新的適應差分進化算法（JADE）。在JADE算法中，對每個個體，分別應用標準正態分布和柯西分布采樣確定交叉概率CR和縮放因子F。

3.2 操作算子策略的改進

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

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

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

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

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

3.3 混合差分進化算法

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

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

4 總結與展望

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

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

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

[3]張航，王偉，鄭玲等.一種基于密度聚類的小生境差分進化算法[J].計算機工程與應用，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]沈濟南，梁芳，鄭明輝.一種新的混合差分粒子群優化算法及其應用[J].四川大學學報（工程科學版），2014.46（6）：38-43.

李斌（1974—），男（回族），河南建筑職業技術學院，高級講師，電氣、物理方向

2017-08-23