一種混合策略改進(jìn)的灰狼優(yōu)化算法

倪 靜，秦 斌，曾凡龍

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

0 引言

灰狼優(yōu)化算法（Grey Wolf Optimizer，GWO）是Mirjalili等［1］提出的一種群體智能算法。GWO 算法具有結(jié)構(gòu)簡單、概念清晰且易實(shí)現(xiàn)等特性，已廣泛應(yīng)用于車間調(diào)度［2-3］、路徑優(yōu)化［4］、社會網(wǎng)絡(luò)影響力最大化［5］、參數(shù)尋優(yōu)［6］和聚類優(yōu)化［7］等問題。盡管GWO 算法得到了廣泛應(yīng)用，但是仍存在一些不足。針對標(biāo)準(zhǔn)GWO 算法的不足，目前國內(nèi)外學(xué)者們主要針對GWO 算法的種群初始化過程、控制參數(shù)和搜索機(jī)制等幾個(gè)方面進(jìn)行改進(jìn)，進(jìn)而提高GWO 算法的尋優(yōu)性能。在種群初始化的優(yōu)化方面，文獻(xiàn)［8］利用佳點(diǎn)集對算法種群進(jìn)行初始化，保證初始種群個(gè)體分布均勻，為算法的全局尋優(yōu)奠定基礎(chǔ)；文獻(xiàn)［9］采用高斯分布對種群進(jìn)行初始化，使得種群分布更加均勻，通過實(shí)驗(yàn)驗(yàn)證了該策略可以提高算法求解精度；在控制參數(shù)調(diào)整方面，文獻(xiàn)［10］受粒子群優(yōu)化算法啟發(fā)，提出一種非線性遞減收斂因子更新公式；文獻(xiàn)［11］在基本灰狼優(yōu)化算法的基礎(chǔ)上，通過其動(dòng)態(tài)縮放因子和交叉概率因子提升算法尋優(yōu)能力；在位置更新改進(jìn)方面，文獻(xiàn)［12］分析了灰狼優(yōu)化算法后期個(gè)體均向決策層區(qū)域聚集，從而導(dǎo)致群體多樣性較差的問題，并提出一種基于光學(xué)透鏡成像原理的反向?qū)W習(xí)策略以避免算法陷入局部最優(yōu)；文獻(xiàn)［13］受差分進(jìn)化和粒子群優(yōu)化算法啟發(fā)，構(gòu)建一個(gè)修改的個(gè)體位置更新方程以增強(qiáng)算法探索能力，并提出一種控制參數(shù)隨機(jī)動(dòng)態(tài)調(diào)整策略，增強(qiáng)算法全局搜索能力；文獻(xiàn)［14］為協(xié)調(diào)算法的全局探索和局部開發(fā)能力，設(shè)計(jì)了一種基于正切三角函數(shù)描述的非線性動(dòng)態(tài)變化控制參數(shù)，并給出了一種新的個(gè)體位置更新公式，以加快算法收斂速度。此外，將其他智能算法與灰狼算法結(jié)合也成為一種新的研究思路，學(xué)者們已經(jīng)將蝙蝠算法［15］、鯨魚算法［16］和布谷鳥算法［17］等與GWO 結(jié)合，以改善算法尋優(yōu)性能。雖然國內(nèi)外學(xué)者對GWO 算法進(jìn)行了大量改進(jìn)研究，但是其初始種群不均勻、全局勘探與局部開發(fā)能力不平衡和易陷入局部最優(yōu)等問題依然存在。

本文在已有研究基礎(chǔ)上提出了一種多策略改進(jìn)的灰狼優(yōu)化算法（Improved Grey Wolf Optimization Algorithm，IG?WO），采用反向?qū)W習(xí)策略產(chǎn)生了更加均勻的初始種群，改進(jìn)傳統(tǒng)灰狼優(yōu)化算法在初始化過程中種群不均勻的問題。針對算法全局勘探與局部開發(fā)能力不平衡問題，采用非線性控制因子平衡算法全局搜索能力和局部搜索能力。為進(jìn)一步提高算法全局搜索能力，在位置更新策略中引入萊維飛行策略，擴(kuò)大搜索范圍。通過12 個(gè)標(biāo)準(zhǔn)測試函數(shù)仿真驗(yàn)證改進(jìn)算法的準(zhǔn)確性和有效性，仿真結(jié)果表明，本文改進(jìn)的算法具有良好的收斂精度、速度和穩(wěn)定性。

1 混合策略改進(jìn)的灰狼優(yōu)化算法

1.1 基于反向?qū)W習(xí)策略初始化種群

標(biāo)準(zhǔn)的GWO 算法是基于隨機(jī)性產(chǎn)生的初始種群，這可能使得算法的初始種群分布不均勻，難以保證種群的多樣性。而算法的初始解對算法全局搜索起到了至關(guān)重要的作用，種群的多樣性程度也極大地影響著算法搜索性能。文獻(xiàn)［18］表明，反向解有50%的可能性比當(dāng)前解更加靠近最優(yōu)解，因此，本文采用反向?qū)W習(xí)策略產(chǎn)生初始種群。

首先，在解空間內(nèi)對種群進(jìn)行隨機(jī)初始化，產(chǎn)生一組隨機(jī)種群，種群內(nèi)的每個(gè)個(gè)體xi,j，i∈[1,D]代表維度，j∈[1,n]代表種群個(gè)數(shù)。然后，對每個(gè)個(gè)體采用反向?qū)W習(xí)策略，即采用式（8）找到反向個(gè)體構(gòu)造一組反向解，最后將兩組初始解合并，選取適應(yīng)度前n的個(gè)體作為初始種群。

1.2 控制參數(shù)的非線性調(diào)整策略

Fig.1 Convergence curve of parameters圖1 參數(shù)對比曲線

1.3 位置更新策略改進(jìn)

在標(biāo)準(zhǔn)GWO 算法中，只有α狼、β狼和δ狼的位置影響下一代位置，下一代種群過度向全局最優(yōu)“靠攏”，很容易出現(xiàn)局部尋優(yōu)。為了進(jìn)一步增強(qiáng)算法的全局搜索能力并加快收斂速度，在原始位置更新策略基礎(chǔ)上引入萊維飛行策略。萊維飛行是一種隨機(jī)游動(dòng)的搜索策略，能夠擴(kuò)大搜索范圍，防止算法陷入局部尋優(yōu)。引入萊維飛行的位置更新策略如下：

其中，⊕為點(diǎn)對點(diǎn)乘法，a0=0.01，sign[rand-1/2]的取值為-1，0 和1。萊維飛行的步長服從萊維分布：

其中，s是飛行路徑，可由Mantega 算法計(jì)算如下：

θ的取值范圍一般為（1，2），本文取值1.5，μ和u是符合正態(tài)分布的隨機(jī)數(shù)：u～N

1.4 算法流程

將增加以上改進(jìn)策略的灰狼優(yōu)化算法簡寫為IGWO，算法流程描述如下：

Step1：設(shè)置算法參數(shù)，包括種群數(shù)目n，最大迭代次數(shù)max_iter；

Step2：采用反向?qū)W習(xí)策略進(jìn)行種群初始化；

Step3：計(jì)算狼群個(gè)體的適應(yīng)度值，選取適應(yīng)度最優(yōu)的個(gè)體、次優(yōu)個(gè)體、第三優(yōu)個(gè)體為，并且分別記錄其位置；

Step4：采用式（3）更新灰狼個(gè)體位置；

2 實(shí)驗(yàn)及分析

實(shí)驗(yàn)環(huán)境為Inter（R）Core（TM）i5-5200CPU，主頻2.20GHz 和內(nèi)存4GB 的PC 機(jī)，操作系統(tǒng)采用64 位的Win?dows 10，編程語言采用MATLAB2018B。

為了驗(yàn)證IGWO 算法求解性能的優(yōu)越性，選取12 基準(zhǔn)測試函數(shù)測試算法性能。測試函數(shù)如下：Sephere（F1）、Schwefel’s Problem 2.22（F2）、Schwefel’s Problem 1.2（F3）、Generalized Rosenbrock’s（F4）、Step（F5）、Quartic Function i.e.Niose（F6）、Generalized Rastrigin’s（F7）、Generalized Grie?wank（F8）、Generalized Penalized（F9）、Levy Function N.3（F10）、Shekel’s Foxholes（F11）、Kowalik’s（F12）。其中F1～F6 為單峰值函數(shù)，F(xiàn)7～F10 是多峰值函數(shù)，F(xiàn)11 和F12表示固定低維函數(shù)。首先將IGWO 算法與差分進(jìn)化算法（DE）、布谷鳥算法（CS）、粒子群算法（PSO）、基本灰狼算法（GWO）進(jìn)行比較，驗(yàn)證IGWO 的性能優(yōu)越性，然后將本文改進(jìn)算法與其他改進(jìn)灰狼算法進(jìn)行對比，進(jìn)一步驗(yàn)證算法的求解性能。

2.1 與經(jīng)典算法比較

為了測試算法性能，將IGWO 算法與DE、CS、PSO、GWO 作對比，在維度D=30 下分別對每個(gè)函數(shù)獨(dú)立運(yùn)行30次（其中F11 搜索維度為2 維，F(xiàn)12 搜索維度為4 維）。選取平均精度Ave 評價(jià)算法的搜索精度，選取標(biāo)準(zhǔn)差Std 評價(jià)算法的魯棒性，并通過觀察算法的收斂曲線比較算法的收斂速度。幾種算法的基本參數(shù)設(shè)置如表1 所示。

Table 1 Algorithm parameter settings表1 算法參數(shù)設(shè)置

表2 給出了IGWO 算法與各經(jīng)典優(yōu)化算法運(yùn)行不同測試函數(shù)后的平均值和標(biāo)準(zhǔn)差，圖2 為不同函數(shù)下的尋優(yōu)收斂曲線。從仿真結(jié)果可以看出，改進(jìn)的灰狼算法IGWO 在12 組獨(dú)立實(shí)驗(yàn)中均一致收斂到全局最優(yōu)解，尤其是求解函數(shù)F7、F8、F11、F12 時(shí)，IGWO 均能收斂到理論最優(yōu)值，而其他經(jīng)典優(yōu)化算法均不能收斂到理論最優(yōu)值。對于F1、F2、F3，與各經(jīng)典的優(yōu)化算法相比，IGWO 算法的求解精度和魯棒性都具有較大優(yōu)勢，并且能夠達(dá)到函數(shù)給定的收斂精度。例如，對于F1，IGWO 的平均值和標(biāo)準(zhǔn)差分別約是GWO 算法的約4 倍、DE 算法的29 倍、CS 算法的113 倍、PSO 算法的28 倍，求解精度和求解穩(wěn)定性優(yōu)勢明顯。對于F4、F5、F6、F9 和F10，IGWO 算法相比于其他優(yōu)化算法的求解精度和求解穩(wěn)定性也有一定優(yōu)勢。從圖2 中可以明顯看出，相比于DE、CS 和PSO，IGWO 算法求解速度最快，在所有測試函數(shù)上都比其他算法更快找到最優(yōu)解位置。雖然GWO 算法也能取得很好的收斂效果，但是仍不及IGWO 算法的收斂性能明顯，IGWO 算法較傳統(tǒng)GWO 算法明顯提升了收斂速度。因此，仿真結(jié)果表明，改進(jìn)后的算法無論是收斂速度還是收斂精度，相對于基本灰狼算法都起到一定的改善效果，同時(shí)相對于其他經(jīng)典優(yōu)化算法都具有顯著優(yōu)勢。

Table 2 Performance comparison with classic algorithms表2 與經(jīng)典算法性能比較

Fig.2 Algorithm convergence圖2 算法收斂

2.2 與其他改進(jìn)算法比較

為了進(jìn)一步測試IGWO 算法的尋優(yōu)性能，將IGWO 算法與其他參考文獻(xiàn)中改進(jìn)的灰狼算法［19-21］進(jìn)行對比。其中，mGWO 為文獻(xiàn)［19］提出的非線性收斂的灰狼優(yōu)化算法，EGWO 為文獻(xiàn)［20］提出的進(jìn)化種群動(dòng)態(tài)灰狼算法，Ex-GWO 為文獻(xiàn)［21］提出的改進(jìn)位置更新方式的改進(jìn)灰狼算法。通過比較算法最優(yōu)解的均值以及標(biāo)準(zhǔn)差測試改進(jìn)灰狼優(yōu)化算法的尋優(yōu)性能，對比結(jié)果如表3 所示。

平均值用于反映算法求解尋優(yōu)精度，由表3 的平均值數(shù)據(jù)可知，IGWO 算法僅測試函數(shù)F6 的優(yōu)化指標(biāo)劣于mG?WO 和Ex-GWO 算法，其余測試函數(shù)優(yōu)化求解效果均優(yōu)于表中其他3 種改進(jìn)的灰狼優(yōu)化算法。對于F1、F2、F3、F7、F8 函數(shù)，IGWO 得到的各函數(shù)求解的平均值遠(yuǎn)遠(yuǎn)小于mG?WO、EGWO 和Ex-GWO，即IGWO 算法的求解精度遠(yuǎn)遠(yuǎn)高于mGWO、EGWO 和Ex-GWO。對于函數(shù)F4、F5、F9、F10、F11、F12，IGWO 相對于mGWO、EGWO 和Ex-GWO 算法也具有較高的求精精度。同時(shí)，標(biāo)準(zhǔn)差用于反映算法求解尋優(yōu)的穩(wěn)定性，由表3 的標(biāo)準(zhǔn)差數(shù)據(jù)對比可以看出，IGWO 算法對12 個(gè)測試函數(shù)的標(biāo)準(zhǔn)差值小于其他改進(jìn)的灰狼算法，說明IGWO 算法的穩(wěn)定性相對于mGWO、EGWO 和Ex-GWO 也較好。因此，對比其他改進(jìn)的灰狼優(yōu)化算法，IGWO算法在尋優(yōu)性能上依然具有優(yōu)勢。

Table 3 Performance comparison with other improved gray wolf algorithms表3 與其他改進(jìn)灰狼算法性能比較

3 結(jié)語

本文在標(biāo)準(zhǔn)灰狼優(yōu)化算法的基礎(chǔ)上，引入了反向?qū)W習(xí)策略、非線性控制因子和萊維飛行策略對標(biāo)準(zhǔn)的灰狼優(yōu)化算法進(jìn)行改進(jìn)，提出了一種混合策略改進(jìn)的灰狼優(yōu)化算法。由12 個(gè)標(biāo)準(zhǔn)測試函數(shù)的仿真結(jié)果可知，IGWO 在尋優(yōu)精度、穩(wěn)定性和收斂速度方面不僅與經(jīng)典的優(yōu)化算法相比具有一定優(yōu)勢，同時(shí)與一些改進(jìn)的灰狼優(yōu)化算法相比也有一定優(yōu)勢。但是，本文算法未在實(shí)際問題中得到進(jìn)一步驗(yàn)證，未來研究中，會將改進(jìn)的算法應(yīng)用于實(shí)際問題求解，驗(yàn)證算法實(shí)用性。