唐 煜 曹小鵬 張 瑩(西安郵電大學計算機學院 陜西 西安 710121)

0 引 言

2010年，美國賓夕法尼亞州立大學電氣工程系的 Bayraktar Z和Werner D H 博士以及氣象學系的Komurcu M博士[1]根據(jù)對大氣運動的簡單模擬提出了風驅(qū)動優(yōu)化算法(WDO)[2-3]。該算法是將空氣微團的物理運動模型抽象成簡化的空氣質(zhì)點受力運動模型，主要分析空氣質(zhì)點在大氣中的受力運動情況，主要考慮四個力：重力、摩擦力、科氏力和大氣壓力。通過運用牛頓第二定律及理想氣體狀態(tài)方程，推導出空氣質(zhì)點速度方程及位置方程。

相比于其他全局優(yōu)化算法(如粒子群算法)，風驅(qū)動優(yōu)化算法具有全局搜索能力強、收斂速度較快、精度高、尋優(yōu)效率高、魯棒性強，且可以通過微調(diào)系數(shù)優(yōu)化算法效果，并且可用于解決多維和多模態(tài)問題，可以處理連續(xù)和離散優(yōu)化問題，具有廣泛的應用前景。已經(jīng)被應用于鍋爐NO_x排放模型優(yōu)化[4]、PID參數(shù)優(yōu)化[5]、電磁綜合問題[6]、雷達波束圖[7]、橋梁有限元模型[8]、非等間距直線陣方向圖實例[9]、霍夫變換[10]等場景中。

為了解決風驅(qū)動優(yōu)化算法陷入局部最優(yōu)時而導致的精度低以及收斂速度慢等問題，本文提出了基于模擬退火和歷史存檔兩者融合的風驅(qū)動優(yōu)化算法，簡稱WDO-HSSA。實驗表明，改進后的算法具有穩(wěn)定性好、收斂速度快、尋優(yōu)精度高的特點。

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

1.1 WDO算法的基本原理

風驅(qū)動優(yōu)化算法通過各地氣壓不同而導致大氣運動這一自然現(xiàn)象，建立物理模型，從而得到一種新的全局優(yōu)化算法。在WDO算法中，研究對象是空氣質(zhì)點，對簡化的空氣質(zhì)點運用牛頓第二定律、理想氣體狀態(tài)方程可得空氣質(zhì)點的位置和速度公式[11]。

速度更新公式為：

unext=(1-a)ucur-gxcur+

(1)

位置更新公式為：

xnext=xcur+unext

(2)

式中：ucur為空氣質(zhì)點的當前速度，unext為空氣質(zhì)點下一次迭代的速度，xcur為當前空氣質(zhì)點位置，xbest為最優(yōu)位置，xnext為空氣質(zhì)點下一次迭代位置，i表示所有空氣質(zhì)點依據(jù)適應度值的一個升序排列，uc表示第i個空氣質(zhì)點除k維以外的其他維度的速度，g表示重力相關因數(shù)，a表示摩擦因數(shù)，R為理想氣體常數(shù),T為溫度。

風驅(qū)動算法步驟如下：

Step1初始化種群規(guī)模、維度、最大迭代次數(shù)、搜索邊界、公式參數(shù)、壓力函數(shù)(即目標函數(shù))。

Step2初始化空氣質(zhì)點，分配初始速度和位置。

Step3計算空氣質(zhì)點壓力值并按照壓力值大小進行排序。

Step4根據(jù)式(1)、式(2)分別更新空氣質(zhì)點的速度和位置。

Step5若未達到終止條件，則轉至Step3，若終止，輸出最優(yōu)解。

通常終止條件為足設定一個理想的壓力值或初始化的最大迭代次數(shù)。

1.2 模擬退火算法

模擬退火算法[12]最早由N.Metropolis等提出，模擬退火思想模擬了熱力學中的高溫金屬冷卻的過程，是一種隨機組合優(yōu)化方法。模擬退火算法作為一種通用的優(yōu)化算法，廣泛應用于金融、管理、工程的領域。模擬退火算法模擬熱力學中粒子系統(tǒng)降溫過程，用于求解最優(yōu)化問題。當孤立粒子系統(tǒng)溫度逐步下降時，以一定概率接受或拒絕新的狀態(tài)，使粒子系統(tǒng)逐步趨于有序，使系統(tǒng)近似于熱力平衡狀態(tài)，最終系統(tǒng)將達到基態(tài)，等同于全局極小點[13]。通過以概率作為接受新狀態(tài)的方法，可以有效避免搜索陷入局部最優(yōu)的問題，提高尋優(yōu)能力。

1.3 歷史存檔思想

本文提出了一種歷史存檔的優(yōu)化思想，它是指通過記錄歷史數(shù)據(jù)，完善“自我認知”的過程，它是對歷史經(jīng)驗的累積。在處理當代數(shù)據(jù)時，結合歷史經(jīng)驗，能更好地對未來進行決策。

為了減少歷史數(shù)據(jù)的存儲，提高算法執(zhí)行效率，本文提出的歷史存檔思想采用設置兩個歷史暫存點，存儲與當代最近的間隔相鄰周期的全局最優(yōu)值。利用兩個暫存點的大小比較來判斷收斂狀態(tài)以及確定是否需要對種群進行調(diào)整。

基于歷史存檔思想的實施步驟如下：

Step1初始化記錄間隔周期T，設置第一次記錄時的當前周期為begin，設置記錄間隔周期的全局最優(yōu)解的變量Gbegin、Gbegin+T。

Step2計算該點適應度函數(shù)E=f(x)。

Step3是否觸發(fā)記錄條件，如果當前周期為begin+nT(n為1,2,…)，則觸發(fā)記錄條件，繼續(xù)執(zhí)行歷史存檔的判斷準則，反之則轉至Step5。

Step4更新Gbegin、Gbegin+T。如若Gbegin

Step5增加迭代次數(shù)，當K達到最大迭代次數(shù)時停止迭代，否則返回Step2。

以上過程稱之為基于暫存點的歷史存檔準則。

1.4 基于模擬退火和歷史存檔融合的風驅(qū)動優(yōu)化算法改進

通常WDO算法經(jīng)過若干次迭代以后，會陷入局部最優(yōu)解，種群失去了多樣性，致使收斂速度變慢，造成早熟。為了解決該問題，本文將模擬退火和歷史存檔思想融入到風驅(qū)動優(yōu)化算法之中，由此提出了基于模擬退火和歷史存檔兩者融合的風驅(qū)動優(yōu)化算法，簡稱WDO-HSSA。其中，引入模擬退火思想能使WDO算法避免陷入局部最優(yōu)的陷阱，同時提高全局搜索能力，引入歷史存檔思想使算法有效增強陷入局部最優(yōu)解時的脫困能力。

改進后的WDO算法具體步驟如下：

Step1初始化種群規(guī)模、維度、最大迭代次數(shù)、搜索邊界、公式參數(shù)、壓力函數(shù)(即目標函數(shù))。

Step2初始化空氣質(zhì)點，分配初始速度和位置。

Step3計算空氣質(zhì)點壓力值并按照壓力值大小進行排序。

Step4更新空氣質(zhì)點的速度和位置。

Step5計算當前解與新解的適應度值，利用Metropolis準則更新全局最優(yōu)值。

Step6判斷適應度值否達到要求，若滿足則執(zhí)行降溫操作，反之，則轉至Step8。

Step7降溫退火操作。

Step8每隔預先設置的代數(shù)則對相應周期的歷史全局最優(yōu)解記錄存檔。

Step9根據(jù)歷史存檔的準則決定是否變異部分空氣質(zhì)點速度和位置。

Step10若未達到終止條件，則轉至Step3，若終止，輸出最優(yōu)解。

通常終止條件為一個理想的壓力值或初始化的最大迭代次數(shù)。

2 實驗設計及仿真分析

2.1 測試函數(shù)設計

為了評價優(yōu)化算法性能，本文采用了表1所示的五種標準測試函數(shù)對風驅(qū)動優(yōu)化算法(WDO)、基于模擬退火和歷史存檔融合的風驅(qū)動優(yōu)化算法(WDO-HSSA)、粒子群算法(PSO)[14-16]進行測試。分別是Sphere函數(shù)、Griewank函數(shù)、Rastrigrin函數(shù)、Ackley函數(shù)、Quartic函數(shù)。表1所示為五種測試函數(shù)的公式定義以及實驗用到的搜索范圍和函數(shù)的最優(yōu)值。

表1 測試函數(shù)基本信息

續(xù)表1

2.2 實驗條件設計

每個算法實驗按照維度的不同劃分為三組，分別是維度N=10、N=20、N=50三組，隨著維度的增加，測試難度不斷增大，更加能反映算法在不同維度下的搜索能力，體現(xiàn)出算法綜合性能。每組實驗在每個測試函數(shù)下都獨立執(zhí)行30次，記錄下30次執(zhí)行后的最優(yōu)適應度值BP(Best Fitness)、平均最優(yōu)適應度值MBF(Mean Best Fitness)、標準差SD(Standard Deviation)、平均適應度值誤差AE(Average Error)這四組數(shù)據(jù)，其中BF反映了算法尋優(yōu)的極限能力，BF越接近極值，則算法極限搜索能力越強。MBF反映了算法尋優(yōu)的平均能力，MBF越小，則算法平均搜索能力越強。SD反映了算法在多次重復尋優(yōu)過程中的穩(wěn)定性，SD越小，則算法穩(wěn)定性越強。AE反映了算法性能優(yōu)越性，當AE越小，算法性能通常越優(yōu)，AE的計算公式為AE=MBF-BF。

在實驗設計中，三個算法的參數(shù)始終保持一致。具體設置如下：種群數(shù)為40，搜索范圍見表1，最大搜索速度都為1。其中，WDO參數(shù)設置如下:a=0.7、g=0.8、RT=0.7、c=0.42。WDO-HSSA參數(shù)設置如下:a=0.7、g=0.8、RT=0.7、c=0.42、T=初始化全局最優(yōu)值、r=0.9、Tmin=0。PSO參數(shù)設置如下:c1=2、c2=2、w=0。實驗仿真環(huán)境為MATLAB R2017a。

2.3 結果分析

根據(jù)表2中最優(yōu)適應度值(BF)可以看出，WDO-HSSA算法、WDO算法在標準測試函數(shù)f1、f2、f3、f4、f5下尋優(yōu)精度對比PSO算法均有一定的提升，其中對于函數(shù)f1、f4均有10個數(shù)量級以上的提升。隨著維度的增加，WDO-HSSA算法在BF這一指標上優(yōu)勢越來越明顯。可以得出結論，在BF指標上WDO-HSSA算法最好，其次是WDO算法，PSO算法最差，這說明WDO-HSSA的極限尋優(yōu)精度的能力上比起WDO算法以及PSO算法更強。

表2 多組測試函數(shù)不同維度下的仿真結果

續(xù)表2

圖1所示為三種算法的平均最優(yōu)適應值曲線，其中，橫軸表示迭代次數(shù)，縱軸表示30次實驗平均最優(yōu)適應度值的對數(shù)，每幅子圖頂部標明了對應的標準測試函數(shù)及其測試維度和搜索范圍。根據(jù)表2中平均最優(yōu)適應度值(MBF)及圖1可以看出，WDO-HSSA、WDO算法在測試函數(shù)f1、f2、f3、f4、f5下MBF指標比PSO算法MBF指標更優(yōu)?？梢缘贸鼋Y論，在MBF指標上WDO-HSSA算法最好，其次是WDO算法，PSO算法最差，這說明WDO-HSSA的平均尋優(yōu)精度的能力上強于WDO算法以及PSO算法。

根據(jù)表2中標準差值(SD)可以看出，WDO-HSSA算法、WDO算法在標準測試函數(shù)f1、f2、f3、f4、f5下標準差值對比PSO算法均有較為滿意的解?？梢缘贸鼋Y論，在SD指標上WDO-HSSA優(yōu)于WDO算法，PSO算法最差，這說明WDO-HSSA算法在算法穩(wěn)定性上最好，其次是WDO算法，最差為PSO算法。

根據(jù)表2中平均適應度值誤差(AE)可以看出，WDO-HSSA算法、WDO算法在標準測試函數(shù)f1、f2、f3、f4、f5下標準差值對比PSO算法均有較為滿意的解。隨著維度的增加，這一指標的優(yōu)勢越來越明顯?？梢缘贸鼋Y論，在AE指標上WDO-HSSA算法最好，其次是WDO算法，PSO算法最差，說明WDO-HSSA算法性能優(yōu)越性上好于WDO算法，最差是PSO算法。

綜上所述，在BF、MBF、SD、AE四組指標下，可對三種算法的尋優(yōu)性能排序如下：WDO-HSSA>WDO>PSO。隨著維度的提升，WDO-HSSA算法的在四組指標下的優(yōu)勢也是越來越明顯。所以無論從算法精度層面考慮還是從穩(wěn)定性層面考慮，WDO-HSSA算法具有更強的尋優(yōu)能力。

3 結 語

風驅(qū)動的優(yōu)化算法是一種基于自然啟發(fā)式的全局優(yōu)化算法。本文在標準的風驅(qū)動優(yōu)化算法下引入了模擬退火思想以及歷史存檔思想來完成對算法的進一步改進。通過模擬退火機制能更好地避免陷入局部最優(yōu)問題，模擬退火接受變異的種群，隨著迭代、溫度的下降，接受概率逐漸減小，從而提高了收斂性能。通過引入歷史存檔機制，在發(fā)現(xiàn)陷入局部最有問題時，變異一定數(shù)量種群，使算法能有效提高陷入局部最優(yōu)問題時的擺脫能力。所以基于模擬退火以及歷史存檔融合后的算法能有效提高避免陷入局部最優(yōu)的能力以及陷入局部最優(yōu)時的脫困能力,增強全局搜索能力以及尋優(yōu)精度。通過測試仿真結果表明，HSSA-WDO算法的性能優(yōu)于WDO算法以及PSO算法。

[1] 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. IEEE, 2010:1- 4.

[2] Bayraktar Z, Komurcu M, Bossard J A, et al. The Wind Driven Optimiazation Technique and its Application in Electromagnetics[J]. IEEE Transactions on Antennas & Propagation, 2013, 61(5):2745- 2757.

[3] Bayraktar Z, Komurcu M, Jiang Z H, et al. Stub-loaded inverted-F antenna synthesis via Wind Driven Optimization[C]// IEEE International Symposium on Antennas and Propagation. IEEE, 2011:2920- 2923.

[4] 牛培峰, 趙振, 馬云鵬,等. 基于風驅(qū)動算法的鍋爐NOx排放模型優(yōu)化[J]. 動力工程學報, 2016, 36(9):732- 738.

[5] 陳彬彬, 曹中清, 余勝威. 基于風驅(qū)動優(yōu)化算法WDO的PID參數(shù)優(yōu)化[J]. 計算機工程與應用, 2016, 52(14):250- 253.

[6] 任作琳. 風驅(qū)動優(yōu)化算法及其在電磁綜合問題中的應用研究[D]. 江蘇科技大學, 2016.

[7] 毛晟,張貞凱,田雨波. 基于風驅(qū)動算法的機會陣雷達波束圖綜合[J]. 江蘇科技大學學報(自然科學版),2017,31(4):485- 489.

[8] 周赤偉. 基于泰勒展開式和風驅(qū)動優(yōu)化算法的橋梁有限元模型修正研究[D]. 北京交通大學, 2016.

[9] 任作琳,田雨波,孫菲艷. 基于改進風驅(qū)動算法的非等間距直線陣綜合[J]. 計算機科學,2016,43(7):268- 274.

[10] 范旭,曹中清,陳彬彬. 基于風驅(qū)動優(yōu)化的霍夫變換算法[J]. 計算機工程與設計,2017,38(6):1522- 1525.

[11] 任作琳,田雨波,孫菲艷. 具有強開發(fā)能力的風驅(qū)動優(yōu)化算法[J]. 計算機科學,2016,43(1):275- 281,305.

[12] 龐峰. 模擬退火算法的原理及算法在優(yōu)化問題上的應用[D].吉林大學,2006.

[13] 盧宇婷,林禹攸,彭喬姿,等. 模擬退火算法改進綜述及參數(shù)探究[J]. 大學數(shù)學,2015,31(6):96- 103.

[14] 隨聰慧. 粒子群算法的改進方法研究[D].西南交通大學,2010.

[15] 李志,陳年生,郭小珊,等. 粒子群算法及其改進技術研究[J]. 湖北師范學院學報(自然科學版),2011,31(2):104- 108.

[16] 白艷敏. 粒子群算法及其應用研究[D].蘭州交通大學,2013.