朱祥兵 李垣江，2 王建華 武漢卿

（1.江蘇科技大學(xué)電子信息學(xué)院 鎮(zhèn)江 212003）（2.毫米波國家重點(diǎn)實(shí)驗(yàn) 南京 210096）

1 引言

風(fēng)驅(qū)動(dòng)優(yōu)化（Wind Driven Optimization，WDO）算法是在2010年由Zikri Bayraktar博士等提出的一種基于種群的全局優(yōu)化算法［1］。該算法對空氣質(zhì)點(diǎn)受力情況進(jìn)行模擬，研究質(zhì)點(diǎn)在地球大氣層內(nèi)的運(yùn)動(dòng)狀況，同時(shí)根據(jù)牛頓第二定律（F=ma）和理想氣體定律（pV=nRT），可以推導(dǎo)求出空氣質(zhì)點(diǎn)的速度和位置更新方程。近幾年，風(fēng)驅(qū)動(dòng)優(yōu)化算法已經(jīng)成功應(yīng)用于許多領(lǐng)域，例如電磁優(yōu)化領(lǐng)域［2］、圖像處理［3］、云資源調(diào)度分配［4］、層次規(guī)劃［5］等。

傳統(tǒng)的風(fēng)驅(qū)動(dòng)算法跟其他智能優(yōu)化算法一樣，容易陷入局部最優(yōu)極值，特別是在多峰函數(shù)優(yōu)化時(shí)，無法從局部最優(yōu)值中跳出，無法獲得理想的全局最優(yōu)效果。與其他智能算法類似，風(fēng)驅(qū)動(dòng)算法的改進(jìn)策略集中在種群的多樣性、變異性［6］及尋優(yōu)策略等方面。文獻(xiàn)［7］提出了五種不同的變異機(jī)制（小波變異策略、混沌變異策略、非均勻變異策略、高斯變異策略以及柯西變異策略），并與粒子群算法對比分析風(fēng)驅(qū)動(dòng)優(yōu)化算法的優(yōu)化能力，實(shí)驗(yàn)結(jié)果表明，小波變異風(fēng)驅(qū)動(dòng)優(yōu)化（Wind Driven Optimiza?tion with Wavelet Mutation，WDOWM）算法具有較強(qiáng)的尋優(yōu)能力，可有效跳出局部最優(yōu)，其尋優(yōu)速率、收斂精度及算法穩(wěn)定性均優(yōu)于粒子群優(yōu)化算法、風(fēng)驅(qū)動(dòng)優(yōu)化算法和其他改進(jìn)算法，但其全局搜索能力仍然有提高的可能。

本文針對上述的風(fēng)驅(qū)動(dòng)優(yōu)化算法易陷入局部最優(yōu)、早熟收斂的問題，在優(yōu)化過程中有條件的引入 Levy飛行機(jī)制［8～9］更新質(zhì)點(diǎn)位置，提高空氣質(zhì)點(diǎn)的搜索范圍和種群多樣性，增強(qiáng)其跳出局部最優(yōu)的能力，從而實(shí)現(xiàn)算法的全局優(yōu)化。

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

2.1 算法介紹

風(fēng)驅(qū)動(dòng)優(yōu)化算法是以地球大氣中的任一空氣質(zhì)點(diǎn)為研究對象提出的［10］。根據(jù)非慣性坐標(biāo)系中牛頓第二定律并結(jié)合理想氣體狀態(tài)方程，可以簡化模型得出WDO算法［1］。算法中主要考慮4個(gè)力的作用：由高壓指向低壓的氣壓梯度力、與氣壓梯度力發(fā)作用的摩擦力、指向地心的重力和地球旋轉(zhuǎn)引起的科氏力［7］。質(zhì)點(diǎn)的壓力值是對空氣質(zhì)點(diǎn)位置的評價(jià)，與其他優(yōu)化算法中的自適應(yīng)值類似，一般由目標(biāo)函數(shù)迭代計(jì)算得到。

設(shè)M個(gè)空氣質(zhì)點(diǎn)存在于N維中，那么第i個(gè)空氣質(zhì)點(diǎn)的位置信息表達(dá)式為

在WDO算法中，空氣質(zhì)點(diǎn)的受力主要由摩擦力，重力，氣壓梯度力和科氏力組成。式（3）中第一部分代表了空氣質(zhì)點(diǎn)受摩擦力影響，其系數(shù)常量a的權(quán)重決定對當(dāng)前質(zhì)點(diǎn)的速度繼承值，根據(jù)經(jīng)驗(yàn)(1-a)不應(yīng)該超過0.3，正常情況下?。?.8，0.9］。第二部分是重力對質(zhì)點(diǎn)的影響，是質(zhì)點(diǎn)對自身當(dāng)前位置的判斷，有助于質(zhì)點(diǎn)跳出邊界和局部最優(yōu)值，系數(shù)g的取值范圍［0.6，0.7］。第三部分是氣壓梯度力對質(zhì)點(diǎn)的影響，它是一個(gè)改進(jìn)自身位置的過程，初始自己向全局最優(yōu)位置移動(dòng)，RT的取值范圍在［1，2］。最后一部分是科氏力對質(zhì)點(diǎn)的影響，將同一指點(diǎn)的其他維度的速度信息借鑒過來，調(diào)整自身的速度信息，增強(qiáng)算法的魯棒性，提高算法性能，系數(shù)c的取值范圍在0.05～3.6 之間［1］。

2.2 算法過程

WDO算法的實(shí)現(xiàn)流程：

1）初始化空氣質(zhì)點(diǎn)的個(gè)數(shù)和維度，定義最大迭代次數(shù)和相關(guān)的參數(shù)常量，設(shè)置搜索邊界（位置和速度），設(shè)置相應(yīng)的測試函數(shù)。

2）隨機(jī)初始化各個(gè)質(zhì)點(diǎn)的初始信息（位置和速度），計(jì)算初始的壓力值并根據(jù)壓力值的大小升序排列。

3）開始迭代。更新空氣質(zhì)點(diǎn)的速度和位置，計(jì)算質(zhì)點(diǎn)壓力值并以升序方式重新排列種群順序。

4）迭代終止。判斷是否滿足終止條件，如果不滿足就返回步驟3），否則就終止迭代，最后搜索到的最優(yōu)位置就是最優(yōu)解。

3 Levy飛行

自然界中很多動(dòng)物想要在不確定的環(huán)境中找到食物，最理想的方式就是采用“Levy飛行”搜索策略，在這種形式的搜索中，短距離的探索性蹦蹦跳跳與偶爾的較長距離行走相間［8］。短距離的行走習(xí)慣可以確保動(dòng)物在對自身周邊的環(huán)境探索的比較仔細(xì)，偶爾的長距離行走可以讓動(dòng)物進(jìn)入其他環(huán)境進(jìn)行探索，進(jìn)入更廣闊的環(huán)境范圍。目前，Levy飛行已經(jīng)被運(yùn)用于優(yōu)化領(lǐng)域，比如布谷鳥算法中就用萊維飛行進(jìn)行位置更新［9］。同時(shí)，許多成熟的優(yōu)化算法也借鑒了Levy飛行機(jī)制，改進(jìn)算法的性能，從而取得了更好的效果［11］。在智能優(yōu)化算法中使用Levy飛行能擴(kuò)大搜索范圍，增加種群多樣性，更容易跳出局部最優(yōu)值。

使用Levy飛行機(jī)制的位置更新方程為［12］

其中：?代表了步長控制量；⊕表示點(diǎn)對點(diǎn)乘法，Levy(β)代表萊維隨機(jī)搜索路徑，同時(shí)?和Levy(β)需要滿足下列條件：

因?yàn)長evy飛行的步長滿足一個(gè)重尾的概率分布，在用算法編碼方面比較復(fù)雜，難以實(shí)現(xiàn)。所以我們通過Mantegna提出的Mantegna算法來模擬出Levy飛行路徑的步長計(jì)算公式［13］：

式中：s代表了Levy隨機(jī)搜索路徑Levy(β)；β的取值范圍在［0，2］，通常取 1.5；μ、v是服從式（8）的正態(tài)分布隨機(jī)數(shù)：

其中，σμ，σv代表了符合正態(tài)分布的標(biāo)準(zhǔn)差，它們的取值滿足式（9）：

如此就可以模擬出Levy飛行的搜索路徑。

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

4.1 算法思想

從WDO算法中，第t次迭代所獲得的較好的質(zhì)點(diǎn)的位置信息可以表示為（i=1，2，…，M），LW?DO算法通過一個(gè)均勻隨機(jī)數(shù)來確定是否需要Levy飛行進(jìn)來優(yōu)化位置信息。

當(dāng)空氣質(zhì)點(diǎn)在迭代過程中，其速度和位置信息初步更新完畢后，通過隨機(jī)生成的［0，1］之間的均勻隨機(jī)數(shù)rand來與飛行概率控制變(Levy flight probability,lp)∈[0,1]進(jìn)行比較，如果小于lp則剛剛更新的位置信息通過式以下飛行公式繼續(xù)優(yōu)化：

4.2 算法步驟

1）初始化空氣質(zhì)點(diǎn)的個(gè)數(shù)和維度，定義最大迭代次數(shù)和相關(guān)的參數(shù)常量，設(shè)置搜索邊界（位置和速度），設(shè)置相應(yīng)的測試函數(shù)。

2）隨機(jī)初始化各個(gè)質(zhì)點(diǎn)的初始信息（位置和速度），計(jì)算初始的壓力值并根據(jù)壓力值的大小升序排列。

3）開始迭代，更新空氣質(zhì)點(diǎn)的速度和位置信息，判斷速度和位置是否越界，如越界做相應(yīng)的修正。

4）均勻隨機(jī)數(shù)rand與飛行概率比較lp，如果rand＞lp，執(zhí)行步驟 6），否則執(zhí)行步驟5）。

5）Levy飛行。通過式（4）開始繼續(xù)對位置信息進(jìn)行優(yōu)化，判斷位置是否越界，如越界做相應(yīng)的修正。計(jì)算空氣質(zhì)點(diǎn)的個(gè)體壓力值并根據(jù)壓力值的大小做升序排列，更新種群全局最優(yōu)值glob?al_best。

6）迭代終止。判斷是否滿足終止條件，如果不滿足迭代終止。判斷是否滿足終止條件，如果不滿足就返回步驟3），否則就終止迭代，最后搜索到的最優(yōu)位置就是最優(yōu)解。

LWDO算法的流程圖如圖1所示。

圖1 基于Levy飛行機(jī)制的風(fēng)驅(qū)動(dòng)優(yōu)化算法流程圖

5 測試仿真

為了測試基于風(fēng)驅(qū)動(dòng)優(yōu)化算法（LWDO）的整體性能，將通過Matlab對原始WDO算法、小波變異風(fēng)驅(qū)動(dòng)優(yōu)化算法、本文改進(jìn)算法進(jìn)行對比分析，從而驗(yàn)證算法的有效性。實(shí)驗(yàn)的測試環(huán)境建立在In?tel（R）Core（TM）i5-2450M CPU@2.50GHz、內(nèi)存4GB、Windows7操作系統(tǒng)的計(jì)算機(jī)上，其仿真測試軟件為Matlab 2010.b。

如表1所示，本文采用7個(gè)比較經(jīng)典的測試函數(shù)。這些測試函數(shù)中 f1～f4代表著單峰函數(shù)，其中Sphere函數(shù)較為簡單，用來測試算法的尋優(yōu)效果；Rosenbrock函數(shù)是一個(gè)經(jīng)典且復(fù)雜的優(yōu)化測試函數(shù)，其全局最優(yōu)值位于一條連續(xù)的好似長且窄的拋物形態(tài)的山谷內(nèi)，正常較難以找到全局最優(yōu)值，常用它來測試算法的執(zhí)行效率；Quadratic和Schwefel函數(shù)常被用作檢驗(yàn)算法的性能。 f5～f7代表著多峰函數(shù)，其中Rastrigin函數(shù)Griewank函數(shù)類似，都含有較多的局部極小值，常被用來測試算法的尋優(yōu)效果；Ackley函數(shù)提供了一個(gè)余弦函數(shù)來控制指數(shù)函數(shù)，局部最優(yōu)值眾多。

表1 測試函數(shù)簡介

5.1 實(shí)驗(yàn)參數(shù)設(shè)置

在實(shí)驗(yàn)過程中，各個(gè)算法的種群個(gè)數(shù)M設(shè)置為30，空氣質(zhì)點(diǎn)的維度分別選取10、30，最大的迭代次數(shù)設(shè)置為200，測試函數(shù)的相應(yīng)搜索范圍如表1所示，搜索速度的范圍對應(yīng)于位置搜索范圍的百分之一。在標(biāo)準(zhǔn)WDO算法中，常量參數(shù)a=0.7，g=0.4，RT=2，c=0.2；LWDO算法中飛行概率主要控制算法前50次迭代過程中尋優(yōu)曲線的振蕩程度，其數(shù)值越小，曲線越平穩(wěn)，在這里取lp=0.2，?0=1，β=1.5；WDOWM算法中，變異概率pm的值與飛行概率相同，取值為0.2；其他參數(shù)如ξwm=0.5，gwm=1000［5］。

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

實(shí)驗(yàn)中，3種待測算法的初始化過程相同。采用上述7個(gè)測試函數(shù)分別對算法的性能進(jìn)行測試，其獨(dú)立運(yùn)行次數(shù)為30。最后采用最優(yōu)壓力值（Best Pressure，BP）、平均最優(yōu)壓力值（Mean Best Pressure，MBP）、標(biāo)準(zhǔn)差（Standard Deviation，SD）和平均迭代次數(shù)來評價(jià)算法的性能。其中BP和MBP體現(xiàn)了算法的尋優(yōu)精度，SD代表了算法的穩(wěn)定性，平均迭代次數(shù)表示算法的尋優(yōu)效率。

圖2是WDO、LWDO、WDOWM對不同測試函數(shù)優(yōu)化30次的平均最優(yōu)壓力值的曲線，空氣質(zhì)點(diǎn)的維度分別取10和30。表2是對最優(yōu)壓力值、平均最優(yōu)壓力值、標(biāo)準(zhǔn)差的對比結(jié)果。表3是對各個(gè)算法的迭代次數(shù)的統(tǒng)計(jì)分析。

根據(jù)以上的仿真數(shù)據(jù)可以總結(jié)出以下結(jié)論：

1）由表2的最優(yōu)壓力值和平均最優(yōu)壓力值和表3的迭代次數(shù)可以看出，對于單峰函數(shù)來說，LW?DO算法和WDOWM算法比較優(yōu)秀，在尋優(yōu)精度上至少領(lǐng)先WDO算法5個(gè)數(shù)兩級，總的來說LWDO的尋優(yōu)精度比WDOWM好。而且在多峰函數(shù)上，LWDO算法的尋優(yōu)效率遠(yuǎn)遠(yuǎn)大于WDOWM和WDO算法，總是領(lǐng)先其他算法20次迭代以上。

2）根據(jù)表2中標(biāo)準(zhǔn)差數(shù)據(jù)可以判斷出算法的穩(wěn)定性能，標(biāo)準(zhǔn)差越小代表穩(wěn)定性越高，根據(jù)表中粗體數(shù)據(jù)可知：LWDO的算法穩(wěn)定性最好，WDO算法的穩(wěn)定性最差。

圖2 3種不同WDO算法優(yōu)化測試函數(shù)的平均最優(yōu)壓力值曲線

3）圖2中，LWDO比其他WDO算法具有更加快速的尋優(yōu)速率，得到較為滿意的結(jié)果。在相同迭代次數(shù)情況下，對 f1、f4、f5、f6、f7的兩種不同維度的仿真結(jié)果，實(shí)現(xiàn)Levy飛行機(jī)制的LWDO算法在任一迭代中都取得較好的結(jié)果。

4）由圖2可知，在對 f1、f2、f3、f4的計(jì)算中，LWDO和WDOWM算法的運(yùn)算量相近似，比WDO算法的運(yùn)算量略大，但得到較大尋優(yōu)精度的提升；而對 f5、f6、f7的優(yōu)化過程中，LWDO和WDOWM在運(yùn)算前期比WDO的運(yùn)算量略大，但其獲得理論最優(yōu)解的速度遠(yuǎn)超WDO，特別是LWDO只需要將近一半的迭代次數(shù)，大大提高了運(yùn)算速度。

5）結(jié)合圖2、表2和表3的信息，可以對下面這3種不同算法的尋優(yōu)性能作出如下判斷：LWDO＞W(wǎng)DOWM＞W(wǎng)DO。無論是從算法的尋優(yōu)精度、尋優(yōu)效率和穩(wěn)定性來看，LWDO算法均有良好的表現(xiàn)，極具應(yīng)用價(jià)值。

表2 仿真數(shù)據(jù)比較

表3 迭代次數(shù)比較

6 結(jié)語

本文提出一種基于Levy飛行機(jī)制的風(fēng)驅(qū)動(dòng)優(yōu)化算法（LWDO）。該算法在空氣質(zhì)點(diǎn)初步位置更新完成后通過飛行概率選擇性的對質(zhì)點(diǎn)進(jìn)行Levy飛行，提高風(fēng)驅(qū)動(dòng)算法的種群多樣性和全局搜索能力。從對標(biāo)準(zhǔn)測試函數(shù)的仿真實(shí)驗(yàn)可以看出，本文提出的LWDO算法有著較優(yōu)的收斂精度和收斂速度，不僅提高了算法跳出局部最優(yōu)的能力，還增強(qiáng)了算法的穩(wěn)定性，具有較好的應(yīng)用價(jià)值。