雙收斂因子策略下的改進(jìn)灰狼優(yōu)化算法

歐 云，周愷卿，尹鵬飛，劉雪薇

（1.吉首大學(xué) 通信與電子工程學(xué)院，湖南 吉首 416000；2.吉首大學(xué) 教務(wù)處，湖南 吉首 416000；3.吉首大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，湖南 吉首 416000）

0 引言

群智能算法是一種模仿生物群體智慧的概率搜索算法，具有強(qiáng)魯棒性、易擴(kuò)充、易實(shí)現(xiàn)等特點(diǎn)，已被廣泛應(yīng)用于研究領(lǐng)域和實(shí)際場景［1］?；依莾?yōu)化（Grey Wolf Optimizer，GWO）［2］算法作為近幾年新起的群智能算法之一，因具有參數(shù)少、易實(shí)現(xiàn)、穩(wěn)定性強(qiáng)等特點(diǎn)，在解決特征選擇、神經(jīng)網(wǎng)絡(luò)優(yōu)化、路徑規(guī)劃等優(yōu)化問題時(shí)表現(xiàn)出了良好的性能；但該算法也存在求解精度不高、收斂速度慢、易陷入局部最優(yōu)等缺陷。

針對以上不足，研究者從初始化種群、收斂因子、位置更新方法、設(shè)置跳出局部機(jī)制等方面改進(jìn)GWO。王振東等［3］針對入侵檢測存在的初始值不確定性及早熟的問題，利用混沌映射初始化種群、設(shè)計(jì)非線性收斂因子以及動態(tài)權(quán)重策略等手段優(yōu)化GWO，并將它用于解決反向傳播（Back Propagation，BP）神經(jīng)網(wǎng)絡(luò)因初始化權(quán)值和閾值的隨機(jī)性而導(dǎo)致的陷入局部最優(yōu)問題；李長安等［4］針對GWO 收斂速度慢、尋優(yōu)精度不高等問題，采用sin 映射初始化種群，引入合作競爭機(jī)制及修正自適應(yīng)權(quán)重等策略改進(jìn)算法，提高了算法收斂速度和精度；Joshi 等［5］針對GWO 在探索和開發(fā)之間的不平衡問題，將每次迭代中適應(yīng)度值最優(yōu)解作為頭狼，提出了一種增強(qiáng)型灰狼優(yōu)化（Enhanced Grey Wolf Optimizer，EGWO）算法來提升前期探索階段的收斂速度；Heidari 等［6］針對GWO 在某些問題求解中因種群的多樣性不足而易陷入局部最優(yōu)等問題，提出了一種基于α 和β 雙狼引領(lǐng)、萊維（Levy）飛行隨機(jī)更新、貪婪選擇等策略的灰狼算法LGWO（Levy-embedded Grey Wolf Optimizer）來提升算法全局尋優(yōu)能力。王敏等［7］針對灰狼優(yōu)化算法存在的尋優(yōu)精度不高和易早熟等缺點(diǎn)，提出了一種新型灰狼優(yōu)化（Novel Grey Wolf Optimizer，NGWO）算法，采用了如下策略：首先，在初始化種群時(shí)采用反向?qū)W習(xí)策略和隨機(jī)均勻分布進(jìn)行優(yōu)化；其次，通過調(diào)整收斂因子平衡全局勘探和局部開發(fā)能力；最后，利用變異算子避免算法陷入局部最優(yōu)。張文勝等［2］提出了一種采用Sigmoid 函數(shù)作為收斂因子，以粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法的慣性權(quán)重因子作為位置更新權(quán)重的灰狼算法TGWO（Transformed Grey Wolf Optimizer）；Yu 等［8］提出一種基于對立學(xué)習(xí)的灰狼優(yōu)化器（Oppositionbased learning Grey Wolf Optimizer，OGWO），在不增加計(jì)算復(fù)雜度情況下，以跳躍率方式將對立學(xué)習(xí)與GWO 相結(jié)合，提升了算法在求解復(fù)雜多模態(tài)函數(shù)方面的性能。針對灰狼算法在競選三頭領(lǐng)導(dǎo)狼期間，其他落選狼必須等待競選完成后才能更新所導(dǎo)致的收斂慢等問題，Zhang 等［9］提出一種改進(jìn)的動態(tài)灰狼優(yōu)化（improved Dynamic Grey Wolf Optimizer，DGWO）算法，當(dāng)前搜索狼在完成自身或前一個搜索狼與領(lǐng)先狼的比較后，就更新它的位置，這種在競選期間動態(tài)更新搜索狼的位置策略，提高了算法收斂速度。針對灰狼算法易早熟等缺陷，張佳琦等［10］提出一種改進(jìn)的灰狼優(yōu)化算法（Improved Grey Wolf Optimizer，IGWO），首先利用混沌Tent 映射策略初始化種群，提升種群的多樣性和分布均勻性，然后采用非線性收斂因子、差分進(jìn)化更新迭代等手段平衡算法的全局勘探和局部開發(fā)能力，并降低出現(xiàn)局部最優(yōu)概率；劉繼忠等［11］為避免全局搜索時(shí)陷入局部最優(yōu)，提出了動態(tài)雙子群策略改進(jìn)的灰狼優(yōu)化（improved Grey Wolf Optimizer based on Dynamic Double-subgroup strategy，DDGWO）算法。其他類似改進(jìn)思路可參閱文獻(xiàn)［12-15］。上述研究表明，對GWO 的改進(jìn)思路可以歸納為以下幾點(diǎn)：

1）優(yōu)化初始化種群，確保種群的均勻分布性和多樣性。

2）調(diào)整收斂因子，平衡算法全局勘探和局部開發(fā)能力。

3）改進(jìn)更新方法，提升算法收斂速度和精度，避免陷入局部最優(yōu)。

受以上研究啟發(fā)，本文提出了基于雙頭狼引領(lǐng)的改進(jìn)灰狼優(yōu)化（Grey Wolf Optimization with Two Headed Wolves guide，GWO-THW）算法。首先引入混沌Cubic 映射初始化種群用以提升種群分布的均勻性和多樣性；然后根據(jù)平均適應(yīng)度值將狼群分為適應(yīng)度值較優(yōu)的捕獵狼和適應(yīng)度值較差的偵察狼，并設(shè)立雙頭狼分別帶領(lǐng)捕獵狼和偵察狼以不同的非線性收斂因子進(jìn)行狩獵；最后設(shè)計(jì)一種自適應(yīng)權(quán)重因子更新位置，提高收斂速度和精度。實(shí)驗(yàn)部分通過常用的基準(zhǔn)測試函數(shù)測試了算法改進(jìn)的可行性。

1 灰狼算法

灰狼優(yōu)化算法是2014 年Mirjalili 等［16］受灰狼群狩獵行為啟發(fā)而提出的一種群智能算法。GWO 首先將灰狼群當(dāng)成初始解種群，按灰狼社會等級制度，將當(dāng)前最優(yōu)解當(dāng)作α 狼，次優(yōu)解為β 狼，第三優(yōu)解為δ 狼，其余所有解為ω 狼，算法求解過程就是狼群的狩獵過程，具體模型如下。

1.1 包圍獵物過程

灰狼為了完成對獵物的包圍，需要根據(jù)獵物的大概位置計(jì)算出到獵物的距離，然后向獵物移動，計(jì)算公式如式（1）、（2）所示。

其中：t表示當(dāng)前迭代次數(shù)；X(t)表示第t次迭代灰狼個體位置向量；XP(t)表示第t次迭代獵物的位置向量；X(t+1)表示更新后灰狼個體位置向量；D表示灰狼個體與獵物之間的距離；A和C是參數(shù)控制向量，A用于調(diào)節(jié)灰狼個體移動的方向，C用于修正獵物位置，分別用式（3）和式（4）計(jì)算。

其中：r1、r2為（0，1）內(nèi)的隨機(jī)向量；a為迭代收斂因子，它的值由2 線性遞減到0，由式（5）確定。

其中：t表示當(dāng)前迭代次數(shù)；T表示總迭代次數(shù)。

1.2 捕獲獵物過程

在整個狩獵過程中，α 狼確定獵物位置，并一直向著獵物移動，β 狼和δ 狼跟隨α 狼追捕獵物并引導(dǎo)其他狼包圍獵物，其他狼向α 狼、β 狼、δ 狼移動，完成對獵物的包圍。移動公式如式（6）～（12）所示。

其中：A1、A2、A3由式（3）計(jì)算；C1、C2、C3由式（4）計(jì)算；Xα、Xβ、Xδ分別表示α 狼、β 狼、δ 狼的位置向量；式（12）為灰狼個體位置更新公式。

2 灰狼算法的改進(jìn)

GWO-THW 在標(biāo)準(zhǔn)GWO 的基礎(chǔ)上，從種群分布、收斂因子、位置更新權(quán)重、跳出局部最優(yōu)等方面進(jìn)行改進(jìn)。

2.1 初始化種群

在標(biāo)準(zhǔn)GWO 中，狼群位置分布越均勻，算法越易求得最優(yōu)解。相較于GWO 的隨機(jī)生成狼群初始位置策略，混沌映射由于它的隨機(jī)性、均勻性和多樣性等特點(diǎn)被廣泛應(yīng)用于智能算法中初始群體的生成。本文引用映射效果相對穩(wěn)定的改進(jìn)Cubic 混沌映射［17］實(shí)現(xiàn)狼群位置分布的初始化操作，映射函數(shù)如式（13）所示：

其中：xn的初始值設(shè)為x0，x0∈(0，1)；ρ為控制參數(shù)，關(guān)系著Cubic 映射的混沌性。本文參照文獻(xiàn)［17-18］中經(jīng)過驗(yàn)證后相對較優(yōu)的取值，x0取0.3，ρ取2.595。

2.2 改進(jìn)收斂因子

GWO 的全局勘探和局部開發(fā)能力由 |A|決定，當(dāng) |A|≤1時(shí)，狼群跟隨頭狼圍捕獵物；當(dāng) |A|>1 時(shí)，狼群擴(kuò)散搜索獵物。

A值受收斂因子a影響，從式（5）可知，a成線性變化，控制前一半迭代次數(shù)用于全局搜索，后一半迭代次數(shù)用于局部尋優(yōu)，不利于全局勘探和局部開發(fā)的平衡。而GWO-THW 根據(jù)平均適應(yīng)度值將狼群分為適應(yīng)度值較優(yōu)的捕獵狼和適應(yīng)度值較差的偵察狼，并提出相應(yīng)的非線性雙收斂因子。捕獵狼收斂因子如式（14）所示：

式（14）保證了該收斂因子在前期和后期遞減緩慢，中期遞減較快，這樣就平衡了算法的全局勘探和局部開發(fā)能力并確保了算法收斂速度。

偵察狼收斂因子如式（15）所示：

式（15）使收斂因子從2 非線性遞減到0，加強(qiáng)了偵察狼的全局勘探能力。

雙收斂因子與原收斂因子的變化曲線如圖1 所示。

圖1 雙收斂因子與原收斂因子曲線Fig.1 Curves of dual convergence factors and original convergence factor

2.3 增加自適應(yīng)權(quán)重系數(shù)和引入Levy飛行策略

GWO-THW 設(shè)立γ 狼和α 狼雙頭狼機(jī)制，分別引領(lǐng)捕獵狼和偵察狼進(jìn)行狩獵。但二者側(cè)重點(diǎn)不同，捕獵狼的任務(wù)是圍殺獵物，偵察狼的任務(wù)是搜尋獵物。所以，針對捕獵狼和偵察狼目標(biāo)不同，GWO-THW 采用不同的位置更新策略。

捕獵狼由α 狼、β 狼、δ 狼帶領(lǐng)圍捕獵物，但從式（12）可知，標(biāo)準(zhǔn)GWO 采用平均權(quán)重作為灰狼個體的位置更新系數(shù)，不利于快速圍殺獵物。為此，本文提出了一種自適應(yīng)調(diào)整權(quán)重因子策略，以單位歐氏距離內(nèi)適應(yīng)度值遞減速度快慢作為捕獵狼向α 狼、β 狼、δ 狼的移動權(quán)重，比值越大，表示梯度下降越快，該領(lǐng)導(dǎo)狼附近存在獵物的可能性也越大，捕獵狼向它偏移幅度就相應(yīng)變大。

通過此策略，既提升收斂速度，又加強(qiáng)β 狼和δ 狼的影響力，避免所有個體都向α 狼聚集，增強(qiáng)算法勘探能力。權(quán)重公式如式（16）～（21）。

其中：f(X(t))表示第t次灰狼個體的適應(yīng)度值；f(Xα(t))、f(Xβ(t))、f(Xδ(t))表示第t次α 狼、β 狼、δ 狼的適應(yīng)度值；Dα、Dβ、Dδ為當(dāng)前捕獵狼與第t次α 狼、β 狼、δ 狼之間的歐氏距離；ε為一個較小的正常數(shù)，本文取值為10-6。bα(t)、bβ(t)、bδ(t)為當(dāng)前搜索狼與α 狼、β 狼、δ 狼間的單位距離內(nèi)適應(yīng)度值降低值。因此，捕獵狼個體位置更新公式如下：

為加強(qiáng)算法的全局探索能力，本文將迭代歷史過程中的全局最優(yōu)值設(shè)置為全局頭狼γ，它的位置為Pbest。γ 狼一方面積極與α 狼交流，以便及時(shí)更新全局最優(yōu)解；另一方面指導(dǎo)偵察狼以Levy 飛行策略反向搜索獵物。更新公式如下：

其中：θ是步長的縮放因子，?。?，1）內(nèi)的隨機(jī)數(shù)；a2由式（15）確定；Xz為隨機(jī)個體。Levy(λ)為服從式（24）Levy 飛行分布的隨機(jī)步長，u服從N（0，η2）分布，v服從N（0，1）分布，η由式（25）確定，λ取值1.5。

其中，Γ()為伽馬函數(shù)。

為了提升偵察狼的搜尋效果，算法為偵察狼提供一次擇優(yōu)機(jī)會，若進(jìn)行Levy 飛行更新的位置不佳，則保持原位置不變。偵察狼位置更新公式如下：

2.4 增加跳出機(jī)制

在標(biāo)準(zhǔn)GWO 中，狩獵都是α 狼引領(lǐng)。一旦α 狼判斷錯誤，算法就很難找到全局最優(yōu)解。針對這種情況，本文設(shè)定一種跳出機(jī)制，當(dāng)α 狼位置連續(xù)迭代n次無變化（本文中，n=10），則記錄當(dāng)前α 狼位置及適應(yīng)度值，然后種群按式（27）進(jìn)行一次Levy 飛行，繼續(xù)尋找其他最優(yōu)解，直到算法終止。λ取值1.5，Xz、Xk為隨機(jī)個體。

2.5 算法步驟

綜合上述改進(jìn)思想，GWO-THW 算法步驟如下。

步驟1 設(shè)定種群的大小N，維度M，初始化各參數(shù)。

步驟2 利用Cubic 混沌映射初始化灰狼種群。

步驟3 計(jì)算灰狼個體適應(yīng)度值并求出適應(yīng)度平均值，根據(jù)個體適應(yīng)度值確定α 狼、β 狼、δ 狼，取全局最優(yōu)解作為γ狼，計(jì)數(shù)α 狼出現(xiàn)在當(dāng)前位置次數(shù)n，然后根據(jù)式（14）、（15）計(jì)算收斂因子a1、a2。

步驟4 判斷灰狼適應(yīng)度值是否小于平均值，若是，則根據(jù)式（22）進(jìn)行位置更新；否則，保存當(dāng)前位置并根據(jù)式（23）更新位置，然后根據(jù)式（26）擇優(yōu)確定最終更新位置。

步驟5 判斷n次是否達(dá)到閾值，若是，則記錄當(dāng)前α 狼位置及適應(yīng)度值，并與γ 狼比較，取優(yōu)者為γ 狼，然后將種群通過式（27）進(jìn)行位置更新；否則，轉(zhuǎn)入步驟6。

步驟6 判斷是否達(dá)到終止條件，若是，則將輸出最優(yōu)值；否則，返回步驟3。

3 實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證本文算法的有效性，選取了通用的10 個基準(zhǔn)測試函數(shù)進(jìn)行性能測試。運(yùn)行環(huán)境為Intel Corei5-10500 CPU，主頻3.10 GHz，內(nèi)存8 GB，Windows10 64 位操作系統(tǒng)，集成開發(fā)環(huán)境為 Python 3.7。為保證實(shí)驗(yàn)數(shù)據(jù)與其他算法的無差異性，算法的種群數(shù)設(shè)置為30，迭代次數(shù)設(shè)定為500，算法獨(dú)立運(yùn)行30 次，取平均值和標(biāo)準(zhǔn)差為性能對比度量。

3.1 基準(zhǔn)測試函數(shù)

仿真所用基準(zhǔn)測試函數(shù)的相關(guān)參數(shù)如表1 所示，其中包含7 個單峰測試函數(shù)（F1～F7）和3 個多峰測試函數(shù)（F8～F10）。

表1 10個基準(zhǔn)測試函數(shù)Tab.1 Ten benchmark functions

3.2 改進(jìn)策略分析

為驗(yàn)證本文改進(jìn)策略的有效性，將改進(jìn)算法在表1 所列的10 個基準(zhǔn)測試函數(shù)上進(jìn)行消融實(shí)驗(yàn)。對比算法包括GWO和本文的GWO-THW 去掉各改進(jìn)策略后的算法（GWO1 代表去掉初始化種群策略；GWO2 代表去掉改進(jìn)的收斂因子策略；GWO3 代表去掉自適應(yīng)權(quán)重系數(shù)和Levy 飛行策略；GWO4 代表去掉跳出機(jī)制）。實(shí)驗(yàn)結(jié)果如表2 所示。

表2 消融實(shí)驗(yàn)結(jié)果Tab.2 Ablation experiment results

從表2 可知，去掉初始化種群策略（GWO1）和跳出機(jī)制策略（GWO4）對尋優(yōu)精度的影響較小。初始化種群策略能改進(jìn)初始種群的分布，影響算法的前期尋優(yōu)速度和尋優(yōu)結(jié)果的穩(wěn)定性；跳出機(jī)制策略是跳出局部最優(yōu)機(jī)制，在算法尋優(yōu)趨勢較好時(shí)發(fā)揮的作用較小。對于改進(jìn)收斂因子策略、自適應(yīng)權(quán)重系數(shù)和Levy 飛行策略，單一情況下對算法有一定改進(jìn)，但效果一般，二者結(jié)合后，對算法的尋優(yōu)精度提升較大。

3.3 與其他群智能算法比較分析

為驗(yàn)證本文算法在尋優(yōu)性能上的優(yōu)勢，將GWO-THW 與其他群智能算法（包括差分進(jìn)化（Differential Evolution，DE）、螢火蟲算法（Firefly Algorithm，F(xiàn)A）、粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法）在10 個基準(zhǔn)函數(shù)上進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表3 所示。

表3 本文算法與其他群智能算法的比較結(jié)果Tab.3 Comparison results of the proposed algorithm and other swarm intelligence algorithms

從表3 可以看出，GWO-THW 除了在F5函數(shù)上與PSO 算法尋優(yōu)精度相近外，其他數(shù)值都明顯優(yōu)于對比的群智能算法，特別是在F1～F3和F8～F10函數(shù)上，尋優(yōu)精度更佳。這也驗(yàn)證了本文的GWO-THW 相比其他的標(biāo)準(zhǔn)群智能算法具有較大的精度優(yōu)勢。

3.4 與其他灰狼算法的對比分析

為進(jìn)一步驗(yàn)證本文的改進(jìn)策略的有效性，將GWO-THW與GWO 及相關(guān)改進(jìn)GWO 進(jìn)行比較。對比算法如下：

GWO［14］：標(biāo)準(zhǔn)灰狼算法。

EGWO［5］：基于當(dāng)前迭代最優(yōu)解為頭狼的改進(jìn)算法。

LGWO［6］：基于雙狼引領(lǐng)、Levy 飛行的改進(jìn)算法。

NGWO［7］：基于反向?qū)W習(xí)和變異算子的改進(jìn)算法。

TGWO［2］：基于Sigmoid 及權(quán)重因子的改進(jìn)算法。

OGWO［8］：基于反向?qū)W習(xí)的改進(jìn)灰狼優(yōu)化算法。

DGWO2［9］：改進(jìn)的動態(tài)灰狼優(yōu)化算法。

實(shí)驗(yàn)結(jié)果如表4 所示。表4 中10 個基準(zhǔn)測試函數(shù)上的測試數(shù)據(jù)，除GWO、OGWO、DGWO2 和GWO-THW 算法外，其他算法的數(shù)據(jù)都來源于原文獻(xiàn)。

表4 GWO及其各種變體的實(shí)驗(yàn)結(jié)果Tab.4 Experimental results of GWO and its variants

從表4 來看，GWO-THW 在20 個指標(biāo)數(shù)據(jù)中占據(jù)16 項(xiàng)最佳結(jié)果。在復(fù)雜單峰函數(shù)F5～F6上，因最優(yōu)值所在區(qū)域中，函數(shù)值變化不大，隨機(jī)算法容易在此區(qū)域內(nèi)發(fā)生扭擺現(xiàn)象，因此GWO-THW 與其他算法性能接近；但在其他8 個基準(zhǔn)測試函數(shù)上，GWO-THW 都取得了較高的尋優(yōu)精度，尤其在多峰函數(shù)上更是取得了理想最優(yōu)值，說明算法在多峰函數(shù)和簡單單峰函數(shù)上尋優(yōu)能力良好，驗(yàn)證了GWO-THW 的有效性。

從算法改進(jìn)策略分析，在收斂精度方面，NGWO、TGWO、GWO-THW 在多峰函數(shù)方面表現(xiàn)較好，而這幾種算法都改進(jìn)了收斂因子，說明收斂因子調(diào)整有助GWO 算法在多峰函數(shù)上的尋優(yōu)；TGWO、OGWO、GWO-THW 在函數(shù)F1～F4上性能較佳，這些算法在進(jìn)行位置更新時(shí)都引入了自適應(yīng)動態(tài)權(quán)重因子，說明位置更新權(quán)重系數(shù)能提高GWO 在簡單單峰函數(shù)上的性能；在復(fù)雜單峰函數(shù)方面，對比的各算法都有待進(jìn)一步改進(jìn)。

為驗(yàn)證算法在收斂速度方面的性能，選取GWO、OGWO、DGWO2 和GWO-THW 這4 種算法進(jìn)行實(shí)驗(yàn)，算法的種群數(shù)設(shè)置為30，迭代次數(shù)設(shè)定為500。算法獨(dú)立運(yùn)行30次，取其中尋優(yōu)精度最佳的實(shí)驗(yàn)數(shù)據(jù)作迭代圖，具體收斂曲線如圖2 所示。

從圖2 可以看出：除函數(shù)F5、F6外，在迭代相同次數(shù)的情況下，相比其他算法，本文的GWO-THW 能得到更高的精度，尤其在多峰函數(shù)上，200 次迭代內(nèi)就能收斂到理想最優(yōu)值0。說明改進(jìn)算法在收斂速度方面優(yōu)于其他算法，進(jìn)一步驗(yàn)證了GWO-THW 算法的有效性，且在多峰函數(shù)上具備非常明顯的優(yōu)勢。

4 結(jié)語

針對標(biāo)準(zhǔn)GWO 算法的收斂精度不高、易早熟等問題，本文提出了一種的改進(jìn)灰狼算法。首先，利用混沌映射初始化種群機(jī)制，提升算法的魯棒性；設(shè)計(jì)了雙非線性收斂因子和雙頭狼引領(lǐng)狩獵策略，平衡算法的全局勘探和局部開發(fā)性能；引入Levy 飛行策略和調(diào)整自適應(yīng)位置更新權(quán)重機(jī)制，提升算法尋優(yōu)精度和收斂速度，同時(shí)加強(qiáng)算法跳出局部最優(yōu)能力；最后通過10 組基準(zhǔn)測試函數(shù)驗(yàn)證了改進(jìn)策略的有效性。