基于模擬退火和歷史存檔融合的風驅動優化算法

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

0 引 言

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

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

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

1 風驅動優化算法

1.1 WDO算法的基本原理

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

速度更新公式為：

unext=(1-a)ucur-gxcur+

(1)

位置更新公式為：

xnext=xcur+unext

(2)

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

風驅動算法步驟如下：

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

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

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

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

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

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

1.2 模擬退火算法

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

1.3 歷史存檔思想

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

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

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

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

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

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

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

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

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

1.4 基于模擬退火和歷史存檔融合的風驅動優化算法改進

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

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

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

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

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

Step4更新空氣質點的速度和位置。

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

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

Step7降溫退火操作。

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

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

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

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

2 實驗設計及仿真分析

2.1 測試函數設計

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

表1 測試函數基本信息

續表1

2.2 實驗條件設計

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

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

2.3 結果分析

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

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

續表2

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

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

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

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

3 結 語

風驅動的優化算法是一種基于自然啟發式的全局優化算法。本文在標準的風驅動優化算法下引入了模擬退火思想以及歷史存檔思想來完成對算法的進一步改進。通過模擬退火機制能更好地避免陷入局部最優問題，模擬退火接受變異的種群，隨著迭代、溫度的下降，接受概率逐漸減小，從而提高了收斂性能。通過引入歷史存檔機制，在發現陷入局部最有問題時，變異一定數量種群，使算法能有效提高陷入局部最優問題時的擺脫能力。所以基于模擬退火以及歷史存檔融合后的算法能有效提高避免陷入局部最優的能力以及陷入局部最優時的脫困能力,增強全局搜索能力以及尋優精度。通過測試仿真結果表明，HSSA-WDO算法的性能優于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] 牛培峰, 趙振, 馬云鵬,等. 基于風驅動算法的鍋爐NOx排放模型優化[J]. 動力工程學報, 2016, 36(9):732- 738.

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

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

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

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

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

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

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

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

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

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

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

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