動態反向搜索更新位置的改進灰狼優化算法

王夢璐，李連忠

江南大學 理學院，江蘇 無錫214122

灰狼優化算法（Grey Wolf Optimizer，GWO）[1]是澳大利亞學者Mirjalili等于2014年提出的新型群體智能優化算法。它通過模仿自然界中灰狼群體的等級制度和追蹤、圍捕、攻擊獵物等捕食過程實現算法優化搜索的目的。GWO算法在求解精度和收斂速度方面與粒子群算法（Particle Swarm Optimization，PSO）[2-3]、遺傳算法（Genetic Algorithm，GA）[4]、差分進化算法（Differential Evolution，DE）[5]相比是比較有競爭力的，且具有原理簡單、需要調整的參數少、易于實現等優點，因此GWO算法在優化PID控制器參數[6]、路徑規劃[7-8]、文本聚類[9]、支持向量機[10]、多層傳感器訓練[11]等領域上有著廣泛的應用。

然而，標準GWO算法仍存在求解精度不高、后期收斂速度較慢且容易陷入局部最優無法跳出等缺點。為了進一步提高GWO算法的性能，研究學者們提出了許多改進策略，徐松金等[12]提出了一種交叉變異機制，在群體中隨機選擇三個個體與決策層個體執行算術交叉操作并且以一定概率對決策層個體進行變異，該機制有效地提高了算法的局部搜索能力和收斂速度，但是變異時沒有突破遺傳算法的變異規則，較容易陷入局部最優；黎素涵等[13]提出了非線性收斂因子調整策略和精英個體重選策略，該算法有較好的收斂速度和效率，但改進算法的模式較為單一，收斂精度沒有得到有效提高；王敏等[14]提出了一種隨迭代次數非線性遞減的自適應收斂因子與變異算子，平衡了算法的全局搜索和局部搜索能力，但在灰狼的位置更新中沒有考慮優秀個體對其他個體的引導作用只是隨機地進行變異，算法跳出局部最優的能力較差；金星等[15]利用差分進化算法（DE）的變異來改進灰狼優化算法，通過灰狼算法與差分進化的交叉、選擇算子進行全局搜索以增強種群的多樣性和算法收斂精度，該算法有較好的全局收斂性，但算法需要進行反復地迭代，增加了計算的時間復雜度且易早熟；陳超等[16]提出了一種稱為三級領導式的自適應狼群算法，使用三個領導層灰狼指導ω個探狼的形式，并引入微粒進化方程來加快算法收斂速度，該算法著重考慮了灰狼個體最優值和群體最優值對猛狼奔襲的指導，避免了很多無效的搜索從而節省了大量的計算時間，但算法中沒有設置跳出局部極值的機制使得算法收斂精度不高。由以上學者對GWO算法的研究經驗可知，找到一種簡單且高效的改進策略十分必要，結合上述學者對GWO算法的分析及改進思路，本文提出一種動態反向搜索更新位置的改進灰狼優化算法（DAGWO）。采用Tent混沌映射和動態一般反向學習來初始化種群，以提高種群的多樣性；依據sigmoid函數構造一種非線性遞減的收斂因子a，并引入符合beta分布的隨機調整數對a進行局部擾動，以更好地平衡算法全局搜索能力和局部搜索能力；在位置更新公式中引入種群早熟判別指標、反向學習因子和個體歷史最優位置引導策略，使灰狼個體進行自適應的動態反向搜索更新其位置，在提高算法收斂速度的同時增強算法跳出局部最優的能力。通過對20個基本測試函數的仿真實驗，結果表明本文提出的改進算法（DAGWO）比標準智能優化算法和其他策略改進算法有更好的求解精度、收斂速度和跳出局部最優的能力。

1 灰狼優化算法

灰狼過著群居生活且有嚴格的社會等級層次制度，如圖1所示。狼群中的領導者稱為α，負責捕食、食物分配和作息地點等決策。第二等級的狼稱為β，主要負責協助α進行決策。第三等級的狼稱為δ，主要負責偵察、放哨等。處于等級制度的最低端的ω，主要負責維持種群內部關系的平衡。

圖1 灰狼等級制度Fig.1 Gray wolf hierarchy

假設灰狼種群數目為N,第i只灰狼的位置為Xi,α為最優解，β為次最優解，δ為第三最優解，ω為候選解。灰狼追蹤、接近獵物的數學模型如下：其中，t表示當前迭代次數，A、C是系數向量，Xp為獵物位置向量，X為灰狼位置向量。

向量A、C的計算公式如下：

2 改進灰狼優化算法

2.1 種群初始化

本文采用Tent混沌映射和文獻[17]中提出的動態一般反向學習策略（Dynamic GOBL）來產生初始種群，具體步驟如下：

步驟1根據Tent混沌映射的數學模型來生成一個初始種群，其模型為：

其中，?∈(0,1)且xt∈[0,1]時系統處于混沌狀態。

步驟2利用動態一般反向學習策略對生成的初始種群按下式進行反向學習：

其中，xij(t)(i=1,2,…,N,j=1,2,…,D)是當前群體中第i個解在第j維上的分量，是xij(t)對應的反向解，aj(t)和bj(t)分別為當前搜索區間在第j維上的最小值和最大值，N為群體大小，D為搜索空間維數，t為演化代數。

步驟3按照次序在步驟1生成的初始種群和步驟2生成的反向種群中取出個體，計算個體的適應度值并對其進行升序排列，選取前N個個體組成初始種群。

2.2 局部擾動的非線性遞減收斂因子

2.2.1 改進收斂因子

在灰狼算法中， ||A>1時，灰狼將擴大搜索范圍，即進行全局搜索； ||A<1時灰狼將縮小搜索范圍，即進行局部搜索。由式（3）可知，A的取值決定于收斂因子a，在GWO算法中收斂因子a隨迭代次數從2線性遞減到0，而算法的收斂過程是非線性的，故線性收斂因子不能完全適應于算法搜索。本文依據sigmoid函數的特性構造了一種新型非線性遞減的收斂因子a，并引入符合beta分布的隨機調整數對a進行局部擾動以提高算法在迭代后期的全局搜索能力，減少算法陷入局部最優的可能性。改進的收斂因子a表達式如下：

其中，ainitial,afinal分別為收斂因子a的初始值和終止值，t為當前迭代次數，tmax為最大迭代次數。σ為收斂調整因子，經多次實驗得σ取0.1時效果最好；betarnd為matlab中的隨機數生成器，可以生成符合貝塔分布的隨機數。

圖2為原始收斂因子與改進收斂因子的對比圖。

圖2 收斂因子對比圖Fig.2 Comparison of convergence factors

如圖2所示，虛線為線性遞減的標準GWO算法的收斂因子a，實線為非線性遞減的改進收斂因子a。從圖中可以看出，標準GWO算法的收斂因子a在整個迭代過程中呈線性遞減。

迭代前期收斂速度過快導致搜索范圍較小、種群多樣性較差，后期收斂速度過慢求解效率較低。本文提出的改進收斂因子a呈非線性遞減，迭代前期改進收斂因子在較長時間內保持較大值且變化幅度、速度較小，即灰狼長時間以較大的步伐進行搜索，可擴大搜索范圍、保證種群多樣性以加強算法的全局搜索能力；迭代后期，改進收斂因子a在較長時間內保持較小值且變化幅度和速度也較小，使得灰狼長時間以較小的步伐進行搜索，加強算法的局部搜索能力、提高算法的求解效率。因此，本文提出的改進收斂因子a能夠更加有效地平衡全局搜索能力和局部搜索能力。

2.2.2 收斂調整因子σ的有效性分析

改進收斂因子a中使用beta隨機調整數對a的取值進行局部擾動，增強了算法跳出局部最優的能力但同時也使收斂因子a的偏離程度變大，因此，在收斂公式中加入收斂調整因子σ來控制收斂因子的偏離程度，使得對收斂因子a的調整更加合理。為驗證收斂調整因子σ控制收斂因子偏離程度的有效性，引入偏離判別指標δ，公式如下：

其中，n為迭代次數，ai為無隨機調整數時改進收斂因子a在第i次迭代時的取值；為收斂調整因子σ控制偏離程度后a的取值。

偏離判別指標δ的值較小時，表明收斂因子a的偏離程度較小。當σ取不同的值時δ的大小如表1所示。

表1 偏離判別指標對比表Table 1 Comparison of discriminant index deviation

由表1可以看出，當收斂公式中不引入收斂調整因子σ（等同于σ取值為1）時，收斂偏離指標δ的值較大，即收斂因子a的偏離程度較大、算法的搜索效率較低；當σ取0.8、0.5和0.1時，偏離判別指標δ的值隨σ取值的降低而降低，收斂因子的偏離程度得到有效控制，并在σ=0.1時達到本文所需的最優值；當σ取0.05時，δ的值為8.478 3E-04，此時收斂因子的偏離程度非常小，幾乎可以忽略不記。由圖3可以更直觀地看到收斂公式中不引入收斂調整因子σ時，收斂因子的偏離程度很大，引入σ后收斂因子的偏離程度得到了有效控制。

圖3 收斂因子偏離程度對比圖Fig.3 Comparison of deviation degree of convergence factor

綜上所述，收斂調整因子σ可以有效地控制收斂因子a的偏離程度，使得對收斂因子a的調整更加合理。

2.3 動態反向學習的位置更新公式

本文在原始的位置更新公式中引入個體歷史最優位置引導策略，加強算法的收斂速度；同時，構造了個體相似度指標、早熟判別指標和反向搜索因子，用以判別灰狼個體是否陷入局部極值并使陷入局部極值的個體進行反向搜索，增強算法跳出局部極值的能力。

2.3.1 向個體歷史最優位置動態學習

在原始灰狼算法的位置更新中灰狼個體只向群體最優位置進行學習，為了使灰狼個體更快地到達最優解附近區域，本文使灰狼個體在向群體最優位置學習的同時向個體歷史最優位置動態學習。

此時改進的位置更新公式如下：

2.3.2 種群早熟判別指標

原始灰狼算法在探索和開發的過程中都存在容易陷入局部最優值無法跳出的問題。為了合理地判斷算法是否陷入局部極值，并動態地進行反向搜索，本文在灰狼算法中引入個體相似度指標σ和種群早熟判別指標S。利用當前灰狼個體與其他個體間位置的相似程度來定義個體相似度指標σ，對種群中所有個體的相似度指標取均值得到種群早熟判別指標S，早熟判別指標較高時則說明算法有較大概率陷入局部極值即出現早熟現象。

首先，定義灰狼個體之間的相似度指標σ,公式如下：

其中，σ(i)(i=1,2,…,N)為第i個灰狼個體的個體相似度指標；D為算法搜索空間的維度，N為種群數量，xi=(xi,1,xi,2,…,xi,D)為第i只灰狼的位置，xj=(xj,1,xj,2,…,xj,D)為第j只灰狼的位置，xi,k和xj,k分別為灰狼個體i的第k維和灰狼個體j的第k維，δ為相似度閾值，實驗表明δ=0.3時算法的求解效果較好。

由式（16）得到種群中N個個體的相似度指標值，然后對這N個指標值進一步求均值來衡量群體早熟情況，群體早熟判別指標的計算公式如下：

其中，S(t)表示第t代的種群早熟判別指標，當S(t)→1時，種群中個體相似度較高，算法有較大可能陷入局部極值；當S(t)→0時，種群中個體相似度較低，算法陷入局部極值的可能性較小。

2.3.3 反向搜索因子

為進一步提高算法跳出局部極值的能力，引入依據種群早熟判別指標動態調節自身取值的反向搜索因子，在種群陷入局部極值時使灰狼個體向整個種群中最差個體方向進行反向搜索，使得種群能夠以一定概率跳出局部極值。

反向搜索因子q的公式如下：

其中，S(t)為第t代種群相似度指標；p為判別系數，在本文中p取0.4。

由式（17）可以看出，當早熟判別指標較高時算法有較大可能陷入局部極值，此時反向搜索因子q隨早熟判別指標大小動態變化，以調控灰狼個體進行反向搜索，加強算法跳出局部極值的能力；當種群相似度指標較低時，反向搜索因子取0。

綜上所述，本文改進的灰狼位置更新公式如下：

其中，xi(t)=(xi,1,xi,2,…,xi,D)為第t次迭代中第i只灰狼的位置；xibest為第i只灰狼個體的歷史最優位置；xworst(t)為第t次迭代灰狼種群中適應度最差的灰狼個體位置；q為反向搜索因子；c1為學習系數，本文取c1=1-q；r1,r2為[0，1]之間的隨機數。

2.4 DAGWO算法的具體執行步驟

動態反向搜索更新位置的灰狼優化算法（DAGWO）的具體執行步驟如下：

（1）設定種群規模N，最大迭代次數tmax，收斂因子的初始值ainitial和終止值afinal。

（2）種群初始化。利用Tent混沌映射（式（8））生成初始種群，式（9）~（10）生成一般反向種群，在兩個種群中選出適應度最高的個體放入到最終的初始種群對應位置。

（3）計算種群中每個個體的適應度，得到最優個體α，次優個體β，第三優個體δ，并記它們的位置分別為Xα,Xβ,Xδ。

（4）根據式（11）更新收斂因子a的值。

（5）根據式（3）、（4）更新A、C的值。

（6）根據式（14）~（17）計算群體相似度指標；根據式（18）得到反向學習因子。

（7）根據式（19）更新灰狼位置得到新一代灰狼種群。

（8）更新最優個體α，次優個體β，第三優個體δ，和它們的位置Xα,Xβ,Xδ。

（9）檢驗算法是否滿足算法的結束條件，若達到最大迭代次數tmax則停止計算輸出最優位置Xα；否則，返回并重新執行步驟（3）至步驟（8）。

3 仿真實驗及結果分析

本文通過20個標準測試函數對改進灰狼優化算法（DAGWO）進行仿真實驗。為保證仿真實驗的公平及合理性，令各算法的種群規模均為100，迭代次數為1 000，獨立運行30次，所有參數保持一致。

在20個標準測試函數中f1~f10為單峰函數，f11~f16為多峰函數，f17~f20為固定維數多峰函數。標準測試函數的具體特征如表2所示。測試函數收斂曲線如圖4所示。

表2 標準測試函數Table 2 Standard test function

圖4 測試函數收斂曲線Fig.4 Test function convergence curves

3.1 與標準智能優化算法相比

本文通過求解上述20個標準測試函數對標準灰狼算法（GWO）、標準粒子群算法（PSO）、蝙蝠算法（BA）[18]和本文改進算法（DAGWO）的各項性能進行測試和比較。各算法的參數設置如表3所示。

表3 算法的參數設置Table 3 Parameter setting of algorithms

對每個測試函數，四個算法在采用上述實驗參數的條件下獨立運行30次，分別計算四個算法的平均精度值（Mean）和標準差（St.dev）。所有的仿真實驗均在CPU：i5-10210、8 GB、1.6 GHz主頻的計算機上實現，程序采用MATLAB R2019b語言實現，具體結果如表4所示。

由表4可知，與標準GWO、BA、PSO算法相比，DAGWO算法在求解20個標準測試函數的綜合性能上有了明顯的提高，尤其是在算法的收斂速度、精度和跳出局部極值的能力上有很大的提升。測試函數F1~F10為單峰函數，在標準測試函數F1、F3、F4、F5、F7、F8、F9、F10上三個標準算法求解的平均值與全局最優解相差很大，而DAGWO算法均取得了理論最優解且標準差為0，表明DAGWO算法與三個標準算法相比，有更高的求解精度和穩定性，且由圖4可以看出，DAGWO算法的收斂速度明顯高于其他三種算法。對于函數F2，三個標準算法取得的最優解與全局最優解之間誤差較大而DAGWO算法雖然沒有取得理論最優值但30次實驗的平均值4.991 8E-202非常接近最優值0，收斂精度明顯高于其他三個算法，且由圖像可知DAGWO在收斂速度和算法的穩定性上都具有優勢。對于函數F6，四種算法都沒有取得全局最優解，但DAGWO算法的平均值和標準差最小，說明了改進算法的收斂精度和穩定性更好。從單峰函數的求解結果來看DAGWO算法的收斂精度和速度遠高于所測標準算法。

表4 四種算法性能測試結果Table 4 Performance test results of four algorithms

測試函數F11~F20為多峰函數，多峰函數在全局最優解周圍存在很多局部極值點，易使算法在尋優過程中陷入局部最優無法跳出。在函數F11、F13、F16上DAGWO算法均收斂到了理論最優解0，結合圖4可知DAGWO算法的收斂精度和速度都要高于標準算法，這表明DAGWO算法有較強的跳出局部極值的能力。對于函數F12、F14四個算法都沒有取得最優解，但DAGWO算法的收斂精度較高、速度較快。對于函數F15，標準GWO算法和DAGWO算法有相同的高于其他兩個算法的求解精度，但DAGWO算法的標準差小、穩定性好且收斂速度較快。對于函數F17、F18，PSO、BA、DAGWO算法均取得到了理論最優解，但DAGWO算法的標準差更小穩定性更強，且由圖4可知DAGWO算法的收斂速度更快即改進算法跳出局部極值的能力更強。對于函數F19、F20只有DAGWO算法取得了全局最優解，收斂精度和速度明顯高于三個標準算法。從多峰函數的求解結果來看DAGWO算法有更強的全局尋優能力和跳出局部極值的能力，與標準算法相比收斂的速度和精度都更有優勢。

綜上所述，在單峰函數和多峰函數的求解上，與其他三種算法相比，DAGWO算法在收斂精度、速度和跳出局部最優的能力上都體現出了較高的優越性。

3.2 DAGWO改進策略有效性測試

為了驗證DAGWO算法中改進種群初始化方式、收斂因子a和位置更新公式的有效性及可行性，將在GWO算法中只引入改進種群初始化方式的算法稱為DAGWO-I；只引入改進收斂因子a的算法稱為DAGWO-II；只引入改進位置更新公式的算法稱為DAGWO-III。三種算法的參數設置均與表3中DAGWO算法的參數設置相同。利用上述測試函數中的F9、F11、F14、F19對DAGWO-I、DAGWO-II、DAGWO-III進行性能測試，對比實驗結果如表5所示，對比圖像如圖5所示。

由表5、圖5可以看出，DAGWO-I、DAGWO-II、DAGWO-III算法的平均值、標準差均優于標準GWO算法，這表明本文改進的種群初始化方式、收斂因子和位置更新公式都可以有效地加強算法的收斂精度、速度和穩定性，尤其是改進的位置更新公式能夠有效地提高算法的收斂精度和速度；對于多峰函數F14、F19，GWO算法求解時容易陷入局部最優，而DAGWO-III算法能夠跳出局部極值更接近理論最優解，說明DAGWO-III算法采用的反向學習機制能夠在一定程度上規避局部最優解，從而提高算法的收斂精度。

圖5 DAGWO改進策略對比圖Fig.5 Improved formula performance comparison diagram

表5 DAGWO改進策略性能測試結果Table 5 DAGWO improved strategy performance test results

在文獻[19]中，龍文等學者提出EGWO算法，將PSO算法中對粒子自身運動歷史最優解保存的思想和差分搜索的方法引入GWO算法中。本文的位置更新也使灰狼個體向個體歷史最優位置動態學習，不同的是本文同時構建了早熟判別指標和反向搜索因子使算法在出現早熟現象時自適應地進行反向搜索，以提高算法跳出局部極值的能力從而提高算法的收斂精度和速度。為進一步分析本文改進位置更新公式的有效性，選取Sphere等五個標準測試函數對兩個位置更新公式進行實驗，EGWO-w是在原始算法中只引入EGWO中改進的位置更新公式。由表6可得五個標準測試函數的尋優結果，DAGWO-w的收斂精度要明顯高于EGWO-w，表明DAGWO算法改進的位置更新公式有較強的跳出局部最優的能力。由圖6可知對于五個標準測試函數DAGWO-w的收斂速度都明顯高于EGWO-w。綜上所述，DAGWO算法改進的位置更新公式所采用的動態反向搜索機制與EGWO算法所采用的差分搜索相比，動態反向搜索機制有更強的跳出局部最優的能力和更快的收斂速度。

圖6 改進公式性能對比圖Table 6 Comparison of improved formula performance

表6 改進位置更新公式對比表Table 6 Comparison of improved location update formula

使用三種改進策略相融合的DAGWO算法的收斂速度、精度和穩定性都要優于使用單一改進策略的DAGWO-I算法、DAGWO-II算法、DAGWO-III算法和原算法。因此可得單獨使用改進的種群初始化方式、改進的收斂因子和改進的位置更新方程都可以對提高算法的性能起一定的效果但效果有限，而組合的改進策略可以更加有效地提高算法的尋優能力。

3.3 算法的種群多樣性分析

上述仿真實驗的數據表明，與三個標準算法相比DAGWO算法的平均值和標準差最小，即DAGWO算法種群多樣性更高，發掘最優解的能力強于其他三類算法。為更直觀地分析改進算法的種群多樣性，圖7中給出了DAGWO算法在二維搜索空間中生成100個個體的初始種群分布情況；圖8給出了對于單峰測試函數Sphere和多峰測試函數Griewank，DAGWO算法在迭代前期和迭代后期時種群個體分布情況。

圖7 DAGWO初始種群分布圖Fig.7 Initial population profile of DAGWO

GWO算法在迭代前期需要較大的搜索空間，從而有利于提高算法的全局搜索能力，而初始種群多樣性的好壞影響著算法的搜索范圍和解的質量，多樣性較好的初始種群對提高算法的尋優性能很有幫助。原始GWO算法的初始種群是隨機產生的，難以確保初始種群的多樣性，而由圖7可以直觀地看出，DAGWO算法生成的初始種群中個體較為均勻地覆蓋在整個搜索空間中，具有較好的種群多樣性從而使算法有較好的全局搜索能力。雖然均勻分布會產生一些質量較差的解，但改進DAGWO算法中引入了個體最優引導策略，使這些解迅速地向最優解方向靠攏，從而使算法在增強全局搜索能力的同時也有較快的收斂速度。

由圖8得知，不論是單峰函數還是多峰函數DAGWO算法在迭代前期種群個體的分布空間都較大，種群多樣性較好，能夠有效提高算法的全局搜索能力；迭代后期種群個體集中在最優解附近的一個較小的區域內且有部分個體保持相對分散，使得在算法進行局部搜索的同時保持種群多樣性，避免算法陷入局部最優。

圖8 種群個體分布情況圖Fig.8 Population individual distribution

綜合以上分析，DAGWO算法中的改進策略能夠有效地提高算法種群多樣性，提高算法全局搜索能力，降低算法迭代后期陷入局部最優的可能性。

3.4 DAGWO與其他改進GWO算法的對比

8個測試函數的尋優結果對比如表7所示，為了更好地驗證改進DAGWO算法的有效性，將本文提出的DAGWO算法與改進CGWO[20]、改進TS-GWO[21]、改 進SAGWO[22]算法相比較，參數設置和數據均來自于對應文獻。

表7 DAGWO算法與其他不同策略改進算法比較Table 7 Comparison of DAGWO algorithm with other improved algorithms

對于函數F2、F3、F4、F6、F12，DAGWO算法的平均值和標準差均明顯優于其他三個改進算法，表明DAGWO算法在收斂精度和穩定性上有明顯的優勢。對于函數F11，四個算法均取得了較好的收斂精度，由收斂曲線圖可以直觀地看出DAGWO算法的收斂速度更快；對于函數F13，DAGWO、SAGWO、CGWO算法都收斂到了最優解0，但由圖9的收斂曲線可以看出，對于這兩個測試函數DAGWO算法的收斂速度均高于其他三種算法。綜上所述，與以上三種不同策略改進的GWO算法相比，本文提出的DAGWO算法在各項性能上均優于其他三種改進灰狼算法。

圖9 DAGWO與其他改進GWO算法的比較Fig.9 Comparison of DAGWO algorithm and other improved algorithms

4 結束語

本文在標準GWO算法的基礎上提出了動態反向搜索的改進灰狼算法（DAGWO），主要進行了以下三個部分的改進：在算法中的位置更新公式中，引入由種群早熟判別指標和反向搜索因子組成的動態反向搜索機制，提高算法跳出局部最優的能力從而提高算法的收斂速度和精度；引入新型非線性收斂因子a，并加入服從beta分布的隨機調整數和收斂控制因子，以更好地平衡算法的全局和局部搜索能力；采用混沌映射和一般動態反向學習初始化種群，以提高種群的多樣性。通過在20個標準測試函數上的仿真實驗，與三種標準智能優化算法和其他文獻提出的三種改進灰狼算法進行對比，仿真實驗結果表明本文提出的DAGWO算法有更高的求解精度、收斂速度和跳出局部最優的能力。