一種優(yōu)化局部搜索能力的灰狼算法

王習(xí)濤

摘? 要： 灰狼算法是一種經(jīng)典的群智能算法。針對(duì)灰狼算法局部搜索收斂較慢，易陷入局部最優(yōu)且搜索精度不高的缺陷，提出一種新的灰狼算法。新算法通過(guò)增加α狼視野，賦予α狼主動(dòng)搜索能力，在全局搜索的同時(shí)進(jìn)一步提高了局部尋優(yōu)精度，實(shí)現(xiàn)搜索結(jié)果的進(jìn)一步優(yōu)化。通過(guò)多個(gè)基準(zhǔn)函數(shù)測(cè)試實(shí)驗(yàn)、對(duì)比、分析發(fā)現(xiàn)，新算法較原始灰狼算法在收斂精度上有較大提高。

關(guān)鍵詞： 群智能算法; 灰狼算法; 優(yōu)化; 局部搜索; 精度

中圖分類(lèi)號(hào)：TP301.6? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ?文章編號(hào)：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 引言

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

2014年澳大利亞學(xué)者M(jìn)irjalili模仿灰狼圍攻、捕食獵物的過(guò)程提出了灰狼優(yōu)化算法，并通過(guò)多個(gè)基準(zhǔn)函數(shù)的優(yōu)化對(duì)比發(fā)現(xiàn)，灰狼算法在優(yōu)化精度和穩(wěn)定性上要明顯優(yōu)于粒子群算法（PSO）、差分進(jìn)化算法（DE）和引力搜索算法（GSA）[1]。

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

1 傳統(tǒng)灰狼算法

灰狼算法通過(guò)模擬自然界灰狼群體捕食過(guò)程中的等級(jí)分工和信息交互過(guò)程實(shí)現(xiàn)解空間中的尋優(yōu)?；依撬惴▽⒗侨悍譃樗念?lèi)：α狼、β狼、δ狼和其他狼，α狼、β狼、δ狼是狼群的首領(lǐng)，記錄狼群中最優(yōu)的三個(gè)解，算法設(shè)計(jì)α狼、β狼、δ狼相對(duì)其他狼更加了解、靠近最優(yōu)解，其他狼并不知道最優(yōu)解的位置，因此，其他狼根據(jù)α狼、β狼、δ狼的位置自動(dòng)地調(diào)整搜索范圍和步伐。每次調(diào)整后狼群會(huì)重新計(jì)算適應(yīng)度，最優(yōu)的三匹狼自動(dòng)升級(jí)為α狼、β狼、δ狼，以此法迭代，實(shí)現(xiàn)對(duì)最優(yōu)解的逐漸逼近，最終以α狼為最優(yōu)解。

灰狼群體狩獵時(shí)，主要進(jìn)行包圍、獵捕和攻擊等行為。算法通過(guò)α狼、β狼、δ狼和其他狼的初始化模擬灰狼實(shí)現(xiàn)對(duì)獵物的包圍。初始化后默認(rèn)α狼、β狼、δ狼實(shí)現(xiàn)了對(duì)最優(yōu)解的包圍。其他狼通過(guò)α狼、β狼、δ狼的引導(dǎo)實(shí)現(xiàn)位置更新，從而實(shí)現(xiàn)對(duì)最優(yōu)解的圍捕，具體實(shí)現(xiàn)數(shù)學(xué)模式如下：利用式⑴計(jì)算當(dāng)前狼與最優(yōu)解的距離，式⑵計(jì)算當(dāng)前狼的下一個(gè)位置。

通過(guò)反復(fù)迭代更新狼群位置并生成新的α狼、β狼、δ狼，狼群不斷逼近獵物，直至完成捕獲獵物（全局優(yōu)化）這一目標(biāo)。該過(guò)程主要通過(guò)式⑶中的a由2線(xiàn)性遞減到0來(lái)實(shí)現(xiàn)。相應(yīng)地，A的值也在[-a，a]區(qū)間內(nèi)取得任意值。當(dāng)|A|<1時(shí)，狼群的下一個(gè)位置將更加接近獵物所在的位置，從而集中進(jìn)行攻擊，這對(duì)應(yīng)于算法的局部搜索; 當(dāng)|A|>1時(shí)，狼群就會(huì)逐漸遠(yuǎn)離獵物，這對(duì)應(yīng)于算法的全局搜索。

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

仔細(xì)觀(guān)察狼群圍捕過(guò)程可以發(fā)現(xiàn)，在圍捕的最后階段狼群圍繞獵物不斷移動(dòng)，但代價(jià)函數(shù)的輸出卻不再縮小，究其原因是狼群多樣性缺失，α狼陷入局部最優(yōu)，為此，本文提出為α狼增加主動(dòng)搜索視野，使α狼不再被動(dòng)局限于狼群更新帶來(lái)的優(yōu)化，同時(shí)也具備局部搜索的能力。

假設(shè)α狼具備看到β狼的視野，這樣每次α狼、β狼、δ狼更新位置后α狼會(huì)在視野范圍內(nèi)尋找比當(dāng)前更優(yōu)的位置并移動(dòng)到更優(yōu)位置，為了減少參數(shù)數(shù)量，假設(shè)α狼每次視野內(nèi)局部尋優(yōu)進(jìn)行次數(shù)與狼群迭代次數(shù)相同，即程序會(huì)在α狼視野范圍內(nèi)重復(fù)生成備選位置，與α狼比較并選取最優(yōu)解。

為了進(jìn)一步降低算法實(shí)現(xiàn)難度，提高程序運(yùn)行效率，采用式⑿生成備選位置的第i維數(shù)據(jù)，因此，α狼在第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 實(shí)驗(yàn)及對(duì)比分析

為了驗(yàn)證算法的改進(jìn)效果，本文利用6個(gè)常用基準(zhǔn)函數(shù)對(duì)原始算法和本文算法進(jìn)行運(yùn)行對(duì)比，從算法最優(yōu)值、均值和標(biāo)準(zhǔn)差等方面來(lái)進(jìn)行比較分析。表1給出了6個(gè)基準(zhǔn)測(cè)試函數(shù)的具體信息，表2給出了實(shí)驗(yàn)結(jié)果記錄。

為了正確反映算法的運(yùn)行效果，盡量減少偶然因素對(duì)運(yùn)行結(jié)果的影響，所有算法的維度設(shè)置為30，狼群規(guī)模都設(shè)置為15，最大迭代次數(shù)設(shè)置為500，保證了新舊算法具備充足的種群規(guī)模和迭代次數(shù)，以保證都能達(dá)到收斂狀態(tài)。實(shí)驗(yàn)連續(xù)運(yùn)行10次，對(duì)比最優(yōu)值，均值和方差。

表2顯示實(shí)驗(yàn)數(shù)據(jù)結(jié)果，通過(guò)對(duì)比可以看出，無(wú)論是最優(yōu)值、均值，還是方差，本文算法均顯著優(yōu)于原始算法，從而可以證明，為α狼開(kāi)啟視野，增加主動(dòng)搜索動(dòng)作能夠顯著優(yōu)化搜索結(jié)果，對(duì)提升全局搜索精度有明確效果。

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)（References）：

[1] 郭振洲，劉然，拱長(zhǎng)青，趙亮.基于灰狼算法的改進(jìn)研究[J].計(jì)算機(jī)應(yīng)用研究，2017.34（12）：3603-3606

[2] 張曉鳳，王秀英.灰狼優(yōu)化算法研究綜述[J].計(jì)算機(jī)科學(xué)，2019.46（3）：30-38

[3] 邢尹，陳闖，劉立龍，程勝.求解函數(shù)最優(yōu)解的改進(jìn)灰狼算法[J].計(jì)算機(jī)仿真，2018.35（9）：258-262

[4] 郭玉純，曹小鵬，胡元嬌.禁忌搜索灰狼優(yōu)化算法研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2019.29（12）：55-60

[5] 徐松金，龍文.嵌入遺傳算子的改進(jìn)灰狼優(yōu)化算法[J].蘭州理工大學(xué)學(xué)報(bào)，2016.42（4）：102-108

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

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