重選精英個(gè)體的非線性收斂灰狼優(yōu)化算法

黎素涵，葉春明

上海理工大學(xué) 管理學(xué)院，上海200093

群智能算法是一類通過模擬自然界中生物和非生命系統(tǒng)的群體智能行為機(jī)制來尋優(yōu)的元啟發(fā)式算法[1]，具有易于實(shí)現(xiàn)、靈活性強(qiáng)、參數(shù)較少等優(yōu)點(diǎn)。Wolpert等[2]提出的NFL（No Free Lunch）定理從邏輯上證明了不存在一個(gè)元啟發(fā)式算法可以解決所有優(yōu)化問題。因此，元啟發(fā)式算法領(lǐng)域的研究非?；钴S，很多專家學(xué)者進(jìn)行針對當(dāng)前算法的改進(jìn)和新算法的研究。近年來，很多新型群智能算法被提出，如文獻(xiàn)[3]提出的模擬布谷鳥寄生育雛繁殖行為和萊維飛行搜索機(jī)制的布谷鳥算法（Cuckoo Search，CS）；文獻(xiàn)[4]模擬果蠅靠嗅覺快速定位食物方位并快速飛近食物的行為，提出的果蠅優(yōu)化算法（Fruit Fly Optimization Algorithm，F(xiàn)OA）；文獻(xiàn)[5]提出的模擬鯨魚氣泡網(wǎng)攻擊、收縮包圍和隨機(jī)搜尋捕食行為的鯨魚優(yōu)化算法（Whale Optimization Algorithm，WOA）；文獻(xiàn)[6]提出的模擬哈里斯鷹捕食行為的搜索、搜索與開發(fā)轉(zhuǎn)換、開發(fā)三階段尋優(yōu)的哈里斯鷹算法（Harris Hawks Optimization，HHO）；文獻(xiàn)[7]提出的模擬蘑菇通過孢子發(fā)現(xiàn)豐富的生長區(qū)域來擴(kuò)大菌落發(fā)展的蘑菇繁殖算法（Mushroom Reproduction Optimization，MRO）等。

灰狼算法（Gray Wolf Optimization，GWO）是Mirjalili 等[8]受灰狼群的等級制度和捕食行為所啟發(fā)，于2014 年提出的一種群智能算法。其在文中證明GWO算法在求解精度和穩(wěn)定性方面明顯優(yōu)于差分進(jìn)化算法（Differential Evolution，DE）、粒子群算法（Particle Swarm Optimization，PSO）、引力搜索算法（GravitationalSearch Algorithm，GSA）、快速進(jìn)化算法（Fast Evolutionary Programing，F(xiàn)EP），且具有原理簡單、參數(shù)較少、全局搜索能力較強(qiáng)等特點(diǎn)。因此，GWO 算法在生產(chǎn)車間調(diào)度優(yōu)化[9]、智能家居負(fù)荷控制[10]、神經(jīng)網(wǎng)絡(luò)訓(xùn)練[11]等方面有廣泛應(yīng)用。但是，GWO 算法仍存在求解精度較低、后期收斂速度較慢、易陷入局部最優(yōu)的缺點(diǎn)。國內(nèi)外不少學(xué)者針對GWO 存在的問題進(jìn)行了改進(jìn)研究，主要從四個(gè)方面進(jìn)行改進(jìn)：種群初始化方式、搜索機(jī)制、參數(shù)調(diào)整以及與其他算法混合。文獻(xiàn)[12]提出了基于反向?qū)W習(xí)初始化種群和變異算子的非線性收斂灰狼算法；文獻(xiàn)[13]提出基于進(jìn)化種群動力學(xué)（Evolutionary Population Dynamics，EPD）的動態(tài)位置調(diào)整灰狼算法；文獻(xiàn)[14]提出了基于模糊層次算子的灰狼算法；文獻(xiàn)[15]提出了具有動態(tài)權(quán)重策略和非線性收斂因子策略的灰狼算法；文獻(xiàn)[16]提出了與差分進(jìn)化算法相結(jié)合的灰狼算法。本文采用非線性收斂因子調(diào)整策略和精英個(gè)體重選策略，來平衡算法的全局搜索能力和局部開發(fā)能力，提高算法的收斂速度和求解精度。

1 灰狼優(yōu)化算法

一個(gè)灰狼種群常由5～12 匹灰狼組成，在種群內(nèi)部有著森嚴(yán)的等級制度。如圖1所示，金字塔的第一層代表種群中的頭狼α，是整個(gè)種群的管理者，負(fù)責(zé)捕食、食物分配和作息時(shí)間地點(diǎn)等的決策；第二層是β，它負(fù)責(zé)輔助α領(lǐng)導(dǎo)灰狼群，當(dāng)α空缺時(shí)，它就會成為新的α；第三層是δ，它聽從于α和β，但可以指揮其他底層狼，負(fù)責(zé)偵察、放哨等工作。金字塔底層是ω，負(fù)責(zé)平衡種群內(nèi)部關(guān)系[13]。

圖1 灰狼等級結(jié)構(gòu)

灰狼種群以團(tuán)隊(duì)跟蹤、包圍的模式狩獵，因此種群內(nèi)部的等級制度使得捕獵非常有序而高效，狼群在α的帶領(lǐng)下，由β、δ進(jìn)攻獵物，ω負(fù)責(zé)輔助包圍獵物，最終狼群將從各個(gè)方向把獵物圍住并捕殺。

灰狼算法的求解過程模擬灰狼捕獵行為，即將全局最優(yōu)解視為獵物，所有備選解視為一個(gè)灰狼種群。設(shè)種群中灰狼數(shù)為N，搜索空間為d維，第i只灰狼在d維空間中的位置表示為xi=(xi1,xi2,…,xid)，其中適應(yīng)度值最優(yōu)的個(gè)體記為α次優(yōu)個(gè)體和第三優(yōu)個(gè)體分別記為β和δ，其他個(gè)體記為ω。尋優(yōu)過程即根據(jù)α、β、δ與獵物之間的距離來決定灰狼種群位置移動，向獵物靠近的過程。尋優(yōu)過程的數(shù)學(xué)描述為：

式（1）中D為灰狼個(gè)體與獵物的距離，式（2）表示灰狼位置更新的方式，t為迭代次數(shù)，Xp(t)是第t代獵物的位置，X(t)是第t代灰狼個(gè)體的位置，A和C為系數(shù)向量，分別用式（3）和式（4）計(jì)算：

其中，r1、r2是[0，1]內(nèi)的隨機(jī)數(shù)，a是[0，2]內(nèi)隨迭代次數(shù)線性遞減的收斂因子，用式（5）計(jì)算，max_iter表示迭代總次數(shù)。

狼群跟蹤獵物的數(shù)學(xué)模型為：

Dα、Dβ、Dδ分別表示α、β、δ，表示與獵物之間的距離，灰狼個(gè)體聽從α、β、δ移動圍捕獵物，X1、X2、X3表示ω分別向α、β、δ方向的位移量，式（12）是灰狼個(gè)體的位置更新方式。

2 灰狼優(yōu)化算法改進(jìn)策略

2.1 收斂因子非線性調(diào)整策略

全局搜索能力和局部開發(fā)能力是衡量元啟發(fā)式算法尋優(yōu)性能的兩種通用屬性，兩種屬性之間如何平衡是算法性能的關(guān)鍵。全局搜索能力是指在整個(gè)搜索空間尋找最優(yōu)解的能力，全局搜索能力強(qiáng)可以維持種群多樣性，避免陷入局部最優(yōu)。局部開發(fā)能力是指在局部空間內(nèi)精確搜索最優(yōu)解的能力，局部開發(fā)能力強(qiáng)可以提高算法的求解精度和收斂速度。通常，迭代前期使用全局搜索策略，后期使用局部開發(fā)策略。

如圖2 所示，虛線為標(biāo)準(zhǔn)GWO 收斂因子隨迭代次數(shù)的變化圖，實(shí)線為本文提出的非線性收斂因子隨迭代次數(shù)的變化圖。從圖中可以看出，標(biāo)準(zhǔn)GWO 算法的收斂因子在整個(gè)迭代過程中變化率是相同的，前期收斂速度過快導(dǎo)致搜索范圍較小、種群多樣性不足，后期收斂速度過慢導(dǎo)致算法求解效率較低。而本文提出的非線性收斂因子收斂曲線呈拋物線，前期收斂速度較慢，后期收斂速度較快。在迭代前期衰減速率較慢可擴(kuò)大搜索范圍，保證種群多樣性以適應(yīng)于全局搜索，迭代后期衰減速率較快可提高求解效率以適應(yīng)于局部精準(zhǔn)搜索。因此，本文提出的非線性收斂策略能更加有效地平衡全局搜索和局部搜索能力。

圖2 收斂因子變化圖

2.2 精英個(gè)體重選策略

精英策略（elite tactic）是指保留種群中的部分較優(yōu)解，為種群中其他個(gè)體的位置更新提供導(dǎo)向[18]，精英策略可以提高算法的收斂速度和求解效率，因此在GA、PSO等算法中有廣泛應(yīng)用。但是，由于種群中所有個(gè)體的位置更新都由最優(yōu)個(gè)體所引導(dǎo)，當(dāng)最優(yōu)個(gè)體陷入局部最小將導(dǎo)致整個(gè)種群“早熟”，陷入局部最優(yōu)[19]。

GWO 算法中，種群中的精英個(gè)體即適應(yīng)度值排前三的α、β、δ，種群位置更新由這三個(gè)精英個(gè)體引導(dǎo)。每次迭代后會將當(dāng)代狼群和前代的α、β、δ作比較，若有優(yōu)于這三匹狼的個(gè)體，則將其記錄為新的α、β、δ。當(dāng)種群中沒有出現(xiàn)優(yōu)于這三匹狼的個(gè)體，種群將繼續(xù)向這三匹狼靠近。這種搜索機(jī)制的優(yōu)點(diǎn)是能提高收斂速度和算法效率，缺點(diǎn)是導(dǎo)致種群損失多樣性。α不一定是全局最優(yōu)，當(dāng)α陷入局部最小，若種群繼續(xù)向其靠近，容易出現(xiàn)早熟現(xiàn)象，陷入局部最優(yōu)，尤其是求解多峰值函數(shù)時(shí)。

因此，本文提出一種新的精英個(gè)體重選策略，即每次迭代后都在當(dāng)代種群中選取適應(yīng)度值排名前三的個(gè)體記錄為新的α、β、δ，而不是與上次迭代的α、β、δ相比較擇優(yōu)。精英個(gè)體重選策略既保留了精英策略提高求解效率的優(yōu)點(diǎn)，又能保留種群多樣性、減少對經(jīng)驗(yàn)的依賴，降低陷入局部最優(yōu)的風(fēng)險(xiǎn)。

改進(jìn)后的算法流程如圖3所示。

圖3 改進(jìn)灰狼算法流程圖

3 仿真實(shí)驗(yàn)

為了驗(yàn)證本文提出的兩種改進(jìn)策略的有效性，從文獻(xiàn)[8]中選取國際上通用的9 個(gè)經(jīng)典基準(zhǔn)測試函數(shù)進(jìn)行仿真實(shí)驗(yàn)，將本文提出的改進(jìn)灰狼算法與標(biāo)準(zhǔn)灰狼算法、其他文獻(xiàn)提出的改進(jìn)灰狼算法以及其他算法分別進(jìn)行比較。測試函數(shù)如表1所示，其中F1～F6為單峰值函數(shù)，用于測試算法的求解精度和收斂速度，F(xiàn)7～F9 是多峰值函數(shù)，用于測試算法的全局搜索能力。

實(shí)驗(yàn)運(yùn)行環(huán)境為Intel Corei5-7200u CPU，主頻2.50 GHz，內(nèi)存8 GB，Win10 64 位操作系統(tǒng)，運(yùn)行軟件為Python 3.7。為保證無偏性，總迭代次數(shù)設(shè)置為500次。為排除隨機(jī)性的影響，所有實(shí)驗(yàn)獨(dú)立運(yùn)行30次，取平均值和標(biāo)準(zhǔn)差作為算法性能的度量標(biāo)準(zhǔn)，平均值用于衡量算法的求解精度，標(biāo)準(zhǔn)差用于衡量算法魯棒性。平均值和標(biāo)準(zhǔn)差的最優(yōu)值加粗展示。

3.1 與標(biāo)準(zhǔn)GWO算法的比較

為測試改進(jìn)策略在不同維度下的改進(jìn)效果，分別比較30 維和100 維情況下使用本文提出的改進(jìn)策略的灰狼算法與標(biāo)準(zhǔn)GWO的尋優(yōu)性能，測試結(jié)果分別如表2～5所示。其中EGWO-1是使用本文2.1節(jié)的非線性收斂因子策略的灰狼算法，EGWO-2 是使用本文2.2 節(jié)的重選精英個(gè)體策略的灰狼算法，EGWO 是綜合使用本文2.1和2.2節(jié)策略的灰狼算法。

表2 展示了30 維下4 種算法測試結(jié)果的平均值。從表中可看出，與標(biāo)準(zhǔn)GWO的求解結(jié)果相比，EGWO-1對函數(shù)F1、F2、F3、F4、F8 的求解精度明顯提升，對函數(shù)F5、F6、F7、F9 的尋優(yōu)性能沒有明顯改進(jìn)。EGWO-2 對函數(shù)F5、F6、F9 的求解精度沒有無明顯改進(jìn)，對另外6個(gè)函數(shù)的求解精度有明顯提升。EGWO 對每個(gè)函數(shù)的求解精確性都是4種算法中最優(yōu)的，其中對函數(shù)F5、F6、F9 的求解精度略優(yōu)于GWO，對其他6 個(gè)函數(shù)的求解結(jié)果明顯優(yōu)于GWO。

表1 標(biāo)準(zhǔn)測試函數(shù)

表2 30維下4種算法測試結(jié)果平均值比較

表3 30維下4種算法測試結(jié)果標(biāo)準(zhǔn)差比較

表4 100維下4種算法測試結(jié)果平均值比較

表5 100維下4種算法測試結(jié)果標(biāo)準(zhǔn)差比較

表3為30維下4種算法測試結(jié)果的標(biāo)準(zhǔn)差。EGWO-1對函數(shù)F1、F2、F3、F4、F8求解的魯棒性明顯優(yōu)于GWO，對其他函數(shù)求解的魯棒性與GWO無明顯差異。EGWO-2對函數(shù)F1、F2、F3、F4、F7的求解魯棒性明顯提升，對其他4 個(gè)函數(shù)的魯棒性無明顯改進(jìn)。EGWO 對每個(gè)函數(shù)的魯棒性都是4 種算法中最高的，其中對函數(shù)F1、F2、F3、F4、F7、F8求解的魯棒性較GWO提升明顯。

表4 是100 維下4 種算法測試結(jié)果的平均值。EGWO-1 對函數(shù)F1、F2、F8 的求解結(jié)果明顯優(yōu)于標(biāo)準(zhǔn)GWO，對于其他6個(gè)測試函數(shù)的求解結(jié)果的精確性較標(biāo)準(zhǔn)GWO無明顯差異。EGWO-2僅對函數(shù)F3、F4的求解精確度較標(biāo)準(zhǔn)GWO 有明顯提升，對另外7 個(gè)函數(shù)的求解結(jié)果與標(biāo)準(zhǔn)GWO 相當(dāng)。EGWO 對每個(gè)函數(shù)的求解精度仍是4 種算法中最優(yōu)的，在函數(shù)F1、F2、F4、F7、F8、F9 上的求解結(jié)果明顯優(yōu)于標(biāo)準(zhǔn)GWO，對另外3 個(gè)函數(shù)的結(jié)果略優(yōu)于GWO。

表5為100維下4算法測試結(jié)果的標(biāo)準(zhǔn)差。相較于GWO，EGWO-1 對函數(shù)F1、F2、F8 的魯棒性明顯改進(jìn)，對其他6個(gè)函數(shù)無明顯改進(jìn)。EGWO-2僅對函數(shù)F3、F4的求解魯棒性有明顯提升，對另外7個(gè)函數(shù)的魯棒性與GWO相當(dāng)。EGWO對每個(gè)函數(shù)的魯棒性都優(yōu)于另外3種算法，其中對函數(shù)F1、F2、F3、F4、F7、F8、F9 的魯棒性明顯優(yōu)于GWO，對函數(shù)F5、F6 的魯棒性略優(yōu)于GWO。值得特別說明的是，對于函數(shù)F7和F9，單獨(dú)使用非線性收斂因子策略或精英個(gè)體重選策略對求解結(jié)果都較GWO無明顯改進(jìn)，綜合使用兩個(gè)策略的EGWO卻能精準(zhǔn)收斂到最優(yōu)值0，較GWO有明顯提升。

圖4 4種算法對4個(gè)函數(shù)的收斂曲線

表6 6種算法測試結(jié)果平均值比較

綜合30維和100維的測試結(jié)果來看，兩種改進(jìn)策略對算法的尋優(yōu)結(jié)果的準(zhǔn)確性和魯棒性都有所提升，綜合使用兩種改進(jìn)策略的EGWO對算法尋優(yōu)性能提升最顯著。30維下的測試結(jié)果優(yōu)于100維下的測試結(jié)果，因此本文提出的EGWO更適用于低維函數(shù)的求解。

為了更加直觀地反映4種算法的性能，給出30維下4種算法在測試函數(shù)F1-F4上的收斂曲線，見圖4。從圖中可以看出，在迭代前期4 種算法的收斂速度基本一致，迭代后期EGWO-1 、EGWO-2 和EGWO 的收斂速度明顯快于標(biāo)準(zhǔn)GWO，求解精度也優(yōu)于標(biāo)準(zhǔn)GWO，其中EGWO收斂速度和精確度最優(yōu)。

3.2 與不同改進(jìn)策略GWO算法的比較

為了進(jìn)一步測試本文提出的EGWO算法的尋優(yōu)性能，將EGWO 與其他專家學(xué)者提出的改進(jìn)灰狼算法進(jìn)行比較。測試結(jié)果如表6和表7所示，其中NGWO為文獻(xiàn)[12]提出的非線性收斂灰狼優(yōu)化算法，GWO-EPD 為文獻(xiàn)[13]提出的進(jìn)化種群動態(tài)灰狼算法，GWO-Fuzzy為文獻(xiàn)[14]提出的模糊層次算子灰狼算法，IGWO 為文獻(xiàn)[15]提出的動態(tài)權(quán)重灰狼算法，HGWO 為文獻(xiàn)[16]提出的差分進(jìn)化灰狼算法。

表7 6種算法測試結(jié)果標(biāo)準(zhǔn)差比較

表6展示了6種算法測試結(jié)果的平均值。與NGWO相比，對函數(shù)F5 的求解精確度，EGWO 略低于NGWO，對函數(shù)F9，NGWO 可以收斂到理論最優(yōu)值0，而EGWO不能，對函數(shù)F7，兩種算法都能收斂到理論最優(yōu)值0，對其他函數(shù)EGWO的求解精確度優(yōu)于NGWO。與GWOEPD、GWO-Fuzzy、IGWO 和HGWO 相比，EGWO 對每個(gè)函數(shù)的求解精確性都是最優(yōu)的，其中對函數(shù)F1、F2、F3、F4、F7、F8、F9求解精度明顯優(yōu)于另外4種對比算法。

表7 展示了6 種算法測試結(jié)果的標(biāo)準(zhǔn)差。相較于NGWO，EGWO和NGWO對函數(shù)F7的魯棒性都達(dá)到最優(yōu)值0，對函數(shù)F9 魯棒性低于NGWO，對另外7 個(gè)函數(shù)的魯棒性高于NGWO。與GWO-EPD、GWO-Fuzzy、IGWO 和HGWO 相比，EGWO 對每個(gè)函數(shù)的求解魯棒性都是最優(yōu)的，其中，對函數(shù)F1、F2、F3、F4、F7、F8 的魯棒性明顯優(yōu)于其他4種對比算法。

綜合求解的精確性和魯棒性來看，6 種算法中結(jié)果最優(yōu)的是EGWO，其次是NGWO，而NGWO 和EGWO都將GWO 的收斂參數(shù)調(diào)整為非線性收斂因子，這也進(jìn)一步說明前期收斂速度慢后期收斂速度快的收斂方式更適用于灰狼算法。

3.3 與其他算法的比較

為了進(jìn)一步測試本文提出的EGWO算法的尋優(yōu)性能，將EGWO 與PSO、GSA、DE、FEP 這4 種算法進(jìn)行對比，測試結(jié)果的平均值和標(biāo)準(zhǔn)差分別如表8和表9所示。

與DE 相比，對函數(shù)F4、F5、F9，DE 在500 次迭代內(nèi)收斂到理論最優(yōu)值為0，EGWO的求解結(jié)果的精確性和魯棒性差于DE，尤其是對F5，EGWO 的求解結(jié)果遠(yuǎn)遠(yuǎn)差于DE。對函數(shù)F1、F2、F3、F6、F7、F8，EGWO 的求解結(jié)果的精確性和魯棒性則優(yōu)于DE，其中，對函數(shù)F1、F2、F7、F8 的尋優(yōu)結(jié)果，EGWO 明顯優(yōu)于DE。對函數(shù)F3、F6的求解精確性和魯棒性略優(yōu)于DE。

與FEP 相比，EGWO 對函數(shù)F5 的求解精確度低于FEP，對其他8 個(gè)函數(shù)的求解精確度和魯棒性都明顯優(yōu)于FEP。

與PSO 和GSA 相比，EGWO 對9 個(gè)測試函數(shù)的求解結(jié)果的精確性和魯棒性都明顯遠(yuǎn)優(yōu)于PSO和GSA。

綜合表2至表9的結(jié)果分析，從表2至表5來看本文提出的非線性收斂因子調(diào)整策略和精英個(gè)體重選策略都能有效地提升GWO 的算法性能，綜合使用兩種策略對算法性能的改進(jìn)效果最明顯，在30維和100維兩種情況下EGWO都能得到比標(biāo)準(zhǔn)GWO更優(yōu)的結(jié)果，但在30維下尋優(yōu)結(jié)果更好，因此，EGWO 更適用于低維函數(shù)求解。表6、表7 中將本文的EGWO 與5 種其他專家學(xué)者提出的改進(jìn)灰狼算法進(jìn)行對比，結(jié)果顯示EGWO 的尋優(yōu)性能優(yōu)于其他改進(jìn)灰狼算法。表8、表9 中將EGWO與PSO、GSA、DE、FEP 這4 種算法進(jìn)行對比，結(jié)果顯示EGWO略優(yōu)于DE，明顯優(yōu)于PSO、GSA和FEP。

表8 5種算法測試結(jié)果平均值比較

表9 5種算法測試結(jié)果標(biāo)準(zhǔn)差比較

4 結(jié)語

本文提出了一種改進(jìn)灰狼算法，EGWO具有非線性收斂因子調(diào)整策略和精英個(gè)體重選策略，以針對灰狼算法求解精度較低、后期收斂速度較慢、易陷入局部最優(yōu)的缺點(diǎn)進(jìn)行算法性能改善。非線性收斂因子策略可以平衡算法的全局搜索能力和局部開發(fā)能力，精英個(gè)體重選策略可以擴(kuò)大搜索范圍，降低陷入局部最優(yōu)的風(fēng)險(xiǎn)。通過在6個(gè)單峰基準(zhǔn)測試函數(shù)和3個(gè)多峰基準(zhǔn)測試函數(shù)上的仿真實(shí)驗(yàn)，與基本灰狼優(yōu)化算法、文獻(xiàn)提出的5 種改進(jìn)灰狼算法和4種其他算法進(jìn)行對比，實(shí)驗(yàn)結(jié)果表明本文提出的EGWO 算法具有更快的收斂速度、更高的求解精度和更好的全局尋優(yōu)性能。

在實(shí)驗(yàn)中也發(fā)現(xiàn)了EGWO的兩個(gè)缺點(diǎn)：（1）EGWO對低維函數(shù)的實(shí)驗(yàn)結(jié)果較好，而對高維函數(shù)實(shí)驗(yàn)結(jié)果不太好；（2）運(yùn)行時(shí)間長于其他對比算法。未來研究將針對EGWO的這兩個(gè)缺點(diǎn)進(jìn)行改進(jìn)，開發(fā)出適用于高維函數(shù)且運(yùn)行時(shí)間更短的算法，以提高算法的實(shí)用價(jià)值，并將算法應(yīng)用到運(yùn)籌、調(diào)度、深度學(xué)習(xí)等領(lǐng)域，以驗(yàn)證算法的實(shí)用性。