風(fēng)驅(qū)動-差分進(jìn)化混合優(yōu)化算法設(shè)計(jì)及其性能分析

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

（1.南充職業(yè)技術(shù)學(xué)院，南充637131；2.南充電子信息產(chǎn)業(yè)技術(shù)研究院，南充637131）

0 引言

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

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

本文基于對上述兩種算法取長補(bǔ)短、優(yōu)勢互補(bǔ)的思路，以WDO 算法為主體，嘗試以兩種不同方式將DE算法與之融合，設(shè)計(jì)并實(shí)現(xiàn)相應(yīng)的風(fēng)驅(qū)動-差分進(jìn)化（WDO-DE）混合優(yōu)化算法，并與四種常用的優(yōu)化算法比較以分析其性能。

1 風(fēng)驅(qū)動優(yōu)化算法原理與流程

1.1 風(fēng)驅(qū)動優(yōu)化算法原理

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

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

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

為防止速度過快導(dǎo)致空氣質(zhì)點(diǎn)越過最優(yōu)位置，可設(shè)定其最大值，并按公式（2）進(jìn)行越界處理。

空氣質(zhì)點(diǎn)的位置按公式（3）更新。

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

在實(shí)際應(yīng)用WDO 算法時(shí)，空氣質(zhì)點(diǎn)在大氣中的每個位置代表問題的一個候選解，以所在位置的氣壓值作為其適應(yīng)度，根據(jù)速度和位置更新方程迭代搜索解空間。式（1）右端：第一項(xiàng)表示摩擦力的影響，即當(dāng)沒有其他力的作用時(shí)，摩擦力將使空氣質(zhì)點(diǎn)速度在原路徑上減??；第二項(xiàng)表示重力的影響，該速度分量始終指向坐標(biāo)原點(diǎn)方向，可避免空氣質(zhì)點(diǎn)陷于邊界位置不能跳出，從而提高全局搜索能力；第三項(xiàng)模擬氣壓梯度力，因j=1 時(shí)壓力值（適應(yīng)度）最小，故空氣質(zhì)點(diǎn)越接近當(dāng)前最優(yōu)解（j 與1 之差的絕對值越?。渌俣茸兓叫。坏谒捻?xiàng)模擬科氏力，通過加入空氣質(zhì)點(diǎn)的其他任一維速度對當(dāng)前維速度的影響，增強(qiáng)算法的穩(wěn)健性。

1.2 風(fēng)驅(qū)動優(yōu)化算法運(yùn)行流程

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

圖1 標(biāo)準(zhǔn)WDO算法的運(yùn)行流程

2 風(fēng)驅(qū)動-差分進(jìn)化混合優(yōu)化算法

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

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

2.1 PWDO-DE算法流程

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

（2）初始化種群：

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

（3）迭代尋優(yōu)T 次：

①WDO 算法過程

For i=1 to N/2

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

End if

②DE 算法過程

執(zhí)行變異操作，產(chǎn)生向量

執(zhí)行交叉操作，得到向量ut

③確定當(dāng)前最優(yōu)解xbest

2.2 EWDO-DE算法流程

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

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

（3）迭代尋優(yōu)T 次：

For i=1 to N

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

執(zhí)行變異操作，產(chǎn)生向量

執(zhí)行交叉操作，得到向量ui,t

3 WDO-DE算法性能測試

3.1 測試函數(shù)選擇

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

表1 八個測試函數(shù)的基本屬性

3.2 算法參數(shù)設(shè)置與測試結(jié)果

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

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

（2）WDO 算法：與WDO-DE 算法中對應(yīng)參數(shù)相同。

（3）DE 算法：與WDO-DE 算法中對應(yīng)參數(shù)相同。

（4）PSO 算法：學(xué)習(xí)因子c1=c2=2.4995。

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

各算法分別對八個標(biāo)準(zhǔn)函數(shù)進(jìn)行50 次獨(dú)立測試的結(jié)果如表2 所示。

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

3.3 算法性能比較分析

根據(jù)表2 的測試結(jié)果和圖2、圖3 所示的迭代搜索曲線，可分析各算法的評價(jià)指標(biāo)數(shù)據(jù)得出如下結(jié)論：

（1）從標(biāo)準(zhǔn)WDO 算法和DE 算法的四項(xiàng)性能指標(biāo)數(shù)據(jù)可明顯看出，前者對多維函數(shù)f1～f5的優(yōu)化性能全面領(lǐng)先于后者，后者則對二維函數(shù)f6～f8的優(yōu)化能力明顯高于前者。由此可以推知，將二者融于一體當(dāng)可發(fā)揮各自所長、實(shí)現(xiàn)優(yōu)勢互補(bǔ)，從而獲得比標(biāo)準(zhǔn)WDO 算法和DE 算法更好的全局優(yōu)化性能。這正是本文提出WDO-DE 混合優(yōu)化算法的依據(jù)。

圖2 各算法求解Sphere函數(shù)的迭代曲線

圖3 各算法求解Shubert函數(shù)的迭代曲線

表2 算法性能測試結(jié)果

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

（3）在各算法的50 次獨(dú)立測試中，PSO、BF-QPSO和DE 算法對f1～f5所得最優(yōu)結(jié)果的標(biāo)準(zhǔn)差較大，且收斂于理論最優(yōu)值的次數(shù)為0；WDO 算法對f1～f5的這兩項(xiàng)指標(biāo)數(shù)據(jù)皆好于前三種算法，但對f6～f8卻明顯較差；兩種WDO-DE 算法則對全部八個函數(shù)的各項(xiàng)指標(biāo)數(shù)據(jù)全面領(lǐng)先，表明其穩(wěn)健性明顯好于其他四種算法。

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

（5）雖然兩種WDO-DE 算法的各項(xiàng)性能指標(biāo)全面優(yōu)于作為對比的其他四種算法，但PWDO-DE 算法對f3和f4、EWDO-DE 算法對f4和f5的測試結(jié)果并未完全取得理論最佳，表明其尚有進(jìn)一步改進(jìn)的空間。

4 結(jié)語

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