張 陽, 周溪召

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

元啟發(fā)式算法是一類在特定的資源（時間等）約束條件下求解問題近似最優(yōu)的優(yōu)化技術(shù)，具有簡單、高效和計算成本小等優(yōu)點。自1983 年Kirkpatrick等提出模擬退火算法（simulated annealing algorithm,SA）[1]和1992 年Holland 提出遺傳算法（genetic algorithm, GA）[2]以來，眾多學者投入到這一研究領(lǐng)域。經(jīng)過幾十年的發(fā)展，許多元啟發(fā)式算法相繼被提出并已廣泛應(yīng)用于研究領(lǐng)域和實際場景，如粒子群算法（particle swarm optimization, PSO）[3]、蟻群算法（ant colony optimization, ACO）[4]、引力搜索算法（gravity search algorithm, GSA）[5]、蘑菇繁殖算法（mushroom reproduction optimization, MRO）[6]、人工蜂群算法（artificial bee colony algorithm, ABC）[7]、教學優(yōu)化算法（teaching-learning-based optimization,TLBO）[8]和哈里斯鷹算法（Harris hawks optimization,HHO）[9]等。但是，根據(jù)沒有免費的午餐定理（NFL）[10]，沒有一種算法適用于求解所有問題，因此，仍有必要對元啟發(fā)式算法進行進一步的研究。

在文獻[6]中，元啟發(fā)式算法可以根據(jù)不同的靈感來源而分為3 類：群智能算法、非群智能算法和物理/化學算法。2014 年Mirjalili 等[11]受自然界中灰狼領(lǐng)導等級制度和群體狩獵行為啟發(fā)，提出了一種新的群智能算法—灰狼算法（grey wolf optimization, GWO）?；依撬惴ㄊ且环N強大的優(yōu)化技術(shù)，已被成功應(yīng)用于許多領(lǐng)域。譚念等[12]提出了一種基于灰狼算法和支持向量機（GWO-SVM）的木材密度預(yù)測模型，為杉木性質(zhì)定量分析提供了理論依據(jù)；姚鵬等[13]提出了一種基于改進的擾動流體動態(tài)系統(tǒng)與灰狼優(yōu)化理論的混合航路規(guī)劃算法，為復(fù)雜地形環(huán)境下的無人機三維航路規(guī)劃問題提供了解決方案；王書芹等[14]提出了基于灰狼優(yōu)化算法的長短期記憶模型（long short term memory, LSTM），解決了傳統(tǒng)LSTM 易于收斂到局部最優(yōu)的問題。

然而，同其他元啟發(fā)式算法一樣，灰狼算法也存在著收斂速度較慢、求解精度不高、在一些復(fù)雜問題上容易陷入局部最優(yōu)等缺點。為提升GWO 的性能，許多學者進行了相關(guān)研究。Joshi等[15]提出了一種基于精英策略的增強灰狼算法（enhanced grey wolf optimization, EGWO）；Heidari等[16]提出了結(jié)合列維飛行和貪婪搜索機制的灰狼算法（levy-embedded GWO, LGWO）；文獻[17]提出了基于模糊層次算子的灰狼算法，并提出了兩種個體位置更新時的比例權(quán)重策略；Saremi 等[18]提出了基于進化種群動力學（evolutionary population dynamics, EPD）的灰狼算法（GWO-EPD），EPD 要求表現(xiàn)不佳的搜尋個體進行動態(tài)的位置調(diào)整；王敏等[19]提出了一種基于反向?qū)W習策略、非線性收斂因子和變異算法的新型灰狼算法（novel GWO,NGWO）。在GWO 中，收斂因子a在一定程度上決定了算法局部開發(fā)過程和全局搜索過程之間的平衡。本研究首次提出了一種新的指數(shù)變化形式的收斂因子，而且與以前的所有針對a的改進之處所不同的是：提出的收斂因子最終并不會減小為0。同時為了加快算法的收斂速度，重新定義了灰狼算法中的 α，β，δ狼，并提出了一種基于自適應(yīng)調(diào)整策略的灰狼位置更新公式。此外，針對文獻中提出的動態(tài)權(quán)重策略進行修訂，以獲得更好的求解性能和魯棒性。最終，使用了10 個典型的基準測試函數(shù)驗證了以上改進策略的有效性。

1 灰狼優(yōu)化算法

灰狼優(yōu)化算法是一種較新的優(yōu)化技術(shù)，其主要思想是灰狼群體中的領(lǐng)導等級制度和群體狩獵模式。在自然界中，灰狼群體具有森嚴的社會等級制，如圖1 所示，狼群中所有個體劃分為4 個等 級： α，β，δ 及 ω。 α是 狼 群 的 領(lǐng) 袖； β僅 次 于α，其職責是輔助頭狼 α制定決策及其他群體性活動；接下來是δ，狼群中的偵察兵、哨兵、長老、狩獵者及看守者都屬于此類；等級最低的狼則為ω。除等級制度外，小組狩獵也是灰狼種群中一個有趣的社會行為。

圖1 灰狼種群社會等級結(jié)構(gòu)Fig.1 Social hierarchy structure of grey wolf population

在GWO 中，適應(yīng)度值最優(yōu)的個體被視為 α，適應(yīng)度值第二和第三的分別被定義為 β 和 δ，其余個體均為 ω。在算法實施中，以下等式用來描述灰狼種群包圍獵物的行為：

式中：t表示當前迭代次數(shù)；X(t)表示灰狼個體；Xp(t)表示當前的灰狼個體；D表示個體與獵物之間的距離；A和C是系數(shù)向量，分別用式（3）和式（4）來計算。

式中：r1，r2是0～1 之間的隨機向量；a表示收斂因子，可用等式a=2×(1-t/T)來計算，T為設(shè)定的最大迭代次數(shù)。

在狩獵時，GWO 假定 α，β，δ 對于獵物的潛在位置更具有感知性，所以，灰狼個體會分別判斷自身與α ，β，δ 之 間的距離Dα，Dβ，Dδ（式（5）），分別計算其朝向三者的移步距離X1，X2，X3（式（6）），并最終在向著三者的包圍圈之內(nèi)進行移步，移動公式為式（7）。

2 改進的灰狼優(yōu)化算法

2.1 指數(shù)規(guī)律收斂因子調(diào)整策略

全局搜索能力和局部開發(fā)能力是描述元啟發(fā)式算法性能的兩種通用屬性，如何有效平衡兩者也是元啟發(fā)式算法首要思考的問題。全局搜索是指在整個搜索空間搜尋最優(yōu)解，強的全局搜索性可使算法有效避免陷入局部最優(yōu)，增強算法的尋優(yōu)能力；局部開發(fā)能力是指在局部區(qū)域進行精確搜索，強的局部開發(fā)性能夠提升算法的求解精度、加快算法收斂速度。一般情況下，迭代的前期使用全局搜索策略，而在后期則使用局部開發(fā)策略。在GWO 中，當|A|>1 時，灰狼種群在整個搜索域搜尋潛在獵物；當|A|<1 時，灰狼種群將逐漸包圍并捕獲獵物。而A的值取決于收斂因子a的變化情況。

在GWO 中，a隨迭代的更新方式采用一種線性遞減策略，可用等式a=2(1-t/T)進行計算。在Chiu 等[20]的研究中已經(jīng)證明重要參量的不同更新策略會極大影響算法的性能，而且線性策略往往不是最有效的。因此，本文提出了一種新的基于指數(shù)規(guī)律變化的收斂因子更新方式，如式（8）所示。

如圖2 所示，線性表示GWO 中所使用的收斂因子更新方式，指數(shù)形式表示本文提出的新的收斂因子更新方式。

圖2 兩種收斂因子Fig.2 Two convergence factors

2.2 自適應(yīng)位置更新策略

在GWO 中，初始化 α，β，δ 三組解會被記錄并保留，直至在迭代的過程出現(xiàn)適應(yīng)值更好的個體代替它們?yōu)橹埂＞褪钦f，如果在第t代，種群中未出現(xiàn)優(yōu)于記錄的 α，β，δ的解時，當前的種群依然向著這三只狼更新位置。然而，當這三者全部陷入局部最優(yōu)時，此時整個種群就難以尋求更好的解。可以理解為：當狼群的決策者誤判了獵物出現(xiàn)的地方，那么，所有灰狼的包圍動作都將是無效的，它們難以在錯誤的地方找到獵物。

本文提出了一種新的 β 與 δ的定義方式以強化當前代最優(yōu)個體的作用，從而提升算法的全局搜索能力。在算法實施中， α同GWO 一樣，但是，β與 δ被 定義為局部變量，它們是第t(t=1,2,···,T)代中的適應(yīng)度值最優(yōu)和第二的灰狼個體。

同時，為了更好地平衡算法的全局搜索和局部開發(fā)過程，本文提出了一種新的自適應(yīng)的移步策略，其數(shù)學表達為

2.3 修訂的動態(tài)權(quán)重策略

在文獻[17]中指出了GWO 位置更新公式的缺點，X1，X2，X3求平均值的方式無法凸顯α，β，δ三者之間的重要度，為此，作者提出了兩種新的比例權(quán)重策略，分別是加權(quán)平均策略和基于適應(yīng)度值的比例權(quán)重策略，并進行了實驗驗證。文獻[21]提出了一種基于指導位置向量權(quán)值的動態(tài)比例權(quán)重。文獻[22]對不同的權(quán)重策略進行了分析與實驗研究，并從理論上證明了動態(tài)權(quán)重策略能高效尋優(yōu)的原因。

當前灰狼個體到 α ，β，δ之間的距離權(quán)重

最終，灰狼位置更新公式可表示為

然而，在實際應(yīng)用中，式（10）～（12）很可能出現(xiàn)分母為0 的情況。因此，需添加一個很小的常數(shù)ε，取值為10-16。它們被修改為

結(jié)合前面的自適應(yīng)位置更新策略，最終的灰狼位置更新方式可表示為

2.4 MGWO 算法步驟

綜合使用以上3 種改進策略，本文提出的改進灰狼優(yōu)化算法（MGWO）步驟如下：

a.參數(shù)初始化。設(shè)定種群規(guī)模N，總迭代次數(shù)T，常數(shù)ε；初始化a，A，C。

b.在待解問題的搜索空間內(nèi)隨機生成灰狼初始種群。

c.計算種群中所有灰狼個體的適應(yīng)值，選擇適應(yīng)度值最優(yōu)的個體，并記錄其位置為Xα。 令t=1，迭代開始。

d.判斷算法是否滿足終止條件，若滿足，則輸出最優(yōu)解；否則，執(zhí)行步驟e。

e.根據(jù)式（8）計算收斂因子a。

f.灰狼種群按適應(yīng)度值排序，排在前兩位的位置分別被記錄為Xβ和Xδ。

g.根據(jù)式（14）～（16）計算動態(tài)比例權(quán)重，灰狼個體根據(jù)式（17）更新位置。

h.將超出搜索空間的灰狼個體放回搜索空間。

i.更新Xα， 令t=t+1，返回步驟d。

3 實驗與分析

為了實驗驗證提出的3 種改進策略的有效性，選取了國際上通用的10 種基準測試函數(shù)進行仿真實驗。實驗運行環(huán)境為Intel（R）CPU 3550M，主頻2.30 GHz，內(nèi)存4 GB，Windows 10 64 位操作系統(tǒng)，所有代碼通過Python 3.7 進行編程。在此基礎(chǔ)上，進行了3 組對比實驗。為保證無偏性，所有算法的種群數(shù)N均設(shè)定為30，總迭代次數(shù)設(shè)定為500。為了排除隨機性的影響，所有實驗獨立運行30 次，取30 次的平均值和標準差作為算法性能的度量標準。

3.1 基準測試函數(shù)

基準函數(shù)的數(shù)學表達如表1 所示，包括7 個單峰測試函數(shù)（F1～F7）和3 個多峰測試函數(shù)（F8～F10）。單峰測試函數(shù)是算法求解精度和收斂速度的度量，而多峰測試函數(shù)可以很好地表示算法的全局搜索能力和避免局部最優(yōu)的能力。部分測試函數(shù)的3 維圖像如圖3 所示。

表1 基準測試函數(shù)Tab.1 Benchmark function

圖3 部分基準函數(shù)的二維搜尋空間Fig.3 Two-dimensional search space of a part of benchmark function

3.2 與GWO 和其他改進灰狼算法的比較

為了測試算法的搜尋性能，將提出的策略與其他文獻的策略進行比較。各比較算法及其描述如表2 所示。實驗結(jié)果如表3 所示。表3 中列出了各算法在基準測試函數(shù)上的測試結(jié)果。表格中粗體顯示的是最佳求解結(jié)果。表2 中從EGWO 到GWO-Fuzzy 的實驗結(jié)果直接來源于文獻[15-19]。其中，EGWO 的實驗環(huán)境為QT Creator 2.4.0；LGWO實驗運行環(huán)境為Intel（R）Core i2，主頻2 GHz，內(nèi)存4 GB，Windows 7 64 位操作系統(tǒng)，編程軟件為Matlab R2013a。

從表3 可以看出，提出的MGWO_1，MGWO_2算法在函數(shù)F1～F4 和F6～F9 上均優(yōu)于GWO 算法，而且在大多數(shù)問題上略優(yōu)于其他文獻提出的改進灰狼算法，這說明了提出的改進策略的有效性。同時，依據(jù)數(shù)值結(jié)果，MGWO_2 相比MGWO_1獲得更高的求解精度，這說明灰狼個體的自適應(yīng)位置更新策略是一種更優(yōu)的改進策略。

表2 對比算法及描述Tab.2 Comparison algorithms and its description

MGWO_3 綜合使用了指數(shù)規(guī)律收斂因子調(diào)整策略和自適應(yīng)位置更新策略，從結(jié)果可以看出，在函數(shù)F1～F4 上，MGWO_3 明顯優(yōu)于除MGWO_4外的其他對比算法。在函數(shù)F7 上，MGWO_3 排在MGWO_4 和NGWO 之后，勝過其他8 種對比算法。在函數(shù)F8 上，MGWO_3 僅次于MGWO_4，NGWO 和LGWO。在函數(shù)F9 上，MGWO_3 僅次于MGWO_4 和LGWO，優(yōu)于其他8 種算法。但是，在F6 和F10 上，MGWO_3 的結(jié)果并不理想。

MGWO_4 結(jié)合了本文提出的3 種改進策略，從表3 可以看出，它在函數(shù)F1，F(xiàn)3，F(xiàn)8 和F10上均收斂到理論最優(yōu)值。在函數(shù)F2，F(xiàn)4，F(xiàn)7 和F9 上，其求解精度明顯優(yōu)于其他算法。然而，對于函數(shù)F5 和F6，MGWO_4 表現(xiàn)一般。

在所有測試函數(shù)上各算法30 次獨立運行的運行總時間列于表4。從運行時間來看，在函數(shù)F1～F4，F(xiàn)7 和F8 上，GWO_EPD 所耗費的時間成本最小。在函數(shù)F5 上，MGWO_2 的運行時間要小于其他的對比算法。在函數(shù)F6，F(xiàn)9 和F10 上，GWO 的運行時間最短，優(yōu)于其他算法。在函數(shù)F7 和F8 上，GWO_EPD 的運行時間依然具有競爭性。

表3 11 種對比算法在10 個測試函數(shù)上的實驗結(jié)果Tab.3 Experimental results of 11 comparison algorithms on 10 test functions

表4 對比算法運行時間Tab.4 Running time of the comparison algorithms

綜上所述，本文提出的3 種改進策略都是有效的。綜合所有數(shù)值結(jié)果，MGWO_4 明顯優(yōu)于其他10 種對比算法，它具有很高的尋優(yōu)能力，獲得了較高的求解精度，同時從標準差來看，具有較高的魯棒性。MGWO_3，NGWO 和LGWO 僅次于MGWO_4，它們在特定的問題上表現(xiàn)突出，且都明顯改進了GWO 算法的性能。但是，也應(yīng)該認識到，MGWO_4 和MGWO_3 高效尋優(yōu)結(jié)果的代價是一定程度上時間成本的增加。而MGWO_1 和MGWO_2 可能是最佳選擇，它們對GWO 的性能提升幅度不如MGWO_4 和MGWO_3 那么大，但運行時間無明顯變化。具體選擇哪種算法，使用者要視自己的需求情況而定，如果對待求解問題的精度要求較高，MGWO_4 和MGWO_3 算法顯然是更好的選擇。

3.3 與其他元啟發(fā)式算法的比較

為進一步驗證本文改進策略的有效性，將表現(xiàn)較佳的MGWO_3，MGWO_4 與GA，TLBO，HHO 進行對比實驗。其中，GA 和TLBO 是經(jīng)典的優(yōu)化算法，HHO 是該領(lǐng)域最新的研究成果。其中，對于GA，使用輪盤賭的染色體復(fù)制策略、均勻雜交策略和隨機選擇突變3 種策略來進行編碼，染色體交配概率設(shè)置為0.8，突變概率設(shè)為0.3。其余算法均只有種群規(guī)模和總迭代次數(shù)2 個通用參數(shù)。實驗結(jié)果如表5 所示。

從表5 中的數(shù)值結(jié)果可知，對于函數(shù)F1 和F3，MGWO_4 在500 次迭代內(nèi)收斂到理論最優(yōu)值0，遠遠優(yōu)于其他的優(yōu)化算法；對于函數(shù)F8 和F10，MGWO_4，TLBO 和HHO 這3 種算 法 均達到理論最優(yōu)值0，但是，從收斂曲線（圖4）可以看出，MGWO_4 的收斂速度明顯高于TLBO 和HHO，所以，它依然是最佳算法；對于函數(shù)F2 和F4，MGWO_4 分別得到了3.14E-205 和1.23E-181 的最優(yōu)解，其求解精度相當高，遠勝于其他的優(yōu)化算法；對于函數(shù)F5 和F6，HHO 算法取得了最好的尋優(yōu)結(jié)果，其次是MGWO_3 與MGWO_4；對于函數(shù)F7，MGWO_4 獲得最佳求解結(jié)果，其次是TLBO 與MGWO_3。值得注意的是，對于8 個基準函數(shù)（F1，F(xiàn)2，F(xiàn)3，F(xiàn)4，F(xiàn)7，F(xiàn)8，F(xiàn)9，F(xiàn)10），MGWO_4 不僅取得了最優(yōu)的平均值，而且其標準差也是最小的，這說明了MGWO_4 算法具有較高的魯棒性。

表6 列出了GA，TLBO，HHO，MGWO_3 和MGWO_4 在10 個測試函數(shù)上30 次運行的總時間。從表6 中的數(shù)據(jù)可以看出，TLBO 和HHO 算法的求解時間明顯優(yōu)于其他的對比者，特別是對于單峰測試函數(shù)，這兩種算法的運行時間很短。而MGWO_3 和MGWO_4 算法的運行時間相對較長。

6 種算法（GWO，GA，TLBO，HHO，MGWO_3 和MGWO_4）在部分測試函數(shù)上的收斂曲線如圖4 所示。由圖4 可知，MGWO_3 提升了GWO的收斂速度和求解精度，MGWO_4 具有相當高的收斂速度和求解精度，遠優(yōu)于GWO 和其他的對比優(yōu)化算法。

以上兩組對比實驗驗證了本文提出了的3 種改進策略的實施效果，從運行時間來看，MGWO_1和MGWO_2 在提升GWO 的性能的基礎(chǔ)上運行時間無明顯變化，而MGWO_4 和MGWO_3 雖然在求解精度和收斂速度上有大幅度的提升，但帶來了程序運行的時間成本的增加。綜上所述，可以看出本文提出的MGWO 算法依然是一種更好的優(yōu)化算法。

表6 5 種對比算法在10 個測試函數(shù)上的運行時間Tab.6 Running time of the 5 comparison algorithms on 10 test functions

3.4 拉伸/壓縮彈簧設(shè)計優(yōu)化問題

以上兩組對比實驗所針對的問題都是無約束優(yōu)化問題，為進一步驗證本文改進策略的有效性，使用約束優(yōu)化問題繼續(xù)進行實驗。拉伸/壓縮彈簧設(shè)計優(yōu)化問題是一個經(jīng)典的帶約束的工程優(yōu)化問題，該問題的目的是在滿足3 個設(shè)計變量的4 個約束條件的情況下求得彈簧重量的最小值。3 個設(shè)計變量分別是線徑d，平均線圈直徑D和有效線圈數(shù)N；4 個約束條件與剪應(yīng)力、彈簧顫動頻率和最小撓度相關(guān)。圖5 描述了這一問題和其設(shè)計變量，該問題的數(shù)學表達如下：

設(shè)計變量

優(yōu)化函數(shù)

約束條件：

圖5 拉伸/壓縮彈簧設(shè)計優(yōu)化問題Fig.5 Tension/compression spring design problem

設(shè)計變量范圍：

使用7 種對比算法來求解這一約束優(yōu)化問題，算法在30 次實驗中所獲得的最佳實驗結(jié)果如表7所示。從表7 中的數(shù)據(jù)可以看出，MGWO_2 取得了最好的結(jié)果，優(yōu)于其他對比算法。MGWO_1 和MGWO_3 的數(shù)值結(jié)果也要優(yōu)于GWO 和其他算法。MGWO_4 雖然在無約束優(yōu)化問題時表現(xiàn)突出，但在求解拉伸/壓縮彈簧設(shè)計優(yōu)化問題時不如其他3 種MGWO 算法和GWO 算法。

表7 拉伸/壓縮彈簧問題的結(jié)果比較Tab.7 Comparison of results for the tension/compression spring problem

4 結(jié)束語

針對基本GWO 求解精度不高、收斂速度較慢和易于陷入局部最優(yōu)的問題，提出了一種改進的灰狼優(yōu)化算法。首先，提出了一種收斂因子指數(shù)變化規(guī)律的修正策略，處于這種策略下，a在迭代末期并不會減小為0，實驗結(jié)果驗證了其有效性。其次，通過重新定義 β 和δ 而強化每代最佳搜尋個體的作用，進而提出了一種灰狼個體自適應(yīng)位置更新策略。此外，引入動態(tài)權(quán)重策略，并對其進行了修訂。接著，針對無約束優(yōu)化問題的對比測試實驗證明了改進策略的有效性，尤其是綜合使用3 種改進策略的MGWO_4 具有較強的局部最優(yōu)避免性、較快的收斂速度、較高的求解精度，它明顯提升了基本GWO 的性能，更好地平衡了算法的全局搜索性和局部開發(fā)性。最后，對于工程設(shè)計約束優(yōu)化問題的實驗結(jié)果進一步證明了本文提出的MGWO 的有效性。

未來的研究思路是編寫二進制的MGWO，并將MGWO 運用到更多的實際問題中。