呼忠權(quán) 王洪斌

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

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

中圖分類號(hào)： TN967.34?34; TP18? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)： 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)化問題已在人工智能、計(jì)算機(jī)科學(xué)、信息科學(xué)、自動(dòng)化等眾多領(lǐng)域得到極其廣泛的應(yīng)用。而全局優(yōu)化算法成為目標(biāo)優(yōu)化問題的關(guān)鍵，優(yōu)化算法普遍存在早熟收斂、全局搜索與局部尋優(yōu)的矛盾等問題。因此，近年來，隨機(jī)啟發(fā)式搜索算法在全局優(yōu)化問題上得到了較大關(guān)注，而差分進(jìn)化算法在此類算法中表現(xiàn)的更為優(yōu)秀，引起了學(xué)者的極大關(guān)注。

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

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

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

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

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

Mantegna提出的生成Lévy隨機(jī)步長[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飛行和差分進(jìn)化算法的基本進(jìn)化模式二者結(jié)合，共同完成種群的進(jìn)化。針對(duì)基本差分進(jìn)化算法對(duì)參數(shù)選擇比較敏感，引入自適應(yīng)變異縮放因子（F）和自適應(yīng)交叉概率（CR），用于改善算法性能。

2.1? 變異模式

變異模式實(shí)現(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)的隨機(jī)整數(shù)，NP表示種群大小;g表示進(jìn)化代數(shù);[Gm]表示最大迭代次數(shù);[Xi（g）]表示第g代種群中第i個(gè)個(gè)體;F表示縮放因子;[Xbest（g）]表示當(dāng)前種群中的最優(yōu)個(gè)體;[L（g）]表示使用Lévy飛行產(chǎn)生的新個(gè)體;[Vi（g+1）]表示第g代種群中的臨時(shí)新個(gè)體。

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

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

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

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

[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]是個(gè)體[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） 初始化種群，并評(píng)估每個(gè)個(gè)體。

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

4） 變異模式的選擇，并對(duì)個(gè)體進(jìn)行變異操作。

5） 交叉操作。

6） 選擇操作。

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

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

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

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

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

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

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

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

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

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

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

4? 結(jié)? 語

將行走步長滿足Lévy分布的Lévy飛行變異方式引入到差分進(jìn)化算法中，提出基于Lévy飛行的自適應(yīng)差分進(jìn)化算法，并通過對(duì)10組標(biāo)準(zhǔn)測試函數(shù)進(jìn)行求解計(jì)算對(duì)比，以及對(duì)降維函數(shù)求解后種群的分布分析。結(jié)果表明，所提算法能夠一定程度上增強(qiáng)種群的差異性、避免早熟收斂，同時(shí)增強(qiáng)了原有算法的全局搜索和局部尋優(yōu)能力，為算法的工程應(yīng)用提供了一定的理論支撐。雖然算法在理論分析上尚顯不足，但其優(yōu)異的表現(xiàn)，相信隨著研究的深入，差分進(jìn)化算法定將取得更為廣闊的應(yīng)用。

參考文獻(xiàn)

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

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

[5] 張貴軍，王柳靜，周曉根，等.基于共軛增強(qiáng)策略的差分進(jìn)化算法[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ì)算平臺(tái)的差分進(jìn)化算法改進(jìn)研究[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] 張雪霞，陳維榮，戴朝華.帶局部搜索的動(dòng)態(tài)多群體自適應(yīng)差分進(jìn)化算法及函數(shù)優(yōu)化[J].電子學(xué)報(bào)，2010，38（8）：1825?1830.

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