風驅動優化算法

任作琳，張儒劍，田雨波

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

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

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

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

1 風驅動優化算法

1.1 算法物理基礎

大氣動力學是經典力學中牛頓定律在地球大氣中的應用，大氣運動和經典流體力學的一個主要區別是:大氣運動是處于一個旋轉的地球表面上［3］.

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

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

式中:下標a表示絕對坐標系，Fi為作用在氣塊上的力.

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

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

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

式中R為氣塊相對地球轉動軸的位置矢量.

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

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

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

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

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

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

1.2 算法基本原理

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

1.2.1 速度更新方程

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

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

式中:a為加速度，ρ為空氣質點的密度，Fi為作用在空氣質點上的力，P為壓強，R為理想氣體常數，T為溫度.

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

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

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

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

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

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

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

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

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

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

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

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

1.2.2 位置更新方程

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

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

式中umax為速度邊界值.

1.3 算法流程

為了描述方便清晰，表1列出了風驅動優化算法中用到的各個術語.

表1 風驅動優化算法相關術語及其描述Table 1 Terminologies used in the wind driven optimization algorithm and its descriptions

風驅動優化算法的流程如下:

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

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

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

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

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

6)若未達到終止條件，則轉3).

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

圖2 風驅動優化算法流程Fig.2 Flowchart of the wind driven optimization algorithm

2 算法應用

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

2.1 WDO算法在電磁學問題中的應用

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

2.2 WDO算法在圖像處理問題中的應用

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

2.3 WDO算法在其他問題中的應用

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

3 總結與展望

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

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

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

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

References)

［1］ 劉瓊.智能優化算法及其應用研究［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］ 盛裴軒，毛節泰，李建國，等.大氣物理學［M］.北京:北京大學出版社，2003:30-48，168-169.

［4］ 高強，閆敦豹，袁乃昌.一種基于遺傳算法的AMC結構設計［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］ 丁知平.基于混合智能算法的衛星圖像分割技術研究［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］ 陳海燕.基于多群智能算法的云計算任務調度策略［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.