引入萊維飛行與動態(tài)權(quán)重的改進灰狼算法

丁瑞成，周玉成

山東建筑大學 信息與電氣工程學院，濟南 250101

灰狼算法（grey wolf optimization，GWO）是Mirjalili等人[1]通過模擬灰狼種群的社會分級制度與捕獵活動，于2014年提出的一種群智能算法，具有參數(shù)簡單、易于實現(xiàn)等優(yōu)點。群智能算法的尋優(yōu)過程包括兩個階段：前期的全局搜索，初步確定全局最優(yōu)解最大概率的位置，搜索范圍應廣泛分布于整個搜索空間；后期的局部搜索，在由全局搜索得到的位置，小范圍內(nèi)進行精細搜索。GWO算法種群位置更新僅由三頭精英狼決定，當精英個體的搜索方向存在偏差，種群很難尋優(yōu)全局最優(yōu)值，全局搜索能力不足，容易過早收斂。

針對以上問題，相關(guān)學者在GWO算法基礎(chǔ)上提出改進策略。文獻[2]提出一種基于余弦變化的收斂因子與基于步長歐氏距離的動態(tài)權(quán)重位置更新策略，取得了較好的尋優(yōu)精度。文獻[3]針對GWO易陷入局部最優(yōu)的問題，對精英個體的位置添加混沌擾動。文獻[4]在精英狼的位置引入高斯擾動，增加精英狼跳出局部最優(yōu)的能力。文獻[5]提出一種收斂因子非線性調(diào)節(jié)策略，提高了尋優(yōu)精度，但不明顯。這些基于GWO算法本身的改進雖然不同程度上提高了算法的尋優(yōu)性能，但是全局尋優(yōu)能力有限，算法本身的局限性仍然存在。

不同群智能算法具有各自的優(yōu)勢與不足，相關(guān)學者將其他優(yōu)化算法的搜索策略引入GWO算法的個體位置更新公式，可以更好地改善算法的尋優(yōu)性能。文獻[6]將粒子群算法個體最優(yōu)機制引入GWO個體位置更新公式，更好地協(xié)調(diào)了算法的探索與開發(fā)能力。文獻[7]將差分進化（differential evolution，DE）機制引入精英狼的位置更新公式，基于DE算法較強的全局搜索能力，使種群跳出局部最優(yōu)值。文獻[8]提出一種融合隨機蛙跳算法（shuffled frog leaping algorithm，SFLA）的改進GWO算法，通過引入SFLA最差個體的跳躍機制，提高算法的全局探索能力，面對高維復雜尋優(yōu)函數(shù)時，取得了更好的尋優(yōu)性能。

基于此，本文在改進GWO算法的基礎(chǔ)上，引入布谷鳥算法的萊維（Levy）飛行策略，提高了GWO算法的全局尋優(yōu)能力與收斂精度，尤其面對高維復雜優(yōu)化問題時，算法依然保持有效性。本文針對GWO算法的改進主要集中在以下3個方面：

（1）引入Singer混沌映射初始化灰狼種群，使初始種群位置在搜索空間分布更加均勻，提高種群多樣性。

（2）采用新的非線性收斂因子更新策略，在搜索全期，平衡種群的全局搜索與局部搜索能力。

（3）針對GWO算法位置更新公式僅受精英狼影響，種群容易陷入局部最優(yōu)的問題，引入Levy飛行策略，降低種群陷入局部最優(yōu)的風險。并采用一種基于適應度的動態(tài)權(quán)重策略，提高算法的尋優(yōu)精度。

1 標準GWO算法

灰狼種群擁有嚴格的等級制度，體現(xiàn)在GWO算法中，α狼最大程度上決定狼群的行為方式，對應最優(yōu)適應度的位置，其次是β狼與δ狼，分別對應第2優(yōu)適應度位置與第3優(yōu)適應度位置。前三頭精英狼負責追蹤獵物和引導狼群，其余個體統(tǒng)稱ω狼，負責包圍與捕殺獵物，在每次迭代過程中依據(jù)上一迭代中精英狼的位置信息更新自身位置。在d維搜索空間中，第k只灰狼個體在第t次迭代的位置表示為Xk(t)。精英狼追蹤獵物的數(shù)學模型表示為：

其中，D為搜索步長；Xp(t)為當前獵物位置；Xk(t+1)為當前個體更新后的位置；A、C為擾動因子，定義如下：

其中，rand()為[0，1]之間的隨機數(shù)；a為收斂因子，隨迭代次數(shù)在[0，2]線性遞減，定義如下：

其中，T為總的迭代次數(shù)。

種群個體在3頭精英狼的引導下的位置更新公式如下：

其中，Xα(t)、Xβ(t)與Xδ(t)為當前α、β和δ精英狼的位置；Dα、Dβ與Dδ表示3頭精英狼引導下的搜索步長；Xi(t+1)(i=1,2,3）表示灰狼個體在對應精英狼引導后的位置；A1、A2、A3與C1、C2、C3為式（3）、（4）所述擾動因子。

標準GWO算法中收斂因子a采用線性遞減策略。由式（3）可知，A取值范圍為[-2a,2a]，當||A≥1時，精英狼始終與當前獵物位置保持一定距離并在附近范圍內(nèi)持續(xù)搜索，對應于全局搜索階段。當||A＜1時，精英狼開始引導狼群向獵物位置靠近，對應于局部搜索階段。擾動因子C取值為[0，2]的隨機數(shù)，在尋優(yōu)全期過程中影響種群的搜索方向，從而賦予算法一定跳出局部最優(yōu)的能力，但是面對復雜尋優(yōu)問題時存在不足。

2 LGWO算法

2.1 Singer混沌映射

初始種群位置均勻分布于搜索空間，有助于增強算法全局搜索能力，提高搜索效率。標準GWO算法隨機初始化種群，存在降低種群多樣性的風險，而混沌映射生成的混沌序列，具有遍歷性、非線性和不可預測性等特征，常用于替代隨機序列初始化種群。本文采用Singer映射初始化GWO種群。作為混沌映射的典型形式，Singer映射具有參數(shù)簡單，分布均勻等優(yōu)點[9]，其數(shù)學表達形式如下：

其中，λ∈[0.9,1.08]，Singer映射具有混沌行為。

生成的混沌序列sk∈[0,1]，用于初始化GWO種群位置Xk，如下式所示：

其中，ub與lb為搜索空間的上界與下界。

2.2 非線性收斂因子

標準GWO算法通過收斂因子a調(diào)節(jié)參數(shù)A，從而平衡算法的全局搜索與局部搜索能力。復雜優(yōu)化問題往往存在多個局部最優(yōu)值，線性遞減的更新策略決定了算法的全局搜索過程僅為全期過程的一半，算法跳出局部最優(yōu)值的能力較弱。基于此，本文提出一種新的非線性收斂因子更新公式：

為了驗證本文提出非線性收斂因子的優(yōu)勢，列舉了文獻[5]與文獻[10]中的收斂因子更新策略，如下所示：

上述非線性收斂因子a的仿真如圖1所示。由圖1可以看出：與其他更新策略相比，在迭代前期，a取值較大且衰減速度較慢，全局搜索能力較強，促使種群在搜索空間內(nèi)廣泛搜索，有利于避免種群陷入局部最優(yōu)值。在迭代后期，a迅速衰減至較少的值，局部搜索能力較強，在小范圍內(nèi)精細搜索，有利于加速種群收斂。因此本文提出的非線性收斂因子更新策略可以更好地應用于非線性復雜優(yōu)化問題的求解。

圖1 非線性收斂因子曲線Fig.1 Nonlinear convergence factor curve

2.3 引入Levy飛行與動態(tài)權(quán)重策略

由式（8）可以看出，標準GWO算法種群位置更新公式僅由三頭精英狼主導，在搜索過程中，當精英狼陷入局部最優(yōu)時，種群搜索將陷入停滯。文獻[11]提出一種動態(tài)權(quán)重GWO算法，賦予三頭精英狼基于適應度值動態(tài)調(diào)節(jié)的比例權(quán)重，取得了更優(yōu)秀的收斂速度與尋優(yōu)精度，但是算法跳出局部最優(yōu)的能力較弱。文獻[12]證明布谷鳥算法中Levy飛行策略，可以增強算法的全局搜索能力，其特征是搜索范圍遠近交替地隨機飛行。文獻[13]將Levy飛行引入粒子群優(yōu)化（particle swarm optimization，PSO）算法，避免算法早熟收斂。本文在動態(tài)權(quán)重GWO基礎(chǔ)上引入Levy飛行策略，兩種種群個體的位置更新公式如式（15）、式（17）所示。為保證算法在迭代全期的搜索效率，采用貪心算法原則，比較式（15）與式（17）兩種個體位置的適應度值，采用適應度更優(yōu)的個體為最終的更新位置。

其中，bi(i=1,2,3)為基于適應度的比例權(quán)重，如下所示：

其中，f(Xi)(i=1,2,3)分別表示α、β、δ精英狼在目標函數(shù)下的適應度值；X"k(t+1)為采用Levy飛行策略更新后的灰狼個體位置；λ為步長調(diào)節(jié)系數(shù)，受文獻[14]的啟發(fā)，將式（11）的非線性調(diào)節(jié)策略應用于λ的更新，λmax=1，λmin=0。在迭代前期，較大的λ擴寬Levy飛行在解空間的搜索路徑。在迭代后期，較小的λ有利于提高算法的局部搜索能力，加速算法收斂。LV為飛行步長，計算公式如下：

u、v滿足正態(tài)分布定義如下：

其中，β通常取值于[0，2]之間，這里取值1.5。

2.4 LGWO算法流程

步驟1初始化參數(shù)，包括：種群規(guī)模N，最大迭代步長T，收斂因子a極值。

步驟2采用混沌映射初始化種群位置，記為：

步驟3計算種群適應度值，依據(jù)適應度大小確定α、β和δ狼。

步驟4依據(jù)式（11）更新收斂因子a，計算擾動因子A與C的值。

步驟5依據(jù)式（15）更新個體位置Xk，計算適應度值f(Xk)。

步驟6更新步長調(diào)節(jié)系數(shù)λ，依據(jù)式（17）更新個體位置X"k，計算適應度值f(X"k)。

步驟7比較f(Xk)與f(X"k)大小，若f(Xk)＜f(X"k)，Xk+1=Xk，否則Xk+1=X"k。

步驟8更新迭代步數(shù)，判斷是否達到最大迭代步長T，滿足則輸出全局最優(yōu)值，即α狼適應度值，未滿足返回步驟3。

算法1給出了LGWO算法的執(zhí)行偽代碼。

算法1 LGWO算法

Input：

d：the dimensions of the variables，T：the maximum number of iterations，N：population size，ub：upper bounds of variables，lb：lower bounds of variables，f(x)：the objective function

Output：

Xbest：the best solution vector，fbest：the optimal fitness value

1.Initialize the grey wolf populationXi(i=1,2,…,n)by singer mapping and calculate the fitness of each search agent to findXα，XβandXδ

2.Initializea，A，Cand step coefficientλ，then update iteration numbert=1

3.While(t＜T)

4.for each search agent

5.Generate Levy flight step according to equation（18）

6.Update the position of the current search agentXkby equation（15）and calculate the fitnessf(Xk)

7.Update the position of the current search agentX"kby equation（17）and calculate the fitnessf(X"k)

8.iff(Xk)＜f(X"k)then

9.Xk+1=Xk

10.else

11.Xk+1=X"k

12.end if

13.end for

14.Updatea，A，Candλ

15.Calculate the fitness of each search agent and updateXα，XβandXδ

16.t=t+1

17.end while

18.ReturnXbest=Xα，fbest=f(Xα)

2.5 算法復雜度分析

對于標準GWO算法，假設(shè)種群規(guī)模為N，最大迭代次數(shù)為T，自變量維度為d，其時間復雜度為O(N×T×d)[15]，本文提出的LGWO算法主要的執(zhí)行步驟時間復雜度分析如下：

（1）在初始化階段，采用Singer映射初始化種群，該階段時間復雜度為O1(N×d)。

（2）在主循環(huán)部分，假設(shè)標準GWO算法對于任意灰狼個體在任意維度更新位置的時間為t1，Levy飛行策略更新位置的時間為t2；對于任意灰狼個體，比較適應度優(yōu)劣并更新位置的時間為t3，則該階段時間復雜度為O2(N×T×d×(t1+t2)+N×T×t3)，當處理高維優(yōu)化問題時，時間復雜度可近似等于O2(N×T×d)。

綜上所述，LGWO算法的總體時間復雜度為O1+O2=O(N×d+N×T×d)=O(N×T×d)。因此，LGWO算法在標準GWO算法的基礎(chǔ)上并沒有增加額外的時間復雜度。

3 實驗仿真分析

3.1 測試函數(shù)及評價標準

為了驗證LGWO算法的尋優(yōu)性能。選用文獻[1]中8個國際通用的基準函數(shù)用于性能測試，如表1所示。其中，f1～f5為單峰函數(shù)，側(cè)重于驗證算法的收斂速度與尋優(yōu)精度，f6～f8為多峰函數(shù)，側(cè)重于反映算法跳出局部：最優(yōu)的能力。仿真實驗環(huán)境為：Win10 64位操作系統(tǒng)，Intel Core i5-9300H CPU，主頻2.40 GHz，內(nèi)存8 GB，Matlab R2020a。為保證實驗公平性，所有實驗均獨立測試30次，每次總迭代次數(shù)T為500次，種群數(shù)量N均為30。求取30次尋優(yōu)精度的平均值與標準差作為性能評價標準。其中，平均值反映算法的尋優(yōu)精度，標準差反映算法的魯棒性。以下對比實驗均加粗表示評價標準的最優(yōu)結(jié)果。

3.2 算法有效性分析

3.2.1 與標準GWO算法比較

為了驗證LGWO算法的尋優(yōu)性能，分別在低維d=30維，高維（d=100,500維）采用表1所示的8個基準函數(shù)進行性能測試，并與標準GWO算法對比。兩種算法非線性收斂因子a∈[0,2]。實驗結(jié)果如表2所示。

表1 基準函數(shù)Table 1 Benchmark functions

由表2可知：在低維與高維的所有測試函數(shù)中，LGWO算法的尋優(yōu)精度均優(yōu)于GWO算法，其中f1、f3、f6、f8收斂至全局最優(yōu)值0，f2、f4收斂至與0相當接近的尋優(yōu)精度，f5、f7尋優(yōu)精度較低，但LGWO算法均優(yōu)于標準GWO算法，且滿足函數(shù)的收斂精度要求。對于標準差的測試結(jié)果，除了f5、f7，LGWO算法的標準差均為0，表明LGWO具有優(yōu)秀的魯棒性。實驗結(jié)果表明：GWO算法在d=30維下，f1、f2、f7滿足函數(shù)收斂精度，但在高維100與500維下，GWO算法在所有測試函數(shù)均未滿足收斂精度要求。相比較LGWO算法，無論在30維與100、500維情況下，LGWO的尋優(yōu)成功率為100%，均滿足函數(shù)規(guī)定收斂精度，驗證了LGWO算法面對高維復雜優(yōu)化問題時的有效性。

表2 LGWO與GWO測試結(jié)果對比Table 2 Comparison of LGWO and GWO test results

圖2展示了兩種算法在部分單峰函數(shù)f1、f2，部分多峰函數(shù)f6、f7的適應度變化曲線，更直觀地展現(xiàn)LGWO相較于標準GWO算法的優(yōu)勢。由圖2可以看出，LGWO整體的收斂速度明顯優(yōu)于標準GWO算法，在f1、f7較早收斂至全局最優(yōu)值，而標準GWO算法在算法迭代后期適應度曲線陷入停滯，表明算法缺乏跳出局部最優(yōu)的能力，驗證了三種改進策略對于提高算法尋優(yōu)性能的有效性。

圖2 LGWO、GWO適應度變化曲線對比Fig.2 Comparison of fitness curves of LGWO and GWO

3.2.2 與改進GWO算法比較

為了驗證LGWO算法改進策略的優(yōu)勢，分別在d=30維度下8個基準函數(shù)進行測試，并與文獻[5]提出的基于精英個體重選策略與非線性收斂因子的改進GWO算法（EGWO）、基于停滯檢測的雙向搜索灰狼算法（DBGWO）[16]、融合粒子群算法的改進灰狼算法（PSO-GWO）[17]進行對比。為了實驗對比的公平性，對比算法的實驗結(jié)果均來自原參考文獻。

由表3可以看出，在低維d=30維條件下，LGWO在所有測試函數(shù)中尋優(yōu)成功率為100%。在多峰函數(shù)測試中，對于f7，NGWO算法取得了最優(yōu)尋優(yōu)精度為4.40E-16，而LGWO算法的尋優(yōu)精度為2.90E-15，兩者僅相差1個數(shù)量級。對于f8，EGWO算法與PSO-GWO算法的尋優(yōu)精度下降明顯，僅為4.99E-04與9.00E-04，表明這兩種算法的改進策略雖然一定程度上提高了GWO算法的全局搜索能力，但是并非在所有測試函數(shù)適用，存在局限性，而DBGWO算法與LGWO算法均收斂至理論最優(yōu)值0。綜合分析，LGWO算法在多峰函數(shù)測試中取得了優(yōu)秀的尋優(yōu)性能，驗證了該算法具有較強的全局尋優(yōu)能力。

表3 4種GWO改進算法尋優(yōu)結(jié)果比較Table 3 Comparison of optimization results of four GWO improved algorithms

在f1～f5的單峰函數(shù)測試中，LGWO算法在所有函數(shù)均取得了最優(yōu)的尋優(yōu)精度與標準差。對于f5，LGWO取得5.09E-05的尋優(yōu)精度，在四種算法中最優(yōu)且唯一滿足函數(shù)收斂精度。從f1～f4可以看出，三種對比算法的尋優(yōu)精度由高到低依次為DBGWO算法、PSO-GWO算法與EGWO算法，LGWO算法尋優(yōu)精度明顯優(yōu)于3種對比算法，驗證了本文改進策略有效提升了標準GWO算法的收斂精度。

針對標準差的實驗結(jié)果，LGWO算法除了f5、f7，在其他函數(shù)的尋優(yōu)精度保持穩(wěn)定，并在所有測試函數(shù)中取得最優(yōu)的標準差，表明LGWO算法面對復雜優(yōu)化問題依然保持有效性，具有良好的魯棒性。

3.2.3 與其他優(yōu)化算法比較

為了進一步驗證LGWO算法面對高維復雜優(yōu)化問題的有效性。在維度d=100維下，選取表1中8個基準函數(shù)進行實驗，并與混合策略改進的鯨魚優(yōu)化算法（MSWOA）[18]、基于協(xié)同進化的動態(tài)雙重自適應改進PSO算法（DDAPSO）[19]、基于曲線自適應與模擬退火的蝗蟲算法（SA-CAGOA）[20]進行性能對比。為了保證對比實驗的公平性，各個算法的參數(shù)設(shè)置均來源于原文獻，MSWOA算法非線性調(diào)節(jié)系數(shù)取2；DDAPSO算法慣性權(quán)重取值范圍[0.4，0.9]，學習因子取值范圍均為[0.5，2.2]，混沌參數(shù)為4；SA-CAGOA算法初始溫度為100，結(jié)束溫度為1，退火系數(shù)為0.95，玻爾茲曼常數(shù)為10，曲線自適應參數(shù)范圍取[0.000 01，1]。實驗的對比結(jié)果如表4所示。

由表4可以看出：在高維d=100維下，LGWO算法除了多峰函數(shù)f7，在其他函數(shù)的測試中均取得了最優(yōu)的尋優(yōu)精度與標準差，且均滿足函數(shù)收斂精度。在函數(shù)f7中，LGWO算法收斂于4.09E-15，與MSWOA算法取得的最優(yōu)精度8.88E-16接近。綜合分析，3種對比算法的尋優(yōu)精度由高至低依次為：MSWOA算法、SA-CAGOA算法與DDAPSO算法。DDAPSO算法在所有測試函數(shù)的尋優(yōu)精度平均值均不滿足收斂精度要求，表明該算法全局尋優(yōu)能力不足，缺乏跳出局部最優(yōu)的能力，容易過早收斂。MSWOA算法的尋優(yōu)性能明顯優(yōu)于DDAPSO算法與SA-CAGOA算法，在多峰函數(shù)f6與f8中收斂至理論最優(yōu)值0，但對于單峰函數(shù)的收斂精度與LGWO算法存在一定差距，比如在f2中，尋優(yōu)精度僅為2.09E-137，而LGWO算法取得了1.40E-266。

表4 4種優(yōu)化算法尋優(yōu)結(jié)果比較Table 4 Comparison of optimization results of four optimization algorithms

圖3給出了4種算法在函數(shù)f2、f4、f6、f7的適應度變化曲線。可以看出面對高維復雜優(yōu)化問題，DDAPSO算法無論面對單峰函數(shù)還是多峰函數(shù)，尋優(yōu)性能均受到很大程度的抑制，在迭代初期種群已陷入停滯，無法跳出局部最優(yōu)解。SA-CAGO算法稍優(yōu)于DDAPSO算法，但從f6、f7的收斂曲線可以看出與LGWO算法與MSGOA算法存在差距，兩者收斂速度與收斂精度均優(yōu)于SA-CAGOA算法。MSWOA算法的全局尋優(yōu)能力較強，僅次于LGWO算法，但在多峰函數(shù)f6與f7中收斂速度不如LGWO算法，并在單峰函數(shù)f2與f4中，在迭代前期，算法的全局搜索基本陷入停滯，在迭代后期才開始收斂于全局最優(yōu)值，而LGWO算法隨迭代次數(shù)穩(wěn)定向全局最優(yōu)值收斂，驗證了LGWO算法求解高維復雜尋優(yōu)問題時的優(yōu)勢。

圖3 4種優(yōu)化算法適應度曲線對比Fig.3 Comparison of fitness curves of four optimization algorithms

3.3 三種改進策略分析

為了分析LGWO算法三種改進策略對于GWO算法的影響。將采用改進混沌映射的GWO算法（CGWO）、采用非線性收斂因子的GWO算法（NLGWO）與采用新的位置更新方程的GWO算法（PGWO）在8個基準函數(shù)（d=30維）上進行實驗對比。對比結(jié)果如表5所示。

表5 三種改進策略實驗對比Table 5 Comparison of three improvement strategies

由表5可知，引入混沌映射的CGWO算法相較于標準GWO算法，尋優(yōu)精度與標準差有一定的提升，但是提升不明顯。表明種群初始均勻分布于搜索空間，在迭代前期，一定程度上提高了算法的搜索效率，但是在迭代后期對于算法性能的提升不大。NLGWO相較于CGWO性能更加優(yōu)異，在求解多峰函數(shù)f6、f8時滿足函數(shù)收斂精度要求，尤其在f8收斂至理論全局最優(yōu)值0。可見收斂因子非線性調(diào)節(jié)策略更適用于求解復雜優(yōu)化問題，前期與中期較大的收斂因子增強了算法的全局搜索能力，更大概率發(fā)掘全局最優(yōu)值；后期較小的收斂因子提高了算法收斂速度與精度。但是NLGWO在其他測試函數(shù)中對于算法尋優(yōu)精度沒有明顯提升。引入新的位置更新策略的PGWO算法在f1～f4、f6、f8的測試中的尋優(yōu)精度平均值明顯優(yōu)于其他算法，在f5、f7中，PGWO算法尋優(yōu)精度稍好于其他算法，并且滿足函數(shù)的收斂精度要求。對于標準差的測試結(jié)果，PGWO算法除了f5，標準差均為0，可見PGWO算法除了擁有優(yōu)異的尋優(yōu)精度，也具有較強的魯棒性。實驗結(jié)果表明：基于適應度的動態(tài)權(quán)重與Levy飛行的位置更新策略對于標準GWO算法的尋優(yōu)性能有較大的提升。

4 結(jié)語

針對標準GWO算法全局搜索能力不足，易陷入局部最優(yōu)等問題，本文通過Singer混沌映射初始化種群，提高算法搜索效率；引入非線性收斂因子更新策略，提高算法前期全局搜索能力與后期收斂速度；采用基于適應度的動態(tài)權(quán)重位置更新策略，提高尋優(yōu)精度，并與Levy飛行相結(jié)合，避免種群過早收斂。仿真實驗表明LGWO算法的尋優(yōu)精度與收斂速度有了較大的提升，并驗證了LGWO算法求解高維復雜優(yōu)化問題時的有效性與優(yōu)秀的魯棒性。