一種競爭策略的灰狼優(yōu)化算法

袁清晨 程夢杰 李時東 錢楷

摘要：群智能優(yōu)化算法已廣泛用于科學(xué)研究中，主要模擬自然界中的生物種群行為，灰狼優(yōu)化算法是一種模擬狼群捕獵模式的元啟發(fā)式算法。針對灰狼算法存在的局部最優(yōu)及收斂精度不高的問題，采用種群競爭策略和并行化技術(shù)來改進算法，并用四個基準(zhǔn)函數(shù)對所提出方法進行測試。結(jié)果表明，改進算法較原算法提高了收斂速度和精度，且有效減少了局部最優(yōu)的情況。

關(guān)鍵詞：群智能算法；并行化技術(shù)；種群競爭策略；灰狼優(yōu)化算法

中圖分類號：TP399 文獻標(biāo)識碼：A 文章編號：1007-9416（2018）08-0104-03

近幾十年來，人們提出了許多基于生物行為的算法，如進化算法、群體智能等，很多算法應(yīng)用于電源的優(yōu)化配置[1]、路徑優(yōu)化[2]、圖像分割處理[3]等方面。灰狼算法[4]是模擬狼群捕獵過程的優(yōu)化算法，最初是由S.Mirjalili等學(xué)者2015年提出的，針對灰狼算法過早收斂、易陷入局部最優(yōu)等缺點，人們做了大量的改進研究。Pan T S， Dao T K[5]采用了并行化和反向?qū)W習(xí)的種群溝通策略；Nasrabadi M S， Sharafi Y[6]對采用種群交流策略改進算法；牛家彬等[7]把動態(tài)權(quán)重和動態(tài)種群結(jié)合起來提高收斂速度的同時保證了解的質(zhì)量；崔明朗等[8]在尋優(yōu)過程中加入了觀察策略，且對收斂因子做了改進。

本文針對常規(guī)灰狼算法的缺點，提出以下改進方法：有多個狼群并行實施常規(guī)灰狼算法，在達到一定迭代次數(shù)后讓狼群相互競爭，剔除不良個體并更新種群，同時為了驗證改進算法的性能，進行了仿真實驗。

1 灰狼算法簡介

狼群的組織結(jié)構(gòu)根據(jù)領(lǐng)導(dǎo)權(quán)力進行排序，主要分為四個等級：、、、，高等級的狼對低等級的狼有領(lǐng)導(dǎo)權(quán)。在狩獵過程中，主要尋優(yōu)過程是由狼分散包圍獵物，其他三個等級根據(jù)收集到的信息指揮狼的移動方向，并決定是否更新自己的位置，當(dāng)滿足終止條件以后，輸出最優(yōu)解。

在狩獵過程中，獵物位置與灰狼位置可用式（1）-（2）表示：

其中：表示當(dāng)前迭代次數(shù)，為獵物的方向向量，為狼群中某狼的位置向量，為下一步移動方向向量，為獵物的移動系數(shù)。通過調(diào)整系數(shù)向量來控制搜索獵物的范圍，當(dāng)時，擴大搜索范圍尋找全局最優(yōu)；當(dāng)時，縮小搜索范圍尋找局部最優(yōu)。

其中：為收斂因子，隨著迭代次數(shù)從2線性遞減到0，max為最大迭代次數(shù)，、為0到1之間的隨機數(shù)。

當(dāng)狼群完成對獵物的包圍，由狼指揮狼和狼帶領(lǐng)狼群收縮包圍圈，狼群的位置更新用式（6）、（7）、（8）表示：

其中為狼的位置，為狼的位置，為狼的位置，為當(dāng)前狼的位置向量，、、為隨機向量。式（7）分別確定了狼朝向狼、狼、狼的前進方向與步長。

2 灰狼算法的改進

2.1 競爭策略

競爭策略灰狼算法是以常規(guī)灰狼算法為基礎(chǔ)的，在尋優(yōu)區(qū)域內(nèi)有個狼群進行獨立尋優(yōu)。兩個狼群的競爭可以理解為兩個局部最優(yōu)群體的比較，狼群中的個體都會逐步逼近狼群的狼，因此通過比較兩個狼群中的狼的適應(yīng)度判斷狼群的優(yōu)劣性，適應(yīng)度高的狼群留下來，適應(yīng)度低的狼群則被兼并。為了避免比較過程中出現(xiàn)局部最優(yōu)的情況，對兩個狼群進行相似度判斷，當(dāng)相似度小于一定值時才可以進行比較，否則重新初始化。

2.2 數(shù)學(xué)模型

2.2.1 相似度判定

設(shè)狼群的規(guī)模為，比較狼群與狼群的相似程度，狼群中按照適應(yīng)度值從大到小排列，狼群為，狼群為，計算公式如式（9）表示：

2.2.2 競爭方案

已知狼群與狼群，當(dāng)狼群與狼群滿足相似度條件并達到指定的迭代次數(shù)時，可以開始競爭。當(dāng)時，則狼群兼并狼群，淘汰狼群中處于領(lǐng)導(dǎo)地位的狼、狼、狼，將狼群中的狼并入狼群組成新狼群；否則狼群兼并狼群，作相同處理。

2.3 算法流程

（1）初始化個狼群位置以及系數(shù)、、，每一個狼群都通過灰狼算法獨立進行尋優(yōu)；（2）計算各個狼群的適應(yīng)度；（3）根據(jù)公式更新各狼群位置與相關(guān)參數(shù)；（4）可得出個狼群中的頭狼適應(yīng)度，指定在第次迭代，兩兩展開競爭，組成新狼群后再進行常規(guī)尋優(yōu)或是繼續(xù)參與競爭；（5）終止：達到函數(shù)的預(yù)定值或者達到最大迭代次數(shù)時，記錄最優(yōu)個體的值以及其適應(yīng)度。

3 實驗結(jié)果及分析

3.1 實驗設(shè)置

仿真將采用4種不同的算法（GWO常規(guī)灰狼算法；GWO1采用動態(tài)權(quán)值的灰狼算法；GWO2采用改進收斂因子的灰狼算法；GWO3采用競爭機制的并行灰狼算法），基于4個單目標(biāo)無約束的標(biāo)準(zhǔn)測試函數(shù)（如表1所示）測試比較各算法的收斂速度與求解精度。所有算法終止條件是滿足最大迭代次數(shù)500，群體規(guī)模都設(shè)置為30。

3.2 算法性能分析

4種算法對4個函數(shù)的求解結(jié)果見表2，列出了4種算法基于4個標(biāo)準(zhǔn)測試函數(shù)分別運行10次所取得的最優(yōu)值、最差值、平均最優(yōu)值及標(biāo)準(zhǔn)方差，并繪制單峰函數(shù)（、）、多峰多極值函數(shù)（、）的收斂曲線圖。

在單峰值函數(shù)的優(yōu)化過程中，各算法都有較好的優(yōu)化性能及較快的收斂速度，從表1看出在“最優(yōu)值”指標(biāo)和最差值方面，GWO3算法的收斂精度最高，然后依次是GWO1、GWO、GWO2，在“標(biāo)準(zhǔn)方差”指標(biāo)方面，求解結(jié)果的穩(wěn)定性排序依次是GWO3、GWO1、GWO2、GWO。由圖1可以看出在優(yōu)化過程中各算法都存在著局部最優(yōu)的現(xiàn)象，但GWO1的局部最優(yōu)情況最多，由此可見動態(tài)權(quán)值的引入雖然可以提高算法的收斂速度與精度，但也會加劇局部最優(yōu)的產(chǎn)生，相比之下GWO3的局部最優(yōu)現(xiàn)象較少，且在收斂精度及穩(wěn)定性上有很大的提高。

對多峰值多極值函數(shù)，各算法在“最優(yōu)值”、“最差值”、“平均最優(yōu)值”指標(biāo)上結(jié)果精度基本相同，由圖2可以看出，各算法的局部最優(yōu)情況增多了一些，尤其是采用動態(tài)權(quán)值的GWO1算法，采用平均權(quán)值的GWO算法和收斂因子的GWO2算法相對較輕，而采用競爭機制的GWO3算法有效減少了局部最優(yōu)的出現(xiàn)。

4 結(jié)語

本文提出了競爭機制的并行灰狼算法，設(shè)定有多個狼群并行實施常規(guī)灰狼算法，在達到一定條件后讓狼群間相互競爭，剔除不良個體并更新種群，由仿真結(jié)果可知，相比于其他改進，該改進方法可以提高算法的收斂精度和速度，在對多峰值多極值函數(shù)的優(yōu)化過程中可減少算法陷入局部最優(yōu)。此外，如何將改進的算法應(yīng)用到工程中的多目標(biāo)優(yōu)化問題是需要進一步研究的方向。

參考文獻

[1]張濤，張東方，王凌云.基于灰狼算法的分布式電源優(yōu)化配置[J].水電能源科學(xué)，2018，36（04）：204-207+212.

[2]姚鵬，王宏倫.基于改進流體擾動算法與灰狼優(yōu)化的無人機三維航路規(guī)劃[J].控制與決策，2016，31（04）：701-708.

[3]王鈦，許斌，李林國，等.基于離散灰狼算法的多級閾值圖像分割[J].計算機技術(shù)與發(fā)展，2016，26（07）：30-35.

[4]Mirjalili S， Mirjalili S M， Lewis A. Grey Wolf Optimizer[J]. Advances in Engineering Software， 2014， 69（3）：46-61.

[5]Pan T S， Dao T K， Nguyen T T， et al. A Communication Strategy for Paralleling Grey Wolf Optimizer[C]// International Conference on Genetic and Evolutionary Computing.Springer International Publishing，2015：253-262.

[6]Nasrabadi M S， Sharafi Y， Tayari M. A parallel grey wolf optimizer combined with opposition based learning[C]// Swarm Intelligence and Evolutionary Computation. IEEE， 2016：18-23.

[7]牛家彬，王輝.一種基于混合策略的灰狼優(yōu)化算法[J].齊齊哈爾大學(xué)學(xué)報（自然科學(xué)版），2018，34（01）：16-19+32.

[8]崔明朗，杜海文，魏政磊，等.多目標(biāo)灰狼優(yōu)化算法的改進策略研究[J].計算機工程與應(yīng)用，2018（5）：156-164.