張 超

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

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

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

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

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

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

(1)

P=ρRT.

(2)

(3)

(4)

(5)

(6)

(7)

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

(8)

(9)

(10)

(11)

(12)

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

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

(13)

(14)

2 基于Lévy飛行的風(fēng)驅(qū)動(dòng)優(yōu)化算法

2.1 Lévy飛行

Lévy飛行是特殊的隨機(jī)游走模式，是一種馬爾科夫過(guò)程，它行走的隨機(jī)步長(zhǎng)服從于一個(gè)重尾的Lévy分布。Lévy分布一般用一個(gè)簡(jiǎn)單的冪律公式表示：

(15)

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

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

(16)

σ2(s)～s.

(17)

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

圖1 100次的二維Lévy飛行軌跡(從原點(diǎn)(0,0)開(kāi)始，標(biāo)記為□)

在文獻(xiàn)[15]中，Lévy飛行的隨機(jī)步長(zhǎng)s，計(jì)算公式如下：

(18)

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

(19)

其中，

(20)

2.2 LWDO算法

2.2.1 LWDO算法思想

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

(21)

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

2.2.2 LWDO算法流程

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

圖2 LWDO算法流程

3 仿真實(shí)驗(yàn)與性能分析

3.1 實(shí)驗(yàn)設(shè)計(jì)與測(cè)試函數(shù)

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

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

算法的參數(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 測(cè)試函數(shù)

3.2 實(shí)驗(yàn)結(jié)果和性能分析

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

在f5、f6、f7、f8四個(gè)多峰函數(shù)上，LWDO算法的平均值和標(biāo)準(zhǔn)差均為0，說(shuō)明LWDO算法50次仿真實(shí)驗(yàn)均能收斂到四個(gè)函數(shù)的理論極值，尋優(yōu)性能較好；WDO、AWDO、GWDO三種算法在f7、f8函數(shù)上的平均值和標(biāo)準(zhǔn)差均為0，說(shuō)明與LWDO算法一樣，50次仿真實(shí)驗(yàn)均能收斂到這兩個(gè)函數(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兩個(gè)旋轉(zhuǎn)函數(shù)上，LWDO算法的平均值和標(biāo)準(zhǔn)差均為0，說(shuō)明50次實(shí)驗(yàn)均能收斂到函數(shù)的理論極值，尋優(yōu)性能明顯優(yōu)于其他6種對(duì)比算法。

表2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

[參考文獻(xiàn)]

[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ū)動(dòng)優(yōu)化算法WDO的PID參數(shù)優(yōu)化[J].計(jì)算機(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ū)動(dòng)算法的鍋爐NO_x排放模型優(yōu)化[J].動(dòng)力工程學(xué)報(bào),2016(9):732-738.

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

[6]費(fèi)曉,張貞凱,田雨波,等.風(fēng)驅(qū)動(dòng)優(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ū)動(dòng)算法的機(jī)會(huì)陣?yán)走_(dá)波束圖綜合[J].江蘇科技大學(xué)學(xué)報(bào):自然科學(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é)報(bào):工學(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.