基于Lévy飛行的風驅動優化算法

張 超

(宿州職業技術學院計算機信息系，安徽宿州 234101)

空氣相對于地面的運動稱為風，風驅動優化算法[1](Wind Driven Optimization，WDO)是對空氣質點受力運動達到氣壓平衡的狀態進行模擬，推導出算法的速度更新計算方式。與其他智能算法相比，WDO算法的速度更新方程是從物理學公式推導而來，包含了各種自然界中真實存在的力對速度的影響，具有實際物理意義，其具有較強的全局搜索能力和較快的收斂速度[2]，已被成功應用于機器人未知靜態和動態環境路徑規劃[3]、鍋爐NO_x排放模型優化[4]、各種電磁學問題優化[5-7]等領域。

WDO算法對參數取值敏感，涉及4個參數：RT系數、g(重力加速度常數)、a(摩擦力系數)、c(科里奧利力系數)彼此緊密聯系相互耦合，不同的取值組合對算法性能影響較大且不易確定；在算法迭代后期易陷入局部極值，導致算法“早熟”，使種群失去多樣性。鑒于此，國內外學者對WDO算法進行了優化和改進研究。Bayraktar Z[8]借助CMAES算法(Covariance Matrix Adaptation Evaluation Strategy，CMAES)的自適應評價策略確定WDO算法的參數取值，有效地提升了通過人工試探確定參數的效率。Javaid N[9]等將遺傳算法和風驅動算法混合，使用遺傳算法的交叉變異操作替換風驅動算法的速度更新步驟，解決因更新速度過大而導致的算法性能下降問題。Boulesnane A[10]根據大氣層中真實存在的低壓區和高壓區劃分不同區域，采取有效避碰措施防止種群之間的沖突，實現了一種適應動態環境優化的風驅動優化算法。

鑒于WDO算法存在的缺陷，本文旨在增強算法的尋優性能。維護種群多樣性是提升群智能算法性能的有效策略，而變異操作是群智能算法中群體多樣性產生的重要機制之一。為此，本文實現了基于Lévy飛行變異的風驅動算法(Wind driven optimization algorithm with Lévy Flight，LWDO)，針對10個經典測試函數做仿真實驗，實驗結果表明，LWDO算法的尋優性能較傳統WDO算法及相關對比算法有提升，從而驗證了改進策略的有效性。

1 風驅動優化算法

風驅動優化算法，使用牛頓第二運動定律和理想氣體狀態方程，作為算法速度更新方式推導的主要理論依據，其方程如下：

(1)

P=ρRT.

(2)

(3)

(4)

(5)

(6)

(7)

為了簡化模型便于公式推導，WDO算法令δV=1，假定Δt=1，得到：

(8)

(9)

(10)

(11)

(12)

綜上所述，(12)式即為WDO算法的空氣質點的速度更新方式。(12)式右邊包含的4項，分別代表了摩擦力、重力、氣壓梯度力和科里奧利力對空氣質點速度的影響。對于(12)式中包含的4個算法參數：a(摩擦力系數)、g(重力加速度常數)、RT系數和c(科里奧利力系數)，Bayraktar Z[11]在數值實驗的基礎上，給出了推薦取值范圍，一般地，a取[0.8,0.9]，g取[0.6,0.7]，RT取[1.0,2.0]，c取[0.05,3.6]。

WDO算法的位置更新方式通過(13)式計算：

(13)

(14)

2 基于Lévy飛行的風驅動優化算法

2.1 Lévy飛行

Lévy飛行是特殊的隨機游走模式，是一種馬爾科夫過程，它行走的隨機步長服從于一個重尾的Lévy分布。Lévy分布一般用一個簡單的冪律公式表示：

(15)

其中，s為隨機步長，β為指數參數。Lévy飛行在未知的大規模空間搜索時，比布朗隨機運動更加有效，原因之一是Lévy飛行擁有快速增長的無限方差，它比布朗隨機運動的方差增長得更快[12]。(16)式和(17)式分別為Lévy飛行和布朗隨機運動的方差增長表示形式。

σ2(s)～s3-β，1<β≤2.

(16)

σ2(s)～s.

(17)

Lévy飛行在搜索過程中，頻繁的短距離局部搜索與偶爾較長距離的游走相間，如圖1所示。因此，在搜索到最優解附近時，能夠加速局部搜索，而少數較長距離跳躍式游走，有利于拓展搜索范圍，使之更易逃離局部極值的束縛。研究表明，自然界中很多生物的運動軌跡都具有Lévy飛行特征[13]。Lévy飛行已被成功應用于粒子群優化算法、布谷鳥算法、花授粉算法、螢火蟲算法等智能優化算法中，并且效果良好[14]。

圖1 100次的二維Lévy飛行軌跡(從原點(0,0)開始，標記為□)

在文獻[15]中，Lévy飛行的隨機步長s，計算公式如下：

(18)

其中，u和v由(19)式正態分布獲得：

(19)

其中，

(20)

2.2 LWDO算法

2.2.1 LWDO算法思想

WDO算法在迭代搜索過程中，易受到局部極值的干擾，使算法出現“早熟”現象，導致種群的多樣性喪失，算法進化陷入停滯。增加變異機制是維護種群多樣性的有效策略，通過變異操作能夠增加算法獲得新的候選解機會，有助于算法跳出當前局部極值陷阱，保障算法正常進化，獲得全局最優解。鑒于Lévy飛行的頻繁短距離局部搜索特性，當搜索到最優解附近時，能夠增強、加速局部搜索速度。為此，本文提出一種基于Lévy飛行變異的風驅動優化改進算法LWDO，LWDO算法通過設置一個變異參數P∈[0,1]控制空氣質點變異，如果隨機產生一個隨機數小于等于P，那么該空氣質點將被選擇發生變異，變異的空氣質點使用公式(21)進行位置更新計算。

(21)

其中，xi為被選擇空氣質點變異后的新位置，Levy(s)為Lévy分布，xopt為到目前位置最優空氣質點位置。式(21)將到目前為止最優空氣質點位置，通過Lévy飛行變異后賦予被選擇變異的空氣質點，一是充分利用了種群中最優個體的優勢信息；二是通過Lévy飛行對最優空氣質點附近的搜索空間進行頻繁局部搜索，加快了局部搜索的收斂速度；三是伴隨Lévy飛行的少數較長距離跳躍式游走，又能使算法跳出局部機制的束縛，搜索到更大空間，提升了算法收斂到全局最優解的概率。

2.2.2 LWDO算法流程

LWDO算法的執行流程如圖2所示。

圖2 LWDO算法流程

3 仿真實驗與性能分析

3.1 實驗設計與測試函數

為了驗證LWDO算法的尋優性能，本節使用10個經典測試函數進行仿真實驗，其中包括單峰函數、多峰函數和旋轉函數，函數具體信息見表1，表1中f9、f10兩個旋轉函數的旋轉方法具體可參見文獻[16]。

本節實驗著重比較LWDO算法與傳統WDO算法、改進AWDO算法及其將2.2.1節(21)式中Lévy分布變異替換為高斯分布變異的風驅動改進算法，為比較方便，記為GWDO。與粒子群算法(Particle Swarm Optimization，PSO)、花授粉算法(Flower Pollination Algorithm，FPA)、遺傳算法(Genetic Algorithm，GA)等經典和新興的智能算法進行比較。

算法的參數設置：7種算法的種群規模設為n=30，最大迭代次數T=200，函數維度d=30。LWDO、WDO和GWDO算法的a=0.8，g=0.7，RT=1.0，c=0.7，maxV=0.3。PSO的學習因子c1=c2=2，最大速度為搜索空間的一半。GA的交叉概率為0.9，變異概率為0.08。FPA算法的p=0.2，γ=16。

表1 測試函數

3.2 實驗結果和性能分析

算法性能評價使用50次實驗的平均值和標準差兩個指標，實驗結果見表2。可以看出，在f1、f2和f3三個單峰函數上，LWDO算法和傳統WDO算法及其改進算法AWDO、GWDO一樣，都能收斂到函數的理論極值，優于PSO、GA和FPA三種智能算法。在f4函數上，LWDO算法的尋優性能略優于其他6種對比算法。

在f5、f6、f7、f8四個多峰函數上，LWDO算法的平均值和標準差均為0，說明LWDO算法50次仿真實驗均能收斂到四個函數的理論極值，尋優性能較好；WDO、AWDO、GWDO三種算法在f7、f8函數上的平均值和標準差均為0，說明與LWDO算法一樣，50次仿真實驗均能收斂到這兩個函數的理論極值，也優于PSO、GA和FPA三種智能算法；而在f5、f6函數上WDO、AWDO、GWDO三種算法的尋優性能不如LWDO算法，在f5函數上WDO、AWDO、GWDO三種算法的尋優性能也明顯低于PSO算法，尋優性能不高。

在f9、f10兩個旋轉函數上，LWDO算法的平均值和標準差均為0，說明50次實驗均能收斂到函數的理論極值，尋優性能明顯優于其他6種對比算法。

表2 實驗結果

圖3為7種算法在測試函數上的適應度值收斂曲線(適應度值做10為底的對數處理)。由圖3可以看出，LWDO算法在除了f4的其他9個函數上，收斂曲線出現間斷，說明LWDO算法已收斂到函數的理論極值0，對數真數為0時曲線不顯示，并且算法收斂到函數最優值的速度顯著快于其他6種對比算法；對于f4函數，LWDO算法雖未能收斂到函數的理論極值，但從適應度的收斂曲線看，也優于對比算法。

高斯變異是智能算法優化中最常使用的增強局部搜索的方法，從圖3亦可獲知，使用了高斯變異的GWDO算法，在f1、f2、f3、f7、f8五個函數上，收斂到函數最優值的速度顯著快于WDO、AWDO、PSO、GA和FPA算法，但與使用了Lévy分布變異的LWDO算法比，尋優性能不如LWDO算法，從而說明通過對風驅動優化算法的當前最優解實施Lévy分布擾動，作為被選擇變異空氣質點的新位置，充分利用了Lévy分布頻繁短距離局部搜索的特征，使最優解附近的搜索區域充分被搜索，提升了算法局部搜索的速度，而Lévy分布偶爾長距離搜索的特性又拓展了算法的可行搜索空間，增強了算法跳出局部極值的概率，進而加快了算法收斂到全局最優解的速度。

圖3 適應度收斂曲線

圖4為7種算法針對10個測試函數連續獨立進行50次實驗的全局最優值方差分析，由圖4可以看出，LWDO算法50次實驗的最優值分布穩定，特別在f5、f6、f9、f10函數上，比傳統的WDO算法和改進的AWDO算法、GWDO算法尋優性能要好。

圖4 7種算法的全局最優值方差分析

綜上所述，LWDO算法在9個函數上的平均值和標準差均為0，在f4函數上的尋優結果也優于其他6種對比算法，因此本文改進的LWDO算法與對比算法相比具有一定競爭性。

4 結語

本文使用Lévy飛行對風驅動優化算法進行了改進。使用10個包括單峰函數、多峰函數和旋轉函數在內的測試函數，驗證所提改進算法LWDO的性能。LWDO算法在9個函數上，分別獨立進行50次實驗的結果表明，LWDO算法每次都能夠收斂到函數的理論極值，并且所用迭代次數少于對比算法，說明本文提出的改進策略能夠加快風驅動優化算法的局部搜索速度，并有效地防止了算法陷入局部極值，比傳統風驅動算法的尋優性能有所增強。本文將LWDO算法應用在連續空間的函數優化問題中，下一步我們將繼續研究風驅動算法解決離散空間的問題，以及利用LWDO算法解決實際工程應用中比較常見的多目標優化問題。

[參考文獻]

[1]Bayraktar Z,Komurcu M,Wemer D H.Wind Driven Optirnization(WDO):A novel nature-inspired optimization algorithm and its application to electromagneties[C].2010 IEEE Antennas and Propagation Society International Symposium (APSURSI),IEEE,2010:1-4.

[2]陳彬彬,曹中清,余勝威.基于風驅動優化算法WDO的PID參數優化[J].計算機工程與應用,2016(14):250-253,260.

[3]Anish Pandey,Dayal R Parhi.Optimum path planning of mobile robot in unknown static and dynamic environments using Fuzzy-Wind Driven Optimization algorithm[J].Defence Technology,2017(1):47-58.

[4]牛培峰,趙振,馬云鵬,等.基于風驅動算法的鍋爐NO_x排放模型優化[J].動力工程學報,2016(9):732-738.

[5]金雪,夏偉杰,潘彥均,等.基于改進風驅動優化算法的稀疏陣列旁瓣抑制方法[J].數據采集與處理,2017(6):1169-1178.

[6]費曉,張貞凱,田雨波,等.風驅動優化的共享孔徑方向圖綜合[J/OL].電光與控制:1-5[2018-03-20].http://kns.cnki.net/kcms/detail/41.1227.TN.20180314.0920.018.html.

[7]毛晟,張貞凱,田雨波.基于風驅動算法的機會陣雷達波束圖綜合[J].江蘇科技大學學報:自然科學版,2017(4):485-489.

[8]Bayraktar Z,Komurcu M.Adaptive wind driven optimization[C].Eai International Conference on Bio-Inspired Information and Communications Technologies,ICST,2016:124-127.

[9]Javaid N,Javaid S,Abdul W,et al.A Hybrid genetic wind driven heuristic optimization algorithm for demand side management in smart grid[J].Energies,2017(10):1-27.

[10]Boulesnane A,Meshoul S.WD2O:a novel wind driven dynamic optimization approach with effective change detection[J].Applied Intelligence,2017(1):1-17.

[11]Bayraktar Z,Komurcu M,Bossard J A,et al.The wind driven optimization technique and its application in electromagnetics[J].IEEE Transactions on Antennas and Propagation,2013(5):2745-2757.

[12]Yang X S.Nature-Inspired Metaheuristic Algorithms[M].Luniver Press,2008.

[13]朱曉恩,郝欣,夏順仁.基于Levy flight的特征選擇算法[J].浙江大學學報:工學版,2013(4):638-643.

[14]Jamil M.Levy Flights and Global Optimization[M].Swarm Intelligence and Bio-Inspired Computation: Theory and Applications,2013:49-72.

[15]Mantegna RN.Fast,accurate algorithm for numerical simulation of Levy stable stochastic processes[J].Physical Review E,1994(49):4677-4683.

[16]Liang J J,Qin A K,Suganthan P N,et al.Comprehensive learning particle swarm optimizer for global optimization of multimodal functions[J].IEEE Transactions on Evolutionary Computation,2006(3):281-295.