大規模優化問題的差分進化策略對比實驗研究?

楊茂保

【摘要】差分進化算法（Differential Evolution，DE）有多種進化策略，并在求解各種優化問題時存在較大性能差異，求解大規模優化問題時不同策略間差異尤其明顯。利用標準測試函數集對常用5種差分進化策略進行對比實驗研究，分析這些策略的求解效果，總結求解大規模優化問題的不同差分進化策略適用性，為大規模優化問題的差分進化求解的策略選擇提供幫助。

【關鍵詞】大規模；優化問題；差分進化；進化策略；對比實驗

中圖分類號：TP391 文獻標識碼：A

A comparative experimental study on the differential evolution strategy for large scale optimization problems

YANG Maobao

（Jiujiang University， Jiujiang Jiangxi 332005， China）

[Abstract] Differential evolution algorithm（Differential Evolution，DE） has a variety of evolutionary strategies.And there exists a large performance differences between different strategies while solving multiple optimization problems. Especially，in view of large-scale optimization problem， this difference is particularly obvious. By using the standard test functions， 5 kinds of commonly used differential evolution strategy are compared.Based on the above，by analyzing the effect of these strategies， the paper summarizes the applicability of the differential evolution strategy of this research， which could provide the efficient help for the differential evolution strategy selection in sovling large scale optimization problems.

[Key words] large scale； optimization problem； differential evolution； evolutionary strategy；comparative experiment

0 引言

大數據時代，大規模優化問題在科學研究和工程實踐中不斷涌現，比如網絡大數據挖掘、過程系統的大規模優化等，這些優化問題一般具有非線性、多峰、不可微、復雜度高等特性，依賴硬件和傳統優化方法往往難以求解。近年來由于進化算法在求解復雜優化問題上的優越性能，使其廣泛應用于約束優化問題求解、自適應控制、經濟分配等領域[1]。

在進化算法中，差分進化算法吸引了眾多關注，自差分算法正式形成定義以來，已對其展開了深入的分析及研究[2]，并提出了各種改進DE算法的差分進化策略，現有的差分進化策略適用于低維中小規模優化問題，在面向高維大規模優化問題時，差分進化計算雖然可以不受規模條件限制，但與低維優化問題相比在求解高維優化問題時出現收斂速度慢、局部優化等問題[5]。近期文獻中也相繼涌現了在求解大規模優化問題的改進差分策略。畢曉君等[1]設計開發了一種高維多目標多方向協同進化算法（HMMCA），在HMMCA中應用一種混合變異策略加強算法在每個方向上的收斂能力。孔祥勇等[2]在求解大規模問題的改進算法中采用兩區間選擇策略，提高解決大規模系統可靠性問題時的尋優效果。

本文圍繞文獻[6]中的5個差分策略和10個優化問題利用標準DE算法對500維的高維化問題進行測試，對每個問題分別設計30次獨立實驗，記錄最好解和平均值以及標準方差，通過對比測試結果來分析評價各種差分策略在面向大規模優化問題時的搜索性能、收斂速度、穩定性和適用情況。

1 標準差分進化算法

差分進化（DE）算法由Storn等人于1995年提出，是一種新興的進化計算技術。DE算法是一種模擬生物進化規律的智能算法，基本思想是通過種群內個體的交流、通過反復迭代，使得那些適應環境的個體獲得了保存，從而逼近問題最優解。標準DE的算法流程如圖1所示。

在標準DE算法中，問題的解被抽象成D維空間中的個體，每粒個體均存在一個由優化函數決定的適應度（fitness），首先初始種群，然后經過個體變異、交叉以及選擇這3種基本操作，種群逐代進化直至達到終止條件，從而繁衍出具有更高適應度的個體。描述如下：

1）初始種群。DE算法中，問題的解首先被抽象成一個D維空間，并在這個D維空間上隨機產生NP個有上下界約束條件的個體 ， 。

2）變異算子。DE算法的變異算子是利用當前種群中2個或多個隨機選擇的個體之間的差向量產生新的中間個體（記為 ）。DE算法的變異算子衍變有多種形式，Price和Storn等人先后提出了近10種不同策略的差分進化算法[7]，當前最多使用的變異算子是DE/rand/1/bin，如公式（1）所示：

由前述10個函數的收斂曲線圖對比分析可得，混合策略ES6在10個問題上的進化基本上趨向于ES1，進而得出如下結論：如果改變混合策略對某一策略的選擇概率，則趨向某一策略的程度也相應變化，混合策略在問題上的進化僅僅是受選策略的中和，因而并非有效方法。

5 結束語

針對大規模的高維優化問題難以解決并且優化耗費時間長的不足，實驗證明，僅是通過更新差分進化策略對于高維優化問題卻仍未得到滿意的結果。而利用本次研究實驗及相關文獻分析可知，若將協同進化思想引入到差分進化領域是當前能夠有效避免早熟收斂等現象的全局優化理想算法，同時由此提取得到的關聯規則更顯顯示功用，并在應用于高維優化問題時獲得了突出卓越的研究表現。

參考文獻

[1]孔祥勇，高立群，歐陽海濱，等.求解大規模可靠性問題的改進差分進化算法[J].東北大學學報（自然科學版）， 2014，35（3）：328-332.

[2]畢曉君，張永建，沈繼紅.高維多目標多方向協同進化算法[J].控制與決策， 2014，29（10）：1737-1743.

[3]王元卓，靳小龍，程學旗.網絡大數據：現狀與展望[J].計算機學報， 2013，36（6）：1125-1138.

[4]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.

[5]鄧長壽，趙秉巖，梁昌勇.改進的差異演化算法[J].計算機工程， 2009，35（24）：194-195，198.

[6]劉琛，林盈，胡曉敏.差分演化算法各種更新策略的對比分析[J].計算機科學與探索， 2013，7（11）：983-993.

[7]PRICE K， STORN R， LAMPINEN J. Differential evolution—apractical approach to global optimization[M]. Berlin：Springer， 2005.

[8]YUAN Jungang， SUN Zhiguo， QU Guangji. Study about problems in application of differential evolution[J]. Computer Engineering and Applications， 2007， 43（7）： 75-77.

[9] MEZURA-MONTES E， VELAZQUEZ-REYES J， COELLO C A. A com-parative study of differential evolution variants for global optimization[C]//Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation （GECCO 06）. New York， NY， USA： ACM， 2006： 485-492.

[10] WANG Yong，CAI Zixing，ZHANG Qingfu. Enhancing the search ability of differential evolution through orthogonal crossover [J]. Information Sciences， 2006，185： 153-177.

[11]王旭，趙曙光.解決高維優化問題的差分進化算法[J].計算機應用， 2014，34（1）：179-181.

[12]林志毅，王玲玲.求解高維函數優化問題的混合蜂群算法[J].計算機科學， 2013，40（3）：279-282.

[13] STORN R. On the usage of differential evolution for function optimization[C]//Proceedings of the 1996 Conference of the North American Fuzzy Information Processing Society（NAFIPS 1996）. Berkeley， USA：IEEE， 1996： 519-523.