一種優化局部搜索能力的灰狼算法

王習濤

摘? 要： 灰狼算法是一種經典的群智能算法。針對灰狼算法局部搜索收斂較慢，易陷入局部最優且搜索精度不高的缺陷，提出一種新的灰狼算法。新算法通過增加α狼視野，賦予α狼主動搜索能力，在全局搜索的同時進一步提高了局部尋優精度，實現搜索結果的進一步優化。通過多個基準函數測試實驗、對比、分析發現，新算法較原始灰狼算法在收斂精度上有較大提高。

關鍵詞： 群智能算法; 灰狼算法; 優化; 局部搜索; 精度

中圖分類號：TP301.6? ? ? ? ? 文獻標識碼：A? ? ?文章編號：1006-8228（2020）12-53-03

Abstract： Gray wolf algorithm is a classical swarm intelligence algorithm. In this paper， a new gray wolf algorithm is proposed to solve the problems of gray wolf algorithm， which is easy to fall into local optimum， slow convergence and low search accuracy. In the new algorithm， by increasing alpha wolf's field of vision and giving alpha wolf the ability of active search， the local search accuracy is further improved and the search results are further optimized at the same time of global search. Compared with the original gray wolf algorithm， the new algorithm greatly improves the speed and accuracy of convergence according to the experimental test on several reference functions.

Key words： swarm intelligence algorithm; gray wolf algorithm; optimize; local search; accuracy

0 引言

群體智能優化算法是一種演化計算技術，是通過觀察自然界生物群體合作覓食的過程，模擬群體中各成員的共享信息和相互學習，不斷改變搜索方向，最終實現搜索結果優化的算法。較著名的群體智能算法有遺傳算法（GA）、人工蟻群算法（ACO）、粒子群算法（PSO）、人工蜂群算法（ABC）、灰狼算法（GWO）等。

2014年澳大利亞學者Mirjalili模仿灰狼圍攻、捕食獵物的過程提出了灰狼優化算法，并通過多個基準函數的優化對比發現，灰狼算法在優化精度和穩定性上要明顯優于粒子群算法（PSO）、差分進化算法（DE）和引力搜索算法（GSA）[1]。

灰狼算法結構簡單，需要調節的參數少，易于實現[2]，并且能自動調整收斂因子和信息反饋機制，能夠在全局搜索與局部開發中實現平衡，一經問世便廣受關注，但是同其他的群體優化算法一樣，灰狼算法也不可避免地存在易早熟，易陷入局部最優的問題，諸多學者進行了有針對性地優化改進[3-7]]，從整體上提高了算法的穩定性。然而在搜索后期，依然會出現精度不高的現象，這是因為尋優后期群體喪失多樣性，α狼只能根據自身、β狼和δ狼的位置進行位置調整，并且隨機的活動半徑存在跳躍，導致局部尋優精度不高。為此，本文在經典灰狼算法中為α狼開啟視野，增加α狼局部主動尋優能力，通過多個基準函數仿真實驗，顯示改進算法在局部尋優中表現更加出色，收斂精度較傳統算法明顯提高。

1 傳統灰狼算法

灰狼算法通過模擬自然界灰狼群體捕食過程中的等級分工和信息交互過程實現解空間中的尋優。灰狼算法將狼群分為四類：α狼、β狼、δ狼和其他狼，α狼、β狼、δ狼是狼群的首領，記錄狼群中最優的三個解，算法設計α狼、β狼、δ狼相對其他狼更加了解、靠近最優解，其他狼并不知道最優解的位置，因此，其他狼根據α狼、β狼、δ狼的位置自動地調整搜索范圍和步伐。每次調整后狼群會重新計算適應度，最優的三匹狼自動升級為α狼、β狼、δ狼，以此法迭代，實現對最優解的逐漸逼近，最終以α狼為最優解。

灰狼群體狩獵時，主要進行包圍、獵捕和攻擊等行為。算法通過α狼、β狼、δ狼和其他狼的初始化模擬灰狼實現對獵物的包圍。初始化后默認α狼、β狼、δ狼實現了對最優解的包圍。其他狼通過α狼、β狼、δ狼的引導實現位置更新，從而實現對最優解的圍捕，具體實現數學模式如下：利用式⑴計算當前狼與最優解的距離，式⑵計算當前狼的下一個位置。

通過反復迭代更新狼群位置并生成新的α狼、β狼、δ狼，狼群不斷逼近獵物，直至完成捕獲獵物（全局優化）這一目標。該過程主要通過式⑶中的a由2線性遞減到0來實現。相應地，A的值也在[-a，a]區間內取得任意值。當|A|<1時，狼群的下一個位置將更加接近獵物所在的位置，從而集中進行攻擊，這對應于算法的局部搜索; 當|A|>1時，狼群就會逐漸遠離獵物，這對應于算法的全局搜索。

2 改進的狼群算法

仔細觀察狼群圍捕過程可以發現，在圍捕的最后階段狼群圍繞獵物不斷移動，但代價函數的輸出卻不再縮小，究其原因是狼群多樣性缺失，α狼陷入局部最優，為此，本文提出為α狼增加主動搜索視野，使α狼不再被動局限于狼群更新帶來的優化，同時也具備局部搜索的能力。

假設α狼具備看到β狼的視野，這樣每次α狼、β狼、δ狼更新位置后α狼會在視野范圍內尋找比當前更優的位置并移動到更優位置，為了減少參數數量，假設α狼每次視野內局部尋優進行次數與狼群迭代次數相同，即程序會在α狼視野范圍內重復生成備選位置，與α狼比較并選取最優解。

為了進一步降低算法實現難度，提高程序運行效率，采用式⑿生成備選位置的第i維數據，因此，α狼在第i維空間的視野范圍為[[Xiα-absXiα-Xiβ，Xiα+absXiα-Xiβ]]，i=0，1…n，n為解空間維度。

本文GWO算法偽代碼：

[1、 Initializeiteration count （T）

2、 Initialize size of the pack （ pack_size）

3、 Initialize alpha、beta、delta wolf

4、 Initializethe grey wolf population（position）

5、 Calculate the fitness of each grey wolf in population

6、 For iter in （0， count（T））：

7、 ? Update alpha、beta、delta wolf

8、 ? For iter_select in （0， count（T））：

9、 ? ? ?Select a point in? [[Xiα-absXiα-Xiβ，[Xiα-absXiα-Xiβ]] 10、 ? ? ?If points fitness > alphas fitness：

11、 ? ? ? ? Alpha=point

12、 ? Update the grey wolf population by alpha、beta、delta wolf 13、 Output alpha wolf ]

3 實驗及對比分析

為了驗證算法的改進效果，本文利用6個常用基準函數對原始算法和本文算法進行運行對比，從算法最優值、均值和標準差等方面來進行比較分析。表1給出了6個基準測試函數的具體信息，表2給出了實驗結果記錄。

為了正確反映算法的運行效果，盡量減少偶然因素對運行結果的影響，所有算法的維度設置為30，狼群規模都設置為15，最大迭代次數設置為500，保證了新舊算法具備充足的種群規模和迭代次數，以保證都能達到收斂狀態。實驗連續運行10次，對比最優值，均值和方差。

表2顯示實驗數據結果，通過對比可以看出，無論是最優值、均值，還是方差，本文算法均顯著優于原始算法，從而可以證明，為α狼開啟視野，增加主動搜索動作能夠顯著優化搜索結果，對提升全局搜索精度有明確效果。

4 結束語

針對灰狼優化算法進入圍捕階段后局部搜索精度不高的現象，本文創新性地為α狼增加了局部視野，并使α狼在視野范圍內主動搜索最優解，從實驗數據可以看出，改進后的算法搜索精度遠高于傳統算法。群智能算法是解決NP問題的有效手段之一，在提高局部收縮優化的同時，如何進一步保證全局搜索的穩定性，進一步降低陷入局部最優的幾率，必將成為研究的方向。因此，下一步研究將圍繞全局與局部平衡能力、整體收斂速度展開，不斷優化灰狼算法搜索過程，提高搜索速度和精度。

參考文獻（References）：

[1] 郭振洲，劉然，拱長青，趙亮.基于灰狼算法的改進研究[J].計算機應用研究，2017.34（12）：3603-3606

[2] 張曉鳳，王秀英.灰狼優化算法研究綜述[J].計算機科學，2019.46（3）：30-38

[3] 邢尹，陳闖，劉立龍，程勝.求解函數最優解的改進灰狼算法[J].計算機仿真，2018.35（9）：258-262

[4] 郭玉純，曹小鵬，胡元嬌.禁忌搜索灰狼優化算法研究[J].計算機技術與發展，2019.29（12）：55-60

[5] 徐松金，龍文.嵌入遺傳算子的改進灰狼優化算法[J].蘭州理工大學學報，2016.42（4）：102-108

[6] 牛家彬，王輝.一種基于混合策略的灰狼優化算法[J].齊齊哈

[7] 魏政磊，趙輝，韓邦杰，孫楚，李牧東.具有自適應搜索策略的灰狼優化算法[J].計算機科學，2017.44（3）：259-263