大規(guī)模優(yōu)化問題的差分進(jìn)化策略對(duì)比實(shí)驗(yàn)研究?

楊茂保

【摘要】差分進(jìn)化算法（Differential Evolution，DE）有多種進(jìn)化策略，并在求解各種優(yōu)化問題時(shí)存在較大性能差異，求解大規(guī)模優(yōu)化問題時(shí)不同策略間差異尤其明顯。利用標(biāo)準(zhǔn)測試函數(shù)集對(duì)常用5種差分進(jìn)化策略進(jìn)行對(duì)比實(shí)驗(yàn)研究，分析這些策略的求解效果，總結(jié)求解大規(guī)模優(yōu)化問題的不同差分進(jìn)化策略適用性，為大規(guī)模優(yōu)化問題的差分進(jìn)化求解的策略選擇提供幫助。

【關(guān)鍵詞】大規(guī)模；優(yōu)化問題；差分進(jìn)化；進(jìn)化策略；對(duì)比實(shí)驗(yàn)

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：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 引言

大數(shù)據(jù)時(shí)代，大規(guī)模優(yōu)化問題在科學(xué)研究和工程實(shí)踐中不斷涌現(xiàn)，比如網(wǎng)絡(luò)大數(shù)據(jù)挖掘、過程系統(tǒng)的大規(guī)模優(yōu)化等，這些優(yōu)化問題一般具有非線性、多峰、不可微、復(fù)雜度高等特性，依賴硬件和傳統(tǒng)優(yōu)化方法往往難以求解。近年來由于進(jìn)化算法在求解復(fù)雜優(yōu)化問題上的優(yōu)越性能，使其廣泛應(yīng)用于約束優(yōu)化問題求解、自適應(yīng)控制、經(jīng)濟(jì)分配等領(lǐng)域[1]。

在進(jìn)化算法中，差分進(jìn)化算法吸引了眾多關(guān)注，自差分算法正式形成定義以來，已對(duì)其展開了深入的分析及研究[2]，并提出了各種改進(jìn)DE算法的差分進(jìn)化策略，現(xiàn)有的差分進(jìn)化策略適用于低維中小規(guī)模優(yōu)化問題，在面向高維大規(guī)模優(yōu)化問題時(shí)，差分進(jìn)化計(jì)算雖然可以不受規(guī)模條件限制，但與低維優(yōu)化問題相比在求解高維優(yōu)化問題時(shí)出現(xiàn)收斂速度慢、局部優(yōu)化等問題[5]。近期文獻(xiàn)中也相繼涌現(xiàn)了在求解大規(guī)模優(yōu)化問題的改進(jìn)差分策略。畢曉君等[1]設(shè)計(jì)開發(fā)了一種高維多目標(biāo)多方向協(xié)同進(jìn)化算法（HMMCA），在HMMCA中應(yīng)用一種混合變異策略加強(qiáng)算法在每個(gè)方向上的收斂能力?？紫橛碌萚2]在求解大規(guī)模問題的改進(jìn)算法中采用兩區(qū)間選擇策略，提高解決大規(guī)模系統(tǒng)可靠性問題時(shí)的尋優(yōu)效果。

本文圍繞文獻(xiàn)[6]中的5個(gè)差分策略和10個(gè)優(yōu)化問題利用標(biāo)準(zhǔn)DE算法對(duì)500維的高維化問題進(jìn)行測試，對(duì)每個(gè)問題分別設(shè)計(jì)30次獨(dú)立實(shí)驗(yàn)，記錄最好解和平均值以及標(biāo)準(zhǔn)方差，通過對(duì)比測試結(jié)果來分析評(píng)價(jià)各種差分策略在面向大規(guī)模優(yōu)化問題時(shí)的搜索性能、收斂速度、穩(wěn)定性和適用情況。

1 標(biāo)準(zhǔn)差分進(jìn)化算法

差分進(jìn)化（DE）算法由Storn等人于1995年提出，是一種新興的進(jìn)化計(jì)算技術(shù)。DE算法是一種模擬生物進(jìn)化規(guī)律的智能算法，基本思想是通過種群內(nèi)個(gè)體的交流、通過反復(fù)迭代，使得那些適應(yīng)環(huán)境的個(gè)體獲得了保存，從而逼近問題最優(yōu)解。標(biāo)準(zhǔn)DE的算法流程如圖1所示。

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

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

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

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

5 結(jié)束語

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

參考文獻(xiàn)

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

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

[3]王元卓，靳小龍，程學(xué)旗.網(wǎng)絡(luò)大數(shù)據(jù)：現(xiàn)狀與展望[J].計(jì)算機(jī)學(xué)報(bào)， 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ìn)的差異演化算法[J].計(jì)算機(jī)工程， 2009，35（24）：194-195，198.

[6]劉琛，林盈，胡曉敏.差分演化算法各種更新策略的對(duì)比分析[J].計(jì)算機(jī)科學(xué)與探索， 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]王旭，趙曙光.解決高維優(yōu)化問題的差分進(jìn)化算法[J].計(jì)算機(jī)應(yīng)用， 2014，34（1）：179-181.

[12]林志毅，王玲玲.求解高維函數(shù)優(yōu)化問題的混合蜂群算法[J].計(jì)算機(jī)科學(xué)， 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.