風驅動-差分進化混合優化算法設計及其性能分析

胡振，楊華，周金容，代霜春，龍紅梅

（1.南充職業技術學院，南充637131；2.南充電子信息產業技術研究院，南充637131）

0 引言

風驅動優化（Wind Driven Optimization，WDO）算法是一種新興的群體搜索全局優化算法[1]。該算法模擬了簡化的空氣質點在大氣中的受力運動模型，其概念易于理解，更新方程具有一定的物理意義，能夠保證空氣質點的全局“探索”能力與局部“開發”能力的平衡[2]；可調參數較少，且能通過微調系數優化算法效果[3]，具有較好的全局收斂能力和魯棒性，對于多維和多模、連續和離散等各類優化問題都適用[4]。但WDO 算法也存在前期收斂過快、易陷入局部最優，后期種群多樣性不足導致收斂速度慢等缺陷[5]，特別是在多峰函數優化時，無法從局部最優值中跳出，無法獲得理想的全局最優結果[6]。為此，研究者提出了一些WDO 改進算法，通過引入變異機制[7]、量子編碼[8]及參數自適應[9-11]等策略改善種群多樣性和全局搜索性能，從而提高算法的尋優精度、收斂速度和運行穩健性。這些改進算法分別用于解決非等間距直線陣方向圖、機器人路徑規劃和主動懸架LQR 控制優化等問題，取得了較好的效果。

差分進化（Differential Evolution，DE）算法是利用種群個體間差異而逐步進化的一種搜索算法，其進化流程類似于遺傳算法（Genetic Algorithm，GA），主要包括變異、交叉和選擇三種操作。該算法在不同的進化階段，由于個體差異性的變化而表現出不同的搜索能力和開發能力：初期個體差異性較大，將在較大范圍內尋找最優解，故其搜索能力較強；末期則趨于逐漸收斂狀態，個體間差異變小，因而開發能力較強。DE 算法的這種種群自我調節能力，使其具有廣泛的適用性和突出的優化性能[12]。在算法實現和實際應用中，DE 算法雖然具有控制參數少、收斂快、穩健性好等優點，但也存在參數難以選擇、早熟收斂和搜索停滯等問題。有鑒于此，研究者們提出了DE 算法的控制參數自適應、進化策略選擇、多種群結構以及與其他算法混合等多種改進方案[13-15]。

本文基于對上述兩種算法取長補短、優勢互補的思路，以WDO 算法為主體，嘗試以兩種不同方式將DE算法與之融合，設計并實現相應的風驅動-差分進化（WDO-DE）混合優化算法，并與四種常用的優化算法比較以分析其性能。

1 風驅動優化算法原理與流程

1.1 風驅動優化算法原理

WDO 算法模擬了因各地氣壓不同導致大氣運動、終至氣壓平衡的過程。該算法以抽象的空氣質點為研究對象，將其受力運動情況簡化為4 個力的作用，即由高壓指向低壓的氣壓梯度力、與氣壓梯度力發生作用的摩擦力、指向地心的重力和地球自轉引起的科氏力。將這四個力代入牛頓第二定律，并結合理想氣體狀態方程，即可推導出WDO 算法的速度和位置更新公式，其原理描述如下。

設有N 個空氣質點在D 維空間中運動，第i 個空氣質點在第t 次迭代時的速度和位置分別表示為其中1≤i≤N、1≤t≤T、T 為最大迭代次數，則其速度按公式（1）更新。

式中：和分別為空氣質點i 在d 維度的當前（第t 次迭代）速度和更新速度；和xgbest分別為空氣質點i 在d 維度的當前位置和全局最優位置（D 維向量）；j 為所有空氣質點壓力值的升序排列為空氣質點i 除第d 維之外的其他任一維速度；α、g、RT 和c 為4 個常數，分別代表摩擦系數、重力加速度、氣壓梯度力影響系數和科氏力影響系數。根據經驗，可置α∈[0.8,0.9]、g∈[0.6,0.7]、RT∈[1.0,2.0]、c∈[0.05,3.6]。

為防止速度過快導致空氣質點越過最優位置，可設定其最大值，并按公式（2）進行越界處理。

空氣質點的位置按公式（3）更新。

式中：和分別為空氣質點i 在d 維度的當前（第t 次迭代）位置和更新位置，為其更新速度；△k 為時間間隔，一般取值為1。

在實際應用WDO 算法時，空氣質點在大氣中的每個位置代表問題的一個候選解，以所在位置的氣壓值作為其適應度，根據速度和位置更新方程迭代搜索解空間。式（1）右端：第一項表示摩擦力的影響，即當沒有其他力的作用時，摩擦力將使空氣質點速度在原路徑上減小；第二項表示重力的影響，該速度分量始終指向坐標原點方向，可避免空氣質點陷于邊界位置不能跳出，從而提高全局搜索能力；第三項模擬氣壓梯度力，因j=1 時壓力值（適應度）最小，故空氣質點越接近當前最優解（j 與1 之差的絕對值越小），其速度變化越小；第四項模擬科氏力，通過加入空氣質點的其他任一維速度對當前維速度的影響，增強算法的穩健性。

1.2 風驅動優化算法運行流程

標準WDO 算法的基本過程為：根據需優化的具體問題，首先初始化一個空氣質點種群，并為每個空氣質點在搜索空間內隨機分配初始速度、位置。然后進入迭代尋優過程，每次迭代都使空氣質點向最優壓力值（即適應度函數）和最優位置運動，直到最大迭代次數為止。其具體運行流程如圖1 所示。

圖1 標準WDO算法的運行流程

2 風驅動-差分進化混合優化算法

WDO 算法和DE 算法都是高效的全局搜索算法，但二者的原理和搜索機制存在較大差異。前者兼顧了全局探索與局部開發能力的平衡，但在迭代搜索過程中不能持續保證種群的多樣性，容易發生后期收斂變慢、陷入局部最優等問題；后者雖然也存在一些缺陷，但其變異機制卻能有效避免種群多樣性不足的問題。因此，可嘗試將WDO 算法與DE 算法融合，構建一種風驅動-差分進化（WDO-DE）混合優化算法，以發揮其各自優勢，提高全局優化能力。

WDO 算法與DE 算法融合的方式有三種：其一是二者并行形成PWDO-DE（Parallel WDO-DE）算法，即采用雙種群結構，以兩種算法分別對各自子種群進行迭代搜索，通過信息交換機制實現種群的全局優化；其二為將DE 算法嵌入WDO 算法構成EWDO-DE（Em?bedded WDO-DE）算法，即在WDO 算法的迭代尋優流程中嵌入DE 算法的優化算子；其三則是將WDO 算法嵌入DE 算法構建EDE-WDO（Embedded DE-WDO）算法，即在DE 算法的迭代尋優流程中嵌入WDO 算法的優化算子。本文以WDO 算法為主體，故按前兩種方式進行相應混合優化算法流程設計。

2.1 PWDO-DE算法流程

（1）設置種群規模N、最大迭代次數T。WDO 算法參數：摩擦系數α、重力加速度g、氣壓梯度力系數RT、科氏力系數c，速度邊界vmax、位置邊界xmax；DE 算法參數：變異比例因子Fms、交叉概率Pc。

（2）初始化種群：

②生成規模為N/2 的子種群，隨機分配其個體位置。計算適應度值，確定DE 算法之初始最優解；

（3）迭代尋優T 次：

①WDO 算法過程

For i=1 to N/2

按式（3）更新位置xi,t，并進行越界處理

End if

②DE 算法過程

執行變異操作，產生向量

執行交叉操作，得到向量ut

③確定當前最優解xbest

2.2 EWDO-DE算法流程

（1）設置WDO 算法參數：種群規模N、最大迭代次數T，摩擦系數α、重力加速度g、氣壓梯度力系數RT、科氏力系數c，速度邊界vmax、位置邊界xmax；DE 算法參數：變異比例因子Fms、交叉概率Pc。

（2）生成規模為N 的種群，隨機分配其個體速度vi和位置xi。計算適應度值，確定初始最優解xbest。

（3）迭代尋優T 次：

For i=1 to N

按式（1）更新速度vi,t、按式（2）越界處理按式（3）更新位置xi,t，并進行越界處理

執行變異操作，產生向量

執行交叉操作，得到向量ui,t

3 WDO-DE算法性能測試

3.1 測試函數選擇

用標準函數測試兩種WDO-DE 算法的性能，并與WDO 算法、DE 算法、粒子群優化（Particle Swarm Opti?mization，PSO）算法和細菌覓食-量子粒子群優化（Bac?terial Foraging-Quantum Behaved Particle Swarm Optimi?zation，BF-QPSO）算法進行比較。為了驗證WDO-DE算法的全局搜索能力、收斂速度和穩健性，本文選用各具特點的八個標準函數進行測試，分別為Sphere、Ellip?tic、Rastrigin、Ackley、Schwefel 1.2、Branin、Easom 和Shubert，其基本屬性如表1 所示。

表1 八個測試函數的基本屬性

3.2 算法參數設置與測試結果

為了便于比較兩種WDO-DE 算法與其他四種算法的性能，用MATLAB R2019a 編寫各算法對八個標準函數的測試程序，分別獨立運行50 次，將所得結果的最優值、平均值、標準差和收斂于理論最優值（Best The?oretical Value，BTV）的次數作為評價指標。各算法測試程序運行時，種群規模N=40、最大迭代次數T=500、速度邊界v∈[-1.2,1.2]、位置邊界（搜索范圍）如表1 所示，其余參數分別設置如下。

（1）兩種WDO-DE 算法：摩擦系數α=0.9、重力加速度g=0.7、氣壓梯度力系數RT=1.0、科氏力系數c=0.8；變異比例因子Fms=0.25、交叉概率Pc=0.2。

（2）WDO 算法：與WDO-DE 算法中對應參數相同。

（3）DE 算法：與WDO-DE 算法中對應參數相同。

（4）PSO 算法：學習因子c1=c2=2.4995。

（5）BF-QPSO 算法參數：趨化次數Ns=4。

各算法分別對八個標準函數進行50 次獨立測試的結果如表2 所示。

以f1、f8的求解過程為例，各算法的迭代搜索過程對比分別如圖2、圖3 所示。圖中橫坐標為迭代搜索次數，縱坐標為50 次獨立測試所得平均最優函數值的對數。

3.3 算法性能比較分析

根據表2 的測試結果和圖2、圖3 所示的迭代搜索曲線，可分析各算法的評價指標數據得出如下結論：

（1）從標準WDO 算法和DE 算法的四項性能指標數據可明顯看出，前者對多維函數f1～f5的優化性能全面領先于后者，后者則對二維函數f6～f8的優化能力明顯高于前者。由此可以推知，將二者融于一體當可發揮各自所長、實現優勢互補，從而獲得比標準WDO 算法和DE 算法更好的全局優化性能。這正是本文提出WDO-DE 混合優化算法的依據。

圖2 各算法求解Sphere函數的迭代曲線

圖3 各算法求解Shubert函數的迭代曲線

表2 算法性能測試結果

（2）PSO、BF-QPSO 和DE 算法僅能對f6～f8取得理論最優值，而對f1～f5所得最優值和平均值皆距理論最優值較遠；WDO 算法可求出f1～f5的理論最優值，但不能獲得f6～f8的理論最優值，且其平均值與理論最優值相差較大；EWDO-DE 算法能解得f4之外的其余函數理論最優值，且其對f4的最優值和平均值較為接近理論最優值；PWDO-DE 算法則可搜索到全部八個函數的理論最優值，僅對f3所得平均值離理論最優值較遠。這些可以表明，兩種WDO-DE 算法的全局搜索能力顯著高于其他四種算法。

（3）在各算法的50 次獨立測試中，PSO、BF-QPSO和DE 算法對f1～f5所得最優結果的標準差較大，且收斂于理論最優值的次數為0；WDO 算法對f1～f5的這兩項指標數據皆好于前三種算法，但對f6～f8卻明顯較差；兩種WDO-DE 算法則對全部八個函數的各項指標數據全面領先，表明其穩健性明顯好于其他四種算法。

（4）對于能夠獲得理論最優值的同一函數測試時，EWDO-DE 算法搜索到全局最優值所需的迭代次數比PWDO-DE 算法更少，表明前者的收斂速度更快。究其原因，PWDO-DE 算法中的DE 過程與WDO 過程是并行的，其變異、交叉和選擇操作在相對獨立的DE 算法過程內部執行，受到影響的個體僅為種群規模的一半；而EWDO-DE 算法是將DE 算法的變異、交叉和選擇算子嵌入在WDO 算法的迭代過程中執行，可使整個種群的多樣性發生改變，故能更快搜索到全局最優值。

（5）雖然兩種WDO-DE 算法的各項性能指標全面優于作為對比的其他四種算法，但PWDO-DE 算法對f3和f4、EWDO-DE 算法對f4和f5的測試結果并未完全取得理論最佳，表明其尚有進一步改進的空間。

4 結語

WDO 算法和DE 算法皆為性能突出、廣泛適用的群體搜索算法，并對多維優化和二維優化問題各具優勢，但都存在易陷入局部最優、后期收斂變慢甚至搜索停滯等缺陷。本文以WDO 算法為基礎，以并行和嵌入兩種方式分別融入DE 算法，設計并實現了相應的PWDO-DE 和EWDO-DE 混合優化算法，通過標準函數測試驗證，其全局搜索能力、收斂速度和穩健性均顯著優于用作對比的四種算法。