重選精英個體的非線性收斂灰狼優化算法

黎素涵，葉春明

上海理工大學 管理學院，上海200093

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

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

1 灰狼優化算法

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

圖1 灰狼等級結構

灰狼種群以團隊跟蹤、包圍的模式狩獵，因此種群內部的等級制度使得捕獵非常有序而高效，狼群在α的帶領下，由β、δ進攻獵物，ω負責輔助包圍獵物，最終狼群將從各個方向把獵物圍住并捕殺。

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

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

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

狼群跟蹤獵物的數學模型為：

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

2 灰狼優化算法改進策略

2.1 收斂因子非線性調整策略

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

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

圖2 收斂因子變化圖

2.2 精英個體重選策略

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

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

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

改進后的算法流程如圖3所示。

圖3 改進灰狼算法流程圖

3 仿真實驗

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

實驗運行環境為Intel Corei5-7200u CPU，主頻2.50 GHz，內存8 GB，Win10 64 位操作系統，運行軟件為Python 3.7。為保證無偏性，總迭代次數設置為500次。為排除隨機性的影響，所有實驗獨立運行30次，取平均值和標準差作為算法性能的度量標準，平均值用于衡量算法的求解精度，標準差用于衡量算法魯棒性。平均值和標準差的最優值加粗展示。

3.1 與標準GWO算法的比較

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

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

表1 標準測試函數

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

表3 30維下4種算法測試結果標準差比較

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

表5 100維下4種算法測試結果標準差比較

表3為30維下4種算法測試結果的標準差。EGWO-1對函數F1、F2、F3、F4、F8求解的魯棒性明顯優于GWO，對其他函數求解的魯棒性與GWO無明顯差異。EGWO-2對函數F1、F2、F3、F4、F7的求解魯棒性明顯提升，對其他4 個函數的魯棒性無明顯改進。EGWO 對每個函數的魯棒性都是4 種算法中最高的，其中對函數F1、F2、F3、F4、F7、F8求解的魯棒性較GWO提升明顯。

表4 是100 維下4 種算法測試結果的平均值。EGWO-1 對函數F1、F2、F8 的求解結果明顯優于標準GWO，對于其他6個測試函數的求解結果的精確性較標準GWO無明顯差異。EGWO-2僅對函數F3、F4的求解精確度較標準GWO 有明顯提升，對另外7 個函數的求解結果與標準GWO 相當。EGWO 對每個函數的求解精度仍是4 種算法中最優的，在函數F1、F2、F4、F7、F8、F9 上的求解結果明顯優于標準GWO，對另外3 個函數的結果略優于GWO。

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

圖4 4種算法對4個函數的收斂曲線

表6 6種算法測試結果平均值比較

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

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

3.2 與不同改進策略GWO算法的比較

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

表7 6種算法測試結果標準差比較

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

表7 展示了6 種算法測試結果的標準差。相較于NGWO，EGWO和NGWO對函數F7的魯棒性都達到最優值0，對函數F9 魯棒性低于NGWO，對另外7 個函數的魯棒性高于NGWO。與GWO-EPD、GWO-Fuzzy、IGWO 和HGWO 相比，EGWO 對每個函數的求解魯棒性都是最優的，其中，對函數F1、F2、F3、F4、F7、F8 的魯棒性明顯優于其他4種對比算法。

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

3.3 與其他算法的比較

為了進一步測試本文提出的EGWO算法的尋優性能，將EGWO 與PSO、GSA、DE、FEP 這4 種算法進行對比，測試結果的平均值和標準差分別如表8和表9所示。

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

與FEP 相比，EGWO 對函數F5 的求解精確度低于FEP，對其他8 個函數的求解精確度和魯棒性都明顯優于FEP。

與PSO 和GSA 相比，EGWO 對9 個測試函數的求解結果的精確性和魯棒性都明顯遠優于PSO和GSA。

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

表8 5種算法測試結果平均值比較

表9 5種算法測試結果標準差比較

4 結語

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

在實驗中也發現了EGWO的兩個缺點：（1）EGWO對低維函數的實驗結果較好，而對高維函數實驗結果不太好；（2）運行時間長于其他對比算法。未來研究將針對EGWO的這兩個缺點進行改進，開發出適用于高維函數且運行時間更短的算法，以提高算法的實用價值，并將算法應用到運籌、調度、深度學習等領域，以驗證算法的實用性。