一種競爭策略的灰狼優化算法

袁清晨 程夢杰 李時東 錢楷

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

關鍵詞：群智能算法；并行化技術；種群競爭策略；灰狼優化算法

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

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

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

1 灰狼算法簡介

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

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

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

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

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

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

2 灰狼算法的改進

2.1 競爭策略

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

2.2 數學模型

2.2.1 相似度判定

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

2.2.2 競爭方案

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

2.3 算法流程

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

3 實驗結果及分析

3.1 實驗設置

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

3.2 算法性能分析

4種算法對4個函數的求解結果見表2，列出了4種算法基于4個標準測試函數分別運行10次所取得的最優值、最差值、平均最優值及標準方差，并繪制單峰函數（、）、多峰多極值函數（、）的收斂曲線圖。

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

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

4 結語

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

參考文獻

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

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

[3]王鈦，許斌，李林國，等.基于離散灰狼算法的多級閾值圖像分割[J].計算機技術與發展，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]牛家彬，王輝.一種基于混合策略的灰狼優化算法[J].齊齊哈爾大學學報（自然科學版），2018，34（01）：16-19+32.

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