基于Lévy飛行的自適應(yīng)差分進化算法

呼忠權(quán) 王洪斌

摘? 要： 針對目前差分進化算法存在全局搜索與局部尋優(yōu)的矛盾、搜索停滯、收斂速度慢的問題，提出一種改進算法：基于Lévy飛行的自適應(yīng)差分進化算法。該算法鑒于Lévy飛行步長符合重尾分布的特點，在變異過程中結(jié)合差分進化算法的基本變異和Lévy飛行變異兩種模式，并通過引入自適應(yīng)縮放因子和交叉概率算子，改善種群在交叉與變異過程中的不足。通過理論分析與Benchmark函數(shù)的數(shù)值驗證，并與其他6種算法進行比較。結(jié)果表明，所提新算法能夠在全局搜索與局部尋優(yōu)之間進行較好的平衡，而且收斂速度更快，種群多樣性得到了很好的保存，一定程度上避免了搜索停滯的出現(xiàn)。

關(guān)鍵詞： 自適應(yīng)差分進化算法; Lévy飛行; 全局搜索; 局部尋優(yōu); 理論分析; 實驗驗證

中圖分類號： TN967.34?34; TP18? ? ? ? ? ? ? ? ?文獻標(biāo)識碼： A? ? ? ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2020）04?0167?06

Adaptive differential evolution algorithm based on Lévy flight

HU Zhongquan， WANG Hongbin

（Hebei Key Laboratory of Industrial Computer Control Engineering， Yanshan University， Qinhuangdao 066004， China）

Abstract： A new improved algorithm： adaptive differential evolution algorithm based on Lévy flight （ADELF） is proposed to improve contradictions between global search and local optimization， search stagnation and slow convergence in current differential evolution algorithm. The algorithm was consistent with the heavy tailed distribution of Lévy flight steps. In consideration of the fact that Lévy flight step size conforms to the characteristics of heavy?tailed distribution， this algorithm combines the basic variation of differential evolution algorithm and Lévy flight variation in the variation process. The adaptive scaling factor and crossover probability operator are introduced to improve the shortage of population in the process of cross and mutation. The experiment was performed the theoretical analysis and numerical verification of benchmark function， with which other 6 algorithms are compared. The results show that the new algorithm can make a better balance between the global search and the local optimization， has faster convergence speed， and the population diversity is well preserved， which avoids the appearance of the search stagnation to a certain extent.

Keywords： adaptive differential evolution algorithm; Lévy flight; global search; local optimization; theoretical analysis; experimental verification

0? 引? 言

目標(biāo)優(yōu)化問題已在人工智能、計算機科學(xué)、信息科學(xué)、自動化等眾多領(lǐng)域得到極其廣泛的應(yīng)用。而全局優(yōu)化算法成為目標(biāo)優(yōu)化問題的關(guān)鍵，優(yōu)化算法普遍存在早熟收斂、全局搜索與局部尋優(yōu)的矛盾等問題。因此，近年來，隨機啟發(fā)式搜索算法在全局優(yōu)化問題上得到了較大關(guān)注，而差分進化算法在此類算法中表現(xiàn)的更為優(yōu)秀，引起了學(xué)者的極大關(guān)注。

差分進化[1]（Differential Evolution，DE）算法具有可靠、準(zhǔn)確、快速、魯棒性強等優(yōu)點，在眾多領(lǐng)域中得到應(yīng)用。但原始的DE算法存在著明顯的不足：早熟收斂、搜索停滯、收斂速度與收斂精度的矛盾以及對控制參數(shù)的選擇非常敏感。

在算法性能改善方面，國內(nèi)外都進行了很多研究。文獻[2]總結(jié)分析了近年來DE算法的研究進展，并推薦使用自適應(yīng)種群大小的方式來求解高維實際問題;文獻[3]引入外部存檔和精英保留策略的方法對算法進行改進，改善了算法的性能;文獻[4]對變異策略和參數(shù)都采用了自適應(yīng)選擇和調(diào)整，改善了已有算法的收斂速度和求解精度;文獻[5]采用共軛增強的方法指引算法進行局部搜索，平衡了算法的全局搜索與局部尋優(yōu)的能力;文獻[6]利用Lévy飛行進行步長調(diào)整，在改進算法中結(jié)合已有的PGLFDE和FBDE算法來改進基本DE算法的性能;文獻[7]利用云計算改進算法計算速度，并將差分算法與輪盤賭相結(jié)合用于改善全局尋優(yōu)能力。

上述對算法的改進，都取得了一定的研究成果，但在如何平衡全局搜索與局部尋優(yōu)、收斂速度以及保持種群多樣性等方面還有待進一步研究。因此，本文在目前研究的基礎(chǔ)上，提出基于Lévy飛行的自適應(yīng)差分進化算法（Adaptive Differential Evolution Algorithm Based on Lévy Flight，ADELF）。

1? Lévy分布與Lévy飛行

Lévy分布[8?9]屬于重尾分布，相比于高斯分布和柯西分布分布更為廣泛。Lévy過程的框架最早是在20世紀(jì)30年代由法國數(shù)學(xué)家Paul Pierre Lévy提出。Lévy分布的概率密度函數(shù)為：

[Lα，γ（z）=1π0∞exp（-γqα）cos（qz）dq] （1）

式中，[α， γ]為兩個特征參數(shù)。Lévy分布、高斯分布和柯西分布的概率分布對比如圖1所示。

Lévy飛行是一種馬爾可夫[10]隨機過程，行走的步長滿足一個重尾的Lévy分布。Lévy飛行具有更強的擾動能力，是一種比布朗隨機運動更有效的搜索策略，通過大概率短距離和小概率長距離搜索，既可以擴大搜索范圍，又能在特定區(qū)域增強局部搜索效果，提高算法的全局搜索和局部尋優(yōu)能力。

Mantegna提出的生成Lévy隨機步長[7]的公式為：

[s=xy1α] （2）

式中，x和y服從正態(tài)分布，[x?N（0，σ2x）]，[y?N（0，σ2y）]。

[σx（α）=Γ（1+α）?sin（πα2）Γ[（1+α）2]?α?2（α-1）21α] （3）

[σy=1] （4）

式中，[Γ（x）]表示伽馬分布。

200次Lévy飛行的曲線見圖2。行步長分布見圖3。

2? ADELF算法結(jié)構(gòu)

ADELF算法基本思想是將Lévy飛行和差分進化算法的基本進化模式二者結(jié)合，共同完成種群的進化。針對基本差分進化算法對參數(shù)選擇比較敏感，引入自適應(yīng)變異縮放因子（F）和自適應(yīng)交叉概率（CR），用于改善算法性能。

2.1? 變異模式

變異模式實現(xiàn)方法如下：

[Vi（g+1）=Xbest（g）+F?（Xr2（g）-Xr1（g）），? ? ? ? ? ? ? ? ? ? ? ? ? ? rand（0，1）≤cL（g），? ? ? ? ? ? ? ? otherwise? ] （5）

式中：[c=gGm];[i≠r1≠r2]，[i=1，2，…，NP];[r1，r2]均為區(qū)間[1， NP]內(nèi)的隨機整數(shù)，NP表示種群大小;g表示進化代數(shù);[Gm]表示最大迭代次數(shù);[Xi（g）]表示第g代種群中第i個個體;F表示縮放因子;[Xbest（g）]表示當(dāng)前種群中的最優(yōu)個體;[L（g）]表示使用Lévy飛行產(chǎn)生的新個體;[Vi（g+1）]表示第g代種群中的臨時新個體。

變異過程中，基本變異模式中待變異個體為當(dāng)前種群中的最優(yōu)個體，保存了尋優(yōu)的方向，加速了算法的收斂速度;Lévy飛行產(chǎn)生的新變異個體保證了算法的全局尋優(yōu)能力，減小了算法陷入局部最優(yōu)解的可能性。

選擇條件設(shè)置為rand（0，1）與[c]進行比較，而不是將rand（0，1）與c進行比較，從圖4中可以看出，這種方法可以使基本變異模式被選中的概率增大，加快了算法的收斂速度。

2.2? 自適應(yīng)參數(shù)

自適應(yīng)參數(shù)[11]（F和CR）能夠較好地平衡全局搜索和局部尋優(yōu)，能夠一定程度上降低算法對參數(shù)的敏感性。為了保證收斂速度，避免早熟收斂的發(fā)生，采取自適應(yīng)機制對縮放因子和交叉概率進行賦值，具體方法如下：

[F=Fmax-（Fmax-Fmin）·fi - fminfmax+fmin，? ?fi≥f-Fmax，? ? ? fi

[CR=CRmin+（CRmax-CRmin）·fi - fminfmax+fmin，? ?fi≥f-CRmin，? ? ?fi

式中：[Fmax]和[Fmin]分別為F的上、下限;[CRmax]和[CRmin]分別為CR的上、下限;[fi]是個體[Xi（g）]的適應(yīng)度值;[fmax]和[fmin]分別是當(dāng)前種群中最大和最小的適應(yīng)度值;[f-]為當(dāng)前種群適應(yīng)度的平均值。

2.3? 算法描述

ADELF算法主要流程描述如下：

輸入：搜索空間、種群大小、目標(biāo)函數(shù)、迭代次數(shù)、求解精度。

輸出：最優(yōu)解。

1） 參數(shù)初始化：種群大小、最大迭代次數(shù)、縮放因子、交叉概率、求解精度等。

2） 初始化種群，并評估每個個體。

3） 計算適應(yīng)度值和目標(biāo)函數(shù)值。

4） 變異模式的選擇，并對個體進行變異操作。

5） 交叉操作。

6） 選擇操作。

7） 結(jié)束條件：滿足求解精度要求或者達到最大迭代次數(shù);否則，轉(zhuǎn)至步驟3）。

3? 數(shù)值求解及分析

本文通過對10個Benchmark測試函數(shù)進行了數(shù)值求解，將ADELF算法與另外6種算法進行比較。另外6種算法的參數(shù)設(shè)置詳見文獻[11?12]。

表1中PSO?w，CLPSO，DMSDELS和ADDE的部分求解數(shù)據(jù)來自文獻[11]。表2為10個Benchmark測試函數(shù)，維數(shù)（D）、自變量范圍（S）、函數(shù)全局最小值和函數(shù)類型分別給出。數(shù)值求解結(jié)果詳見表1。

對于單峰函數(shù)的求解，除了函數(shù)[f3（x）]，ADELF算法求解能力優(yōu)于其他所有算法，求解的最優(yōu)值更加接近理論最優(yōu)解。由于DE2算法的收斂速度最快，對于單峰函數(shù)的求解有著明顯的優(yōu)勢，因此，DE2算法在求解[f3（x）]的時候優(yōu)于其他算法。

對于多峰函數(shù)的求解，ADELF和ADDE算法的表現(xiàn)更為優(yōu)秀，求解能力更強。對于函數(shù)[f9（x）]的求解，ADDE算法優(yōu)于ADELF，雖然ADELF也能求解到最優(yōu)解，但是搜索精度和平均值上稍差于ADDE。從10組求解結(jié)果來看，ADELF還是優(yōu)于ADDE的。

通過對函數(shù)求解的結(jié)果可以看出，改進算法結(jié)合了DE2的優(yōu)點，發(fā)揮了Lévy飛行變異的全局搜索的特點。改進算法整體上優(yōu)于列舉的其他算法。

為了深入而準(zhǔn)確地了解算法的收斂速度，分別對數(shù)值求解結(jié)果相近的函數(shù)[f5（x）]和[f6（x）]進行了最優(yōu)解收斂曲線的繪制。為了盡可能消除隨機性帶來的偏差，分別對測試函數(shù)進行20次求解，并計算每代最優(yōu)解的平均值。圖5所示兩幅圖分別對應(yīng)數(shù)函數(shù)[f5（x）]和[f6（x）]的最優(yōu)解的平均值收斂曲線。

由圖5可知，ADELF算法的收斂速度是最快的。從求解結(jié)果和收斂速度上來看ADELF和ADDE算法的表現(xiàn)非常相似。為了更深入地了解兩種算法的求解能力，用這兩種算法分別對2維和3維函數(shù)求解，分析函數(shù)[f5（x）]和[f8（x）]在降維求解后的種群分布。解的分布如圖6、圖7所示。

由表1可知，雖然ADELF和ADDE算法對于函數(shù)[f5（x）]和[f8（x）]的求解結(jié)果相同，但是從圖6和圖7中可知，ADELF比ADDE解的分布更加廣，增加了種群的差異性，利于算法進行全局尋優(yōu)和局部搜索，能夠有效地避免算法的早熟收斂和算法停滯。

綜上所述，ADELF算法僅在函數(shù)[f3（x）]和[f8（x）]的求解時，分別稍差于DE2和ADDE算法。但從10個基準(zhǔn)測試函數(shù)的求解結(jié)果、收斂曲線和種群分布來綜合分析，改進算法的全局尋優(yōu)能力、收斂速度都得到了提高和改善。

4? 結(jié)? 語

將行走步長滿足Lévy分布的Lévy飛行變異方式引入到差分進化算法中，提出基于Lévy飛行的自適應(yīng)差分進化算法，并通過對10組標(biāo)準(zhǔn)測試函數(shù)進行求解計算對比，以及對降維函數(shù)求解后種群的分布分析。結(jié)果表明，所提算法能夠一定程度上增強種群的差異性、避免早熟收斂，同時增強了原有算法的全局搜索和局部尋優(yōu)能力，為算法的工程應(yīng)用提供了一定的理論支撐。雖然算法在理論分析上尚顯不足，但其優(yōu)異的表現(xiàn)，相信隨著研究的深入，差分進化算法定將取得更為廣闊的應(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] PIOTROWSKI A P. Review of differential evolution population size [J]. Swarm & evolutionary computation， 2017（34）： 1?24.

[3] 陶勇，沈濟南.基于自適應(yīng)差分進化策略的多目標(biāo)進化算法[J].控制工程，2018，25（11）：2070?2074.

[4] 閤大海，李元香，龔文引，等.一種求解約束優(yōu)化問題的自適應(yīng)差分進化算法[J].電子學(xué)報，2016，44（10）：2535?2542.

[5] 張貴軍，王柳靜，周曉根，等.基于共軛增強策略的差分進化算法[J].控制與決策，2017，32（7）：1313?1318.

[6] SHARMA H， SHARMA V P， SHARMA A. A modified fitness based differential evolution using population based levy flight strategy [C]// 2016 Second International Conference on Computational Intelligence & Communication Technology. Ghaziabad： IEEE， 2016： 707?711.

[7] 孫潔，連暢.基于云計算平臺的差分進化算法改進研究[J].現(xiàn)代電子技術(shù)，2018，41（17）：163?166.

[8] MANTEGNA R N. Fast， accurate algorithm for numerical simulation of Lévy stable stochastic processes [J]. Physical review e statistical physics plasmas fluids & related interdisciplinary topics， 1994， 49（5）： 4677.

[9] DELAPORTE C. Lévy processes with marked jumps I： limit theorems [J]. Journal of theoretical probability， 2015， 28（4）： 1468?1499.

[10] CHOI T J， CHANG W A. Erratum to： adaptive α?stable differential evolution in numerical optimization [J]. Natural computing， 2017， 16（4）： 1.

[11] 張雪霞，陳維榮，戴朝華.帶局部搜索的動態(tài)多群體自適應(yīng)差分進化算法及函數(shù)優(yōu)化[J].電子學(xué)報，2010，38（8）：1825?1830.

[12] 呼忠權(quán)，王洪斌，李碩.自適應(yīng)雙模式差分進化算法[J].計算機工程與設(shè)計，2015，36（8）：2250?2254.