風驅(qū)動優(yōu)化算法

任作琳，張儒劍，田雨波

(1.江蘇科技大學電子信息學院，江蘇鎮(zhèn)江212003)(2.南京郵電大學海外教育學院，江蘇南京210046)

智能優(yōu)化算法具有全局的、并行高效的優(yōu)化性能、魯棒性、通用性強、無需問題特殊信息等優(yōu)點，已經(jīng)被廣泛應(yīng)用于計算機科學、優(yōu)化調(diào)度、運輸問題、組合優(yōu)化、工程優(yōu)化設(shè)計等眾多領(lǐng)域，并引起了國內(nèi)外學者的廣泛關(guān)注［1］.美國賓夕法尼亞州立大學電氣工程系的Bayraktar Z和Werner D H博士以及氣象學系的 Komurcu M博士在2010年IEEE Antennas and Propagation Society International Symposium上發(fā)表了名為“Wind Driven Optimization(WDO):A novel nature-inspired optimization algorithm and its application to electromagnetic”的論文［2］，標志著風驅(qū)動優(yōu)化 (WDO)算法的誕生.

風驅(qū)動優(yōu)化算法是一種基于群體的迭代啟發(fā)式全局優(yōu)化算法，該算法是基于對簡化的空氣質(zhì)點受力運動模型的模擬.其核心是研究空氣質(zhì)點在大氣中的受力運動情況，應(yīng)用牛頓第二定律并結(jié)合理想氣體狀態(tài)方程，推導出空氣質(zhì)點在每一次迭代中的速度和位置的更新方程.該算法簡單，易于實現(xiàn)，可調(diào)參數(shù)較少，能夠有效跳出局部極值尋找到最優(yōu)極值，可以處理多模和多維問題，也可以處理連續(xù)優(yōu)化問題和離散優(yōu)化問題.

相比于其他智能優(yōu)化算法(如粒子群優(yōu)化算法)該算法更新方程具有實際的物理意義，其全局搜索能力較強，收斂速度較快，尋優(yōu)效率高，魯棒性強，且可以通過微調(diào)系數(shù)達到不同的優(yōu)化拓撲結(jié)構(gòu)，應(yīng)用前景十分廣泛.目前國內(nèi)剛剛開始關(guān)注WDO算法的研究，文中介紹了WDO算法的原理和目前的研究情況，進而給致力于研究WDO算法的研究者們提供一些借鑒.

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

1.1 算法物理基礎(chǔ)

大氣動力學是經(jīng)典力學中牛頓定律在地球大氣中的應(yīng)用，大氣運動和經(jīng)典流體力學的一個主要區(qū)別是:大氣運動是處于一個旋轉(zhuǎn)的地球表面上［3］.

眾所周知，牛頓定律是在一個無加速度的坐標系(即慣性坐標系)中處理質(zhì)點加速度與質(zhì)點所受作用力之間的關(guān)系.若將這些定律應(yīng)用于非慣性旋轉(zhuǎn)坐標系中，就必須做一些相應(yīng)的變化與調(diào)整.

在一個無加速度的慣性坐標系(或稱絕對坐標系)中，一個單位質(zhì)量氣塊運動的速度矢量以Va表示.按牛頓定律，它的加速度與所受到的力之間的關(guān)系可以表達為:

式中:下標a表示絕對坐標系，F(xiàn)i為作用在氣塊上的力.

首先分析式(1)左端項.由于大氣運動處于一個旋轉(zhuǎn)的地球表面上，其運動的速度和加速度，從絕對坐標系(例如在恒星上)觀察與從地球表面上觀察是不同的，前者稱為絕對速度和絕對加速度，后者稱為相對速度和相對加速度.

設(shè)地球的旋轉(zhuǎn)角速度為Ω，一個物體或空氣塊的絕對速度為Va，地球表面上觀察的相對速度為V，則它們之間的關(guān)系為:

式中r為氣塊的位置矢量，其大小為地心至氣塊重心的距離，方向由地心指向氣塊.式(2)可以表示為:

式中R為氣塊相對地球轉(zhuǎn)動軸的位置矢量.

下述表達式對所有矢量普遍成立:

式中A為某一矢量.將式(2)代入式(5):

式(6)中最后一個等號右邊第一項為相對于地球表面的加速度;第二項為科氏(Coriolis)加速度，只有當氣塊相對地表運動時(V≠0)才出現(xiàn);第三項為氣塊隨地球旋轉(zhuǎn)而具有的向心加速度，只與氣塊位置(矢量r)有關(guān)，與其是否相對運動無關(guān).

下面再分析式(1)右端項.在地球表面上，氣塊受到的力有:① 氣塊與地球之間的牛頓萬有引力，可表示為g*;② 由于氣壓空間分布差異引起的氣壓梯度力 －2p/ρ，ρ為空氣密度，p為空氣壓強;③由于空氣分子粘性引起的內(nèi)摩擦力ν22V，ν為運動分子的粘性系數(shù)，22為拉普拉斯算子.于是式(1)成為:

這是在旋轉(zhuǎn)地球上的坐標系即非慣性坐標系中，氣塊加速度與作用在其上作用力之間的關(guān)系，即非慣性坐標系中的牛頓第二定律.其右端前3項仍保持原來的含義;第4項稱為科氏力，在慣性坐標系中它本是物體的加速度，在非慣性坐標系中把它看成為力，所以稱其為虛擬力.科氏力與地球自轉(zhuǎn)軸垂直，并在北半球指向風矢量的右方.第5項也是虛擬力，稱其為離心力.由于這個力只與位置有關(guān)，不將其作為單獨的力看待，而是將其與引力項1合并，稱為重力，即

式(10)即是單位質(zhì)量氣塊加速度與作用在其上作用力之間的關(guān)系，亦即非慣性坐標系中的牛頓第二定律.

1.2 算法基本原理

地球大氣的成分和結(jié)構(gòu)是很復雜的，大氣的任一微小部分(空氣微團)可以作為“點”來處理，稱為空氣質(zhì)點［4］.根據(jù)以上得出非慣性坐標系中的牛頓第二定律并結(jié)合理想氣體狀態(tài)方程，可以簡化模型得出風驅(qū)動優(yōu)化算法.

1.2.1 速度更新方程

世界氣象組織(WMO)對于標準大氣的定義中有這樣的描述［2］:假定空氣服從使溫度、壓力和密度與位勢發(fā)生關(guān)系的理想氣體定律和流體靜力學方程.其中，大氣處于流體靜力平衡狀態(tài)是指大氣在垂直方向上受到重力和垂直氣壓梯度力的作用并達到平衡.在建模過程中，研究者并沒有完全模擬大氣運動，忽略了平流層離心力等微小影響的作用力，簡化了建模，主要考慮4個力作用，并且假設(shè)空氣質(zhì)點處于流體靜力平衡狀態(tài)，且滿足理想氣體定律(即理想氣體狀態(tài)方程).又由于地球自轉(zhuǎn)以及不同高度大氣對太陽輻射吸收程度的差異，使得大氣在水平方向比較均勻，而在垂直方向呈現(xiàn)明顯的層狀分布.所以，大氣運動中水平運動對空氣質(zhì)點的影響強于垂直運動，在研究WDO算法中，僅需關(guān)注風的水平運動.由于研究對象是無限小的空氣質(zhì)點，可以假設(shè)空氣質(zhì)點為單位體積.雖然研究大氣運動是在三維的世界里，但是算法應(yīng)用可以映射到解決多維的問題中.

簡化的牛頓第二定律及理想氣體定律方程式如下:

式中:a為加速度，ρ為空氣質(zhì)點的密度，F(xiàn)i為作用在空氣質(zhì)點上的力，P為壓強，R為理想氣體常數(shù)，T為溫度.

由大氣動力學知識可知，影響風吹動的主要力有4個，分別是:①啟動空氣質(zhì)點運動的氣壓梯度力FPG，其方向由高壓區(qū)指向低壓區(qū);②與FPG作用相反的摩擦力FF;需要指出的是，由于摩擦力的方程式較復雜，故在推導速度更新方程時應(yīng)用另一種簡化的表達方式;③ 垂直指向地心的重力FG，在物理學三維坐標系中假設(shè)地球的中心為直角坐標系的中心，那么可以認為重力是使空氣質(zhì)點移向坐標系原點的力，相似的將三維問題映射到N維中，重力代表指向坐標系中心的力;④ 地球旋轉(zhuǎn)產(chǎn)生的科氏力Fc，它代表在每一次迭代中，空氣質(zhì)點當前所在維度中的速度和位置受其他任一維度的影響.4個力具體簡化方程如下:

式中:－2P為氣壓梯度，負號說明沿梯度下降方向;δV為空氣粒子的有限體積;α為摩擦系數(shù)，u為風速度矢量，g為重力加速度矢量，Ω為地球旋轉(zhuǎn)角速度矢量.

由于研究對象為無限小的空氣質(zhì)點，為了簡化模型令δV=1，同時為了便于公式的推導，假定Δt=1，得到式(18):

將式(12)代入式(18)得到:

式中Pcur為當前位置空氣質(zhì)點的壓力數(shù)值，將式(19)左右兩邊同時除以，得到:

在風驅(qū)動優(yōu)化算法中，空氣質(zhì)點速度和位置的每一次迭代都會發(fā)生改變，來探索新的搜索空間.因此，速度變量可以表示為Δu=unew－ucur，其中ucur為當前迭代中空氣質(zhì)點的速度，unew為下一次迭代中空氣質(zhì)點的速度.式(14)中，摩擦力的計算應(yīng)用的是當前迭代速度值ucur，那么式(20)可以改寫為:

根據(jù)重力定義，在一維坐標系［－1，1］范圍中(圖1a))表示空氣質(zhì)點的重力FG，則矢量g可以表示為g=|g|(0－xcur).

相似的由圖1b)，F(xiàn)PG方向為空氣質(zhì)點從高壓區(qū)指向低壓區(qū)，即從當前位置指向最優(yōu)壓力點，那么 －2P可以表示為－2P=|Popt－Pcur|(xoptxcur)，Pcur為空氣質(zhì)點當前位置的壓力值，Popt為種群中目前為止找到的最優(yōu)壓力值，xcur為當前位置，xopt為最優(yōu)位置.式(21)中g(shù)和 －2P可以認為是由矢量圖(圖1a)和b))表示的兩個矢量，并非物理定義的表達式，這樣做的目的是為了簡化方程，將式(21)中g(shù)和－2P寫成標量與方向乘積形式，那么可以改寫為:

圖1 一維坐標系中重力和氣壓梯度力Fig.1 Illustration of the gravitational force and the pressure gradient force in a one dimensional coordinate system

由科氏力Fc定義可知，它代表在每一次迭代中，空氣質(zhì)點當前所在維度中的速度受其他任一維度的影響，這個速度用uoctuhrerdim來表示.文獻［2］為了簡化方程定義設(shè)置了常數(shù)c=－2|Ω|RT，使得式(22)可以表示為:

文獻［2］中用式(23)作為速度更新方程，會因為引入壓力值(Pcur和Popt)而使更新后的速度變得非常大，從而降低WDO算法的可操作性.相對于式(23)中使用的真實壓力值，可以用i表示在所有空氣質(zhì)點中的一個降序排列，用來替換式子中的壓力值(Pcur和Popt)，而在xopt最優(yōu)位置時壓力值最小，可設(shè)為1，那么式(23)可以改寫為:

綜上所述，式(24)為最后改進的速度更新方程，第一項表示在沒有其它力作用在空氣質(zhì)點上時，摩擦力會使其速度在原路徑上減小.可以使用固定的摩擦系數(shù)α，也可根據(jù)具體問題選擇自適應(yīng)的摩擦系數(shù)α，實驗證明α一般取［0.8，0.9］.第二項表示空氣質(zhì)點從當前位置按常數(shù)g成比例向坐標系中心靠近，實驗證明其取值范圍為［0.6，0.7］.由于重力的存在，一定程度上避免了空氣質(zhì)點困在或跳出搜索邊界，提高了全局搜索能力，加快了收斂速度.第三項促使空氣質(zhì)點移向最大壓力點即全局最優(yōu)位置，一般系數(shù)RT在［1.0，2.0］范圍內(nèi).第四項模擬了科氏力，提供了其它維對當前維內(nèi)空氣質(zhì)點速度的影響，增強了算法的魯棒性，一般認為c取［0.05，3.6］.

1.2.2 位置更新方程

WDO算法是基于大氣中空氣質(zhì)點運動的優(yōu)化方法，每一次迭代過程中都要更新空氣質(zhì)點的速度和位置.已知速度更新方程式(24)，不難得出位置更新方程如下:假設(shè)時間間隔為Δt=1.

對于每一維中的空氣質(zhì)點，其搜索位置范圍可以根據(jù)具體問題進行設(shè)定，其更新速度也具有一定的范圍，可以簡單將速度值大小作如下判斷:

式中umax為速度邊界值.

1.3 算法流程

為了描述方便清晰，表1列出了風驅(qū)動優(yōu)化算法中用到的各個術(shù)語.

表1 風驅(qū)動優(yōu)化算法相關(guān)術(shù)語及其描述Table 1 Terminologies used in the wind driven optimization algorithm and its descriptions

風驅(qū)動優(yōu)化算法的流程如下:

1)初始化群體規(guī)模，設(shè)置最大迭代次數(shù)，相關(guān)參數(shù)(α，g，RT，c)，搜索邊界以及定義壓力函數(shù)(即適值函數(shù));

2)隨機初始化空氣質(zhì)點，隨機分配起始速度和位置;

3)計算當前迭代中空氣質(zhì)點的壓力值(適值)，并按照壓力值將種群重新排列;

4)通過式(24)更新空氣質(zhì)點的速度;

5)通過式(25)更新空氣質(zhì)點的位置;

6)若未達到終止條件，則轉(zhuǎn)3).

最后一次迭代過程中的壓力值被記為最優(yōu)結(jié)果.一般將終止條件設(shè)定為一個足夠好的壓力值(適應(yīng)值)或達到一個預設(shè)的最大迭代代數(shù).圖2為風驅(qū)動優(yōu)化算法流程.

圖2 風驅(qū)動優(yōu)化算法流程Fig.2 Flowchart of the wind driven optimization algorithm

2 算法應(yīng)用

風驅(qū)動優(yōu)化算法是一種新型的全局優(yōu)化算法，具有較強的魯棒性，尋優(yōu)效率高，既可以解決離散優(yōu)化問題又可以解決連續(xù)優(yōu)化問題.

2.1 WDO算法在電磁學問題中的應(yīng)用

電磁優(yōu)化問題大多都是非線性、多極值和不可微的復雜問題，一般的優(yōu)化方法難以達到全局最優(yōu)［4］.WDO算法因具有較強的全局搜索能力，并且可以處理離散優(yōu)化問題，故可用于優(yōu)化設(shè)計電磁學中的問題，目前主要解決三大類問題:天線陣綜合問題，微帶天線設(shè)計問題以及吸波材料設(shè)計問題.文獻［5］中WDO算法研究了線性天線陣綜合問題，并將WDO算法與粒子群算法(particle swarm optimization，PSO)、綜合學習粒子群算法(comprehensive learning POS，CLPSO)作了比較，實驗證明WDO算法的優(yōu)化效果優(yōu)于PSO算法和較復雜的CLPSO算法，更加證實了WDO算法的簡單易行且高效的特性.文獻［6］中應(yīng)用WDO算法設(shè)計了兩種微帶天線，分別是E形微帶貼片天線和加載短截線的倒F天線［7］.兩個應(yīng)用都證明了WDO算法針對設(shè)計和解決復雜的電磁學問題是一種高效的優(yōu)化工具.在吸波材料設(shè)計問題上，文獻［2，5，8］應(yīng)用WDO算法設(shè)計了用于WiFi使用的復雜的雙面人工磁導體表面材料(double-sided artificial magnetic conducting，DSAMC)，并與應(yīng)用遺傳算法(genetic algorthm，GA)算法設(shè)計的DSAMC作了比較，實驗結(jié)果突出了WDO算法在電磁優(yōu)化問題上的優(yōu)越性，證明了WDO算法可以很好的解決離散優(yōu)化問題.

2.2 WDO算法在圖像處理問題中的應(yīng)用

在圖像處理方面，WDO算法也表現(xiàn)出了其強大的計算能力以及高效尋優(yōu)的特性.圖像分割技術(shù)是將圖像分割成具有相似特性區(qū)域的過程，它是圖像分析應(yīng)用于模式識別和目標檢測的領(lǐng)域中的一個重要步驟［9］.在衛(wèi)星圖像分割問題中，由于衛(wèi)星圖像的數(shù)據(jù)量大、特征信息豐富、背景復雜，使得精確分割衛(wèi)星遙感圖像是一項極具有挑戰(zhàn)的任務(wù).若想高效準確的找出圖像分割合適的閾值就不得不進行大量的計算，而傳統(tǒng)的優(yōu)化方法表現(xiàn)出了局限性.文獻［10］應(yīng)用WDO算法基于卡普爾熵尋找衛(wèi)星圖像分割中的多層次閾值，實驗證明WDO算法對于解決多層次閾值優(yōu)化問題是十分合適且高效準確的，為WDO算法在圖像處理領(lǐng)域的應(yīng)用提出了一些方向，比如衛(wèi)星圖像增強，衛(wèi)星圖像分類以及其他衛(wèi)星圖像應(yīng)用等.

2.3 WDO算法在其他問題中的應(yīng)用

云計算是并行計算、分布式計算和虛擬技術(shù)相結(jié)合的產(chǎn)物，是當前計算機行業(yè)的技術(shù)熱點，任務(wù)調(diào)度是云計算的核心技術(shù)之一，對云計算系統(tǒng)整體性能影響很大［11］.文獻［12］基于微觀經(jīng)濟學和WDO算法對云資源調(diào)度分配方案進行了設(shè)計，其應(yīng)用WDO算法與GA算法結(jié)合法對云資源分配進行優(yōu)化，在每一次迭代中，選擇出最優(yōu)個體，其余候選解依據(jù)Metropolis準則進行交叉、高斯變異操作，最后將進行過GA操作的候選解與最優(yōu)個體整合得到當前迭代結(jié)果.實驗結(jié)果表明，WDO算法的全局搜索能力較強.

3 總結(jié)與展望

風驅(qū)動優(yōu)化算法是一種新近提出的全局群智能優(yōu)化算法，該算法具有簡單易實現(xiàn)、搜索效率高、收斂速度快等優(yōu)點，文中對算法物理原理以及算法基本原理做出了詳盡的介紹，并將近幾年來國內(nèi)外對該算法的應(yīng)用研究進行了細致闡述.

目前該算法研究正處于起步和發(fā)展階段，隨著研究的深入，WDO算法必將在理論和實踐應(yīng)用上取得新的突破，現(xiàn)對其未來研究提出幾點展望:

在算法理論研究方面:①算法的收斂性研究.對于任何優(yōu)化算法，收斂性都是一個基本的研究問題，目前風驅(qū)動算法還缺少收斂性的理論研究.②算法關(guān)鍵參數(shù)的研究.目前算法參數(shù)的選擇大多依據(jù)經(jīng)驗值選取，一些論文中給出了參數(shù)的選取范圍，但針對不同問題，參數(shù)選取的不合適，則會大大影響尋優(yōu)結(jié)果.如何根據(jù)具體問題，自適應(yīng)地選取這些關(guān)鍵參數(shù)將是一個值得深入研究的內(nèi)容.③算法與其他算法或技術(shù)的結(jié)合.為了不斷完善風驅(qū)動優(yōu)化算法的性能，增強其對不同問題研究的針對性，可以將其與成熟的智能優(yōu)化算法或技術(shù)相結(jié)合，增強算法的尋優(yōu)效率，同時也推進了對風驅(qū)動優(yōu)化算法的研究.

在算法實踐應(yīng)用研究方面:開辟風驅(qū)動優(yōu)化算法新的應(yīng)用領(lǐng)域.與其他算法一樣，應(yīng)用是檢驗算法優(yōu)劣的標準，是算法研究的價值體現(xiàn).雖然WDO算法在電磁學領(lǐng)域應(yīng)用廣泛，但其在更豐富的工程應(yīng)用中還未取得和其他智能算法一樣的地位，研究該方法更廣泛的實際應(yīng)用將有著十分重要的意義.

References)

［1］ 劉瓊.智能優(yōu)化算法及其應(yīng)用研究［D］.江蘇無錫:江南大學，2011.

［2］ Bayraktar Z，Komurcu M，Werner D H.Wind driven optimization(WDO):a novel nature-inspired optimization algorithm and its application to electromagnetics［C］∥Antennas and Propagation Society International Symposium(APSURSI)，2010 IEEE，2010:1-4.

［3］ 盛裴軒，毛節(jié)泰，李建國，等.大氣物理學［M］.北京:北京大學出版社，2003:30-48，168-169.

［4］ 高強，閆敦豹，袁乃昌.一種基于遺傳算法的AMC結(jié)構(gòu)設(shè)計［J］.電子學報，2006，34(9):1686-1689.Gao Qiang，Yan Dunbao，Yuan Naichang.A genetic-algorithm-based AMC structure［J］.Acta Electronica Sinica，2006，34(9):1686-1689.(in Chinese)

［5］ 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，61(5):2745-2757.

［6］ 劉式適，劉式達.大氣動力學(上)［M］.北京:北京大學出版社，2011:1-10.

［7］ Bayraktar Z，Komurcu M，Jiang Z H，et al.Stubloaded inverted-F antenna synthesis via wind driven optimization［C］∥ Antennas and Propagation(APSURS.l.)，2011 IEEE International Symposium on IEEE.［S.l.］:IEEE，2011:2920-2923.

［8］ Bayraktar Z，Turpin J P，Werner D H.Nature-inspired optimization of high-impedance metasurfaces with ultrasmall interwoven unit cells［J］.Antennas and Wireless Propagation Letters，IEEE，2011，10:1563-1566.

［9］ 丁知平.基于混合智能算法的衛(wèi)星圖像分割技術(shù)研究［J］.計算機測量與控制，2012，20(5):1420-1422.Ding Zhiping.Satellite image segmentation based on hybrid intelligent algorithms［J］.Computer Measurement＆ Control，2012，20(5):1420-1422.(in Chinese)

［10］ Bhandari A K，Singh V K，Kumar A，et al.Cuckoo search algorithm and wind driven optimization based study of satellite image segmentation for multilevel thresholding using Kapur′s entropy［J］.Expert Systems with Applications，2014，41(7):3538-3560.

［11］ 陳海燕.基于多群智能算法的云計算任務(wù)調(diào)度策略［J］.計算機科學，2014，41(6A):83-86.Chen Haiyan.Task scheduling in cloud computing based on swarm intelligent algorithms［J］.Computer Science，2014，41(6A):83-86.(in Chinese)

［12］ Sun J，Wang X，Huang M，et al.A cloud resource allocation scheme based on microeconomics and wind driven optimization［C］∥ChinaGrid Annual Conference(ChinaGrid)，2013 8th IEEE.［S.l.］:IEEE，2013:34-39.