張 超

(宿州職業(yè)技術(shù)學(xué)院計算機信息系，安徽宿州 234101)

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

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

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

1 風(fēng)驅(qū)動優(yōu)化算法

風(fēng)驅(qū)動優(yōu)化算法，使用牛頓第二運動定律和理想氣體狀態(tài)方程，作為算法速度更新方式推導(dǎo)的主要理論依據(jù)，其方程如下：

(1)

P=ρRT.

(2)

(3)

(4)

(5)

(6)

(7)

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

(8)

(9)

(10)

(11)

(12)

綜上所述，(12)式即為WDO算法的空氣質(zhì)點的速度更新方式。(12)式右邊包含的4項，分別代表了摩擦力、重力、氣壓梯度力和科里奧利力對空氣質(zhì)點速度的影響。對于(12)式中包含的4個算法參數(shù)：a(摩擦力系數(shù))、g(重力加速度常數(shù))、RT系數(shù)和c(科里奧利力系數(shù))，Bayraktar Z[11]在數(shù)值實驗的基礎(chǔ)上，給出了推薦取值范圍，一般地，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飛行的風(fēng)驅(qū)動優(yōu)化算法

2.1 Lévy飛行

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

(15)

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

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

(16)

σ2(s)～s.

(17)

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

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

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

(18)

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

(19)

其中，

(20)

2.2 LWDO算法

2.2.1 LWDO算法思想

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

(21)

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

2.2.2 LWDO算法流程

LWDO算法的執(zhí)行流程如圖2所示。

圖2 LWDO算法流程

3 仿真實驗與性能分析

3.1 實驗設(shè)計與測試函數(shù)

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

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

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

表1 測試函數(shù)

3.2 實驗結(jié)果和性能分析

算法性能評價使用50次實驗的平均值和標準差兩個指標，實驗結(jié)果見表2?？梢钥闯?，在f1、f2和f3三個單峰函數(shù)上，LWDO算法和傳統(tǒng)WDO算法及其改進算法AWDO、GWDO一樣，都能收斂到函數(shù)的理論極值，優(yōu)于PSO、GA和FPA三種智能算法。在f4函數(shù)上，LWDO算法的尋優(yōu)性能略優(yōu)于其他6種對比算法。

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

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

表2 實驗結(jié)果

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

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

圖3 適應(yīng)度收斂曲線

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

圖4 7種算法的全局最優(yōu)值方差分析

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

4 結(jié)語

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

[參考文獻]

[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]陳彬彬,曹中清,余勝威.基于風(fēng)驅(qū)動優(yōu)化算法WDO的PID參數(shù)優(yōu)化[J].計算機工程與應(yīng)用,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]牛培峰,趙振,馬云鵬,等.基于風(fēng)驅(qū)動算法的鍋爐NO_x排放模型優(yōu)化[J].動力工程學(xué)報,2016(9):732-738.

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

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

[7]毛晟,張貞凱,田雨波.基于風(fēng)驅(qū)動算法的機會陣雷達波束圖綜合[J].江蘇科技大學(xué)學(xué)報:自然科學(xué)版,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].浙江大學(xué)學(xué)報:工學(xué)版,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.