采用動態權重和概率擾動策略改進的灰狼優化算法

陳 闖，Ryad Chellali，邢 尹

(1.南京工業大學 電氣工程與控制科學學院，南京 211816； 2.桂林理工大學 測繪地理信息學院，廣西 桂林 541004)

采用動態權重和概率擾動策略改進的灰狼優化算法

陳 闖1，Ryad Chellali1*，邢 尹2

(1.南京工業大學 電氣工程與控制科學學院，南京 211816； 2.桂林理工大學 測繪地理信息學院，廣西 桂林 541004)

針對基本灰狼優化(GWO)算法存在易陷入局部最優，進而導致搜索精度偏低的問題，提出了一種改進的GWO(IGWO)算法。一方面，通過引入由GWO算法系數向量構成的權值因子，動態調整算法的位置向量更新方程；另一方面，通過采用概率擾動策略，增強算法迭代后期的種群多樣性，從而提升算法跳出局部最優的能力。對多個基準測試函數進行仿真實驗，實驗結果表明，相對于GWO算法、混合GWO(HGWO)算法、引力搜索算法(GSA)和差分進化(DE)算法，所提IGWO算法有效擺脫了局部收斂，在搜索精度、算法穩定性以及收斂速度上具有明顯優勢。

元啟發式算法；灰狼優化算法；函數優化；權值因子；擾動策略

0 引言

近20年來，元啟發式算法得到了迅速發展。它源自于自然現象的啟發，在解決復雜計算問題時提供了一種新的手段，典型的有遺傳算法(Genetic Algorithm, GA)[1]、粒子群(Particle Swarm Optimization, PSO)算法[2]、差分進化(Differential Evolution, DE)算法[3]、引力搜索算法(Gravitational Search Algorithm, GSA)[4]等。

2014年，學者Mirjalili等[5]提出了一種新型的元啟發式算法——灰狼優化(Grey Wolf Optimizer, GWO)算法。它是一種模擬自然界灰狼群體狩獵行為的智能優化算法，以其快速收斂性、參數較少和編程易實現等優點而備受關注。GWO算法已經成功應用于傳感器網絡訓練[6]、直流電機最優控制[7]、經濟調度指派[8]、表面波參數優化[9]等領域。盡管GWO算法得到了廣泛的應用，但是基本GWO算法和其他優化算法一樣，面臨著易收斂于局部最優的缺陷。為此，許多研究人員展開了深入研究，并提出了一些改進策略，如Nasrabadi等[10]提出采用反向學習策略來增加種群多樣性，同時為了實現算法深度尋優，對算法進行并行化處理，但該改進策略加重了計算機運行負擔；龍文等[11]提出混沌和精英反向學習的混合策略來改進GWO算法，在高維優化問題上取得了較好效果，拓寬了GWO算法的應用范圍；Zhu等[12]構建了一種DE和GWO相混合的混合GWO(Hybrid GWO, HGWO)算法，但由于采取的是兩種優化算法之間的相互混合，改進后的算法體系過于龐大且尋優精度也不太理想；魏政磊等[13]提出利用位置矢量差來跳出局部最優，但由于算法迭代后期灰狼之間的位置矢量差很小，對灰狼位置的擾動能力一般。

基于以上研究者對GWO算法的改進研究經驗可知,找到一種簡單且高效的改進策略十分必要。本文考慮到算法位置更新向量中前三頭狼的不同特征，提出引入權值因子來動態調整算法的位置向量更新方程；同時為了擺脫局部最優，提出采用概率擾動策略來增強算法迭代后期的種群多樣性。通過對18個基準測試函數的仿真實驗，與4種優化算法作比較，實驗結果驗證了所提改進GWO(Improved GWO, IGWO)是有效的，從而為GWO算法的改進提供了一種新的思路。

1 基本灰狼優化算法

灰狼是位于食物鏈頂端的食肉型動物，多以群居為主，并構建了嚴格的金字塔式社會等級制度，如圖1所示。圖1中，等級最高的狼為α，其他依次為β、δ和ω。α是整個狼群的領導者，負責主要事務的決策；β是α的接替者，協助α的管理；δ服從α和β的領導，負責偵查和守衛整個狼群的安全；ω位于金字塔最底狼，完成高層狼交代的任務。

圖1 灰狼金字塔等級Fig. 1 Hierarchic pyramid of grey wolf population

對應于GWO算法函數優化問題時，適應度最高的個體被賦予α，兩個次優個體分別定義為β和δ，剩余的其他個體為ω。灰狼群體狩獵時，由α帶領，β和δ協助，其余ω聽從指揮，主要進行包圍、獵捕和攻擊三個步驟[14]，最終高成功率地捕獲獵物(全局最優解)。

首先，灰狼群對獵物進行包圍，該過程的數學描述為：

D=|C·Xp(t)-X(t)|

(1)

X(t+1)=Xp(t)-A·D

(2)

A=2a·r1-a

(3)

C=2r2

(4)

其中：Xp表示獵物的位置；X(t)表示第t代時灰狼個體的位置；A和C為系數向量；r1和r2為[0,1]之間取值的隨機向量；a為控制參數。

其次，灰狼群進行獵捕。該過程由α、β和δ狼來引導，更新灰狼個體位置，數學描述如下：

Dα=|C1·Xα-X(t)|

(5)

Dβ=|C2·Xβ-X(t)|

(6)

Dδ=|C3·Xδ-X(t)|

(7)

X1=Xα-A1·Dα

(8)

X2=Xβ-A2·Dβ

(9)

X3=Xδ-A3·Dδ

(10)

X(t+1)=(X1+X2+X3)/3

(11)

最后，灰狼群進行攻擊，完成捕獲獵物這一目標。攻擊行為主要依據式(3)中的a值隨迭代次數由2線性遞減到0來實現。當|A|≤1時，灰狼群對獵物集中攻擊，對應于局部搜索；當|A|>1灰狼散去，進行全局搜索。

2 改進灰狼優化算法

2.1 引入權值因子

基本GWO算法通過計算三個最佳灰狼位置的平均值來更新灰狼位置，這種策略并沒有考慮三頭狼在群體狩獵活動中的貢獻度問題。由于GWO算法的狼α并不一定是全局最優解，這時在不斷迭代中，隨著其余狼ω向這三頭狼逼近，這就容易陷入局部最優[15]。本文從最佳灰狼貢獻問題角度設計一種權重因子，用來提升GWO算法的尋優能力。由于GWO算法中的系數向量A和C是動態隨機的，而權重因子也應該隨著尋優過程非線性調整變化，為此本文設計的權重因子來源于系數向量A和C。在基本GWO算法中，A1、A2、A3以及C1、C2、C3是不相同的，在這里為了保證權重因子更新的相關聯性，設計A1、A2和A3相同，C1、C2和C3相同，如下：

A1=A2=A3=2a·r1-a

(12)

C1=C2=C3=2r2

(13)

那么，設計的位置向量權重因子分別為：

(14)

(15)

(16)

因此，得到新的位置更新公式為：

(17)

2.2 概率擾動策略

隨著GWO算法迭代次數的不斷增加，算法尋優逐漸趨于收斂，一旦收斂于局部最優很難跳出。在算法種群更新中加入擾動機制可以有效提升算法跳出局部最優的能力[16]。本文設計帶有一定概率的擾動來增強算法尋優后期的種群多樣性，為擺脫局部收斂創造有利條件。對于概率擾動策略，在以往的一些優化算法中有所研究，如胡宏梅等[17]提出采用隨機概率擾動方式作為基本粒子群算法的全局更新條件，從而增強全局尋優區域的搜索能力，但它采用的是模擬退火算法的退火概率，計算過于復雜；張偉[18]提出在差分進化算法中運用小概率擾動操作來增強種群的多樣性，但它采用固定的概率形式，無法在不同迭代過程中充分發揮擾動策略。為此，本文設計一種簡便且高效的擾動概率公式為：

(18)

M(t+1)=lb+r3·(ub-lb);r3

(19)

其中：M為擾動后的個體；lb為灰狼個體位置的下界；ub為灰狼個體位置的上界；r3為[0,1]之間取值的隨機向量。擾動后的灰狼個體基于貪婪機制進行更新，更新公式為：

(20)

其中：f(M(t+1))和f(X(t+1))分別表示第t+1代擾動個體M和灰狼個體X的目標函數值。

采用非線性收斂因子和概率擾動混合策略改進的GWO算法的偽代碼，見算法1。

算法1 采用動態權重和概率擾動改進的灰狼優化算法。

Initialize iteration count (T)

Initialize size of the pack (N)

Initialize the grey wolf populationXi(i=1,2,…,N)

Initializea,AandC

Calculate the fitness of each grey wolf

Xα=the best grey wolf

Xβ=the second best grey wolf

Xδ=the third best grey wolf

whilet≤Tdo

fort=1 toN

Calculate the disturbance probabilityP

ifrand()≥P

Calculate weights forα,βandδand by equation (14)～(16)

Update position vector by equation (17)

else

Generate random individualMby equation (19)

Update position vector by equation (20)

end if

end for

Updatea,AandC

Calculate the fitness of each grey wolf

UpdateXα,XβandXδ

end while

3 數值分析與實驗結果

3.1 測試函數和實驗設置

為了驗證IGWO算法的尋優性能，對18個基準測試函數進行測試，同時選取傳統的優化算法DE算法、GSA以及新型優化算法GWO算法、文獻[12]提出的HGWO算法進行比較。這18個基準測試函數分為三類:第一類為單峰基準測試函數F1～F6，如表1所示；第二類為多峰基準測試函數F7～F12，如表2所示；第三類為固定維度多峰基準測試函數F13～F18，如表3所示。為保證各算法公平以及達到收斂狀態，所有算法的種群規模設置為30，最大迭代次數設置為500。其中為了便于比較各算法，依照參考文獻[4]，GSA的常數α取20，G0取100；依照參考文獻[12]，DE算法的縮放因子F取0.5，交叉概率因子Pc取0.2。

表1 單峰基準測試函數Tab. 1 Unimodal benchmark test functions

表2 多峰基準測試函數Tab. 2 Multimodal benchmark test functions

3.2 實驗結果與分析

為了減少隨機性對結果的影響，各算法獨立運行30次，以30次結果平均值測試算法的搜索精度；30次結果的標準差測試算法的穩定性。IGWO、HGWO、GWO、GSA和DE算法對18個基準測試函數的測試結果，如表4～6所示。

從表4～6中可以看出，IGWO算法相對于HGWO算法，除函數F11、F12和F14～F18外，IGWO算法的搜索精度均優于HGWO算法，且搜索結果十分穩定；相對于算法GWO和GSA，除函數F15～F18外，無論搜索精度還是算法穩定性上，均體現出了明顯優勢；相對于DE算法，IGWO算法除對函數F12和F15～F18的尋優結果略遜色外，對于其他函數的搜索精度明顯好于DE算法，且算法穩定性更好。綜上，IGWO算法除對固定維度多峰基準函數尋優略遜色外，對于其他函數，IGWO算法的搜索精度更高，表現出良好的算法穩定性。

表3 固定維度多峰基準測試函數Tab. 3 Multimodal benchmark test functions with fixed-dimension

表4 單峰基準測試函數測試結果Tab. 4 Test results of unimodal benchmark test functions

表5 多峰基準測試函數測試結果Tab. 5 Test results of multimodal benchmark test functions

表6 固定維度多峰基準測試函數測試結果Tab. 6 Test results of multimodal benchmark test functions with fixed-dimension

為了進一步說明IGWO算法的優越性， 5種算法對不同函數的收斂曲線如圖2所示。考慮到篇幅限制，本文示例性列出了典型的6種基準測試函數的收斂曲線，具體為:單峰基準測試函數F1和F2，多峰基準測試函數F7和F8，固定維度多峰基準測試函數F13和F14。

圖2 不同算法對不同基準測試函數的目標函數值曲線Fig. 2 Objective function value curves of different algorithms for different benchmark test functions

從圖2中可以看出，不論單峰基準測試函數、多峰基準測試函數還是固定維度多峰基準測試函數，相對于HGWO、GWO、GSA和DE算法，IGWO算法具有更快的收斂速度，達到了更高的搜索精度。總的來說，IGWO算法的搜索性能優于另外4種尋優算法。

實驗中對IGWO算法的代碼進行分析知，IGWO算法的時間復雜度為O(TN)，相比基本GWO算法，它的時間復雜度并沒有改變，說明IGWO算法的計算效率依舊保持著較高水平。

4 結語

針對基本灰狼優化算法中位置向量更新方程的不合理性，本文提出引入動態的權值因子來調整算法的位置向量；針對算法易陷入局部最優的問題，本文提出采用概率擾動策略增強算法迭代后期的種群多樣性。通過對18個基準測試函數的仿真實驗，結果表明，與基本灰狼優化算法、混合灰狼優化算法、引力搜索算法和差分進化算法相比，本文提出的改進算法具有更高的搜索性能，克服了GWO算法在多峰基準測試函數優化中易陷入局部最優的缺點。此外，如何利用改進的灰狼優化算法解決支持向量機和神經網絡參數優化問題是下一步需要研究的方向。

References)

[1] TANG K S, MAN K F, KWONG S, et al. Genetic algorithms and their applications [J]. IEEE Signal Processing Magazine, 1996, 13(6): 22-37.

[2] KENNEDY J, EBERHART R. Particle swarm optimization [C]// Proceedings of the 1995 IEEE International Conference on Neural Networks. Piscataway, NJ: IEEE, 1995: 1942-1948.

[3] STORN R, PRICE K. Differential evolution: a simple and efficient heuristic for global optimization over continuous spaces [J]. Journal of Global Optimization, 1997, 11(4): 341-359.

[4] RASHEDI E, NEZAMABADI-POUR H, SARYAZDI S. GSA: a gravitational search algorithm [J]. Information Sciences, 2009, 179(13): 2232-2248.

[5] MIRJALILI S, MIRJALILI S M, LEWIS A. Grey wolf optimizer [J]. Advances in Engineering Software, 2014, 69(3): 46-61.

[6] MIRJALILI S. How effective is the grey wolf optimizer in training multi-layer perceptrons [J]. Applied Intelligence, 2015, 43(1): 150-161.

[7] MADADI A, MOTLAGH M. Optimal control of DC motor using grey wolf optimizer algorithm [J]. Technical Journal of Engineering and Applied Sciences, 2014, 4(4): 373-379.

[8] SONG H M, SULAIMAN M H, MOHAMED M R. An application of grey wolf optimizer for solving combined economic emission dispatch problems [J]. International Review on Modelling and Simulations, 2014, 7(5): 838-844.

[9] SONG X H, TANG L, ZHAO S T, et al. Grey wolf optimizer for parameter estimation in surface waves [J]. Soil Dynamics and Earthquake Engineering, 2015, 75: 147-157.

[10] NASRABADI M S, SHARAFI Y, TAYARI M. A parallel grey wolf optimizer combined with opposition based learning [C]// Proceedings of the 2016 1st Conference on Swarm Intelligence and Evolutionary Computation. Piscataway, NJ: IEEE, 2016: 18-23.

[11] 龍文,蔡紹洪,焦建軍,等.求解高維優化問題的混合灰狼優化算法[J].控制與決策,2016,31(11):1991-1997.(LONG W, CAI S H, JIAO J J, et al. Hybrid grey wolf optimization algorithm for high-dimensional optimization [J]. Control and Decision, 2016, 31(11): 1991-1997.)

[12] ZHU A J, XU C P, LI Z, et al. Hybridizing grey wolf optimization with differential evolution for global optimization and test scheduling for 3D stacked SoC [J]. Journal of Systems Engineering and Electronics, 2015, 26(2): 317-328.

[13] 魏政磊,趙輝,韓邦杰,等.具有自適應搜索策略的灰狼優化算法[J].計算機科學,2017,44(3):259-263.(WEI Z L, ZHAO H, HAN B J, et al. Grey wolf optimization algorithm with self-adaptive searching strategy [J]. Computer Science, 2017, 44(3): 259-263.)

[14] MITTAL N, SINGH U, SOHI B S. Modified grey wolf optimizer for global engineering optimization [J]. Applied Computational Intelligence and Soft Computing, 2016, 2016: Article ID 7950348.

[15] 郭振洲,劉然,拱長青,等.基于改進灰狼算法的RBF神經網絡研究[J].微電子學與計算機, 2017, 34(7):7-10.(GUO Z Z, LIU R, GONG C Q, et al. Study on RBF neural network based on gray wolf optimization algorithm [J]. Microelectronics & Computer, 2017, 34(7): 7-10.)

[16] 徐辰華,李成縣,喻昕,等.基于Cat混沌與高斯變異的改進灰狼優化算法[J].計算機工程與應用,2017,53(4):1-9.(XU C H, LI C X, YU X, et al. Improved grey wolf optimization algorithm based on chaotic cat mapping and Gaussian mutation [J]. Computer Engineering and Applications, 2017, 53(4): 1-9.)

[17] 胡宏梅,董恩清.基于粒子群算法的碼書設計研究[J].微電子學與計算機,2009,26(1):97-100.(HU H M, DONG E Q. Study of codebook design based on particle swarm optimization [J]. Microelectronics and Computer, 2009, 26(1): 97-100.)

[18] 張偉.差分進化算法的改進研究[D].西安：西安電子科技大學,2014:13-15.(ZHANG W. Improved research of differential evolution algorithm [D]. Xi’an: Xidian University, 2014: 13-15.)

CHENChuang, born in 1992, M. S. candidate. His research interests include optimization theory, speech signal processing.

RyadCHELLALI, born in 1964, Ph. D., professor. His research interests include robotics, virtual and augmented reality, machine learning.

XINYYin, born in 1992, M. S. candidate. Her research interests include machine learning, global navigation satellite system.

Improvedgreywolfoptimizeralgorithmusingdynamicweightingandprobabilisticdisturbancestrategy

CHEN Chuang1, Ryad CHELLALI1*, XING Yin2

(1.CollegeofElectricalEngineeringandControlScience,NanjingTechUniversity,NanjingJiangsu211816,China;2.CollegeofGeomaticsandGeoinformation,GuilinUniversityofTechnology,GuilinGuangxi541004,China)

The basic Grey Wolf Optimizer (GWO) algorithm is easy to fall into local optimum, which leads to low search precision. In order to solve the problem, an Improved GWO (IGWO) was proposed. On the one hand, the position vector updating equation was dynamically adjusted by introducing weighting factor derived from coefficient vector of the GWO algorithm. On the other hand, the probabilistic disturbance strategy was adopted to increase the population diversity of the algorithm at later stage of iteration, thus the ability of the algorithm for jumping out of the local optimum was enhanced. The simulation experiments were carried out on multiple benchmark test functions. The experimental results show that, compared with the GWO algorithm, Hybrid GWO (HGWO) algorithm, Gravitational Search Agorithm (GSA) and Differential Evolution (DE) algorithm, the proposed IGWO can effectively get rid of local convergence and has obvious advantages in search precision, algorithm stability and convergence speed.

meta-heuristic algorithm; Grey Wolf Optimizer (GWO) algorithm; function optimization; weighting factor; disturbance strategy

2017- 06- 23;

2017- 09- 07。

陳闖(1992—)，男，江蘇宿遷人，碩士研究生，主要研究方向：最優化理論、語音信號處理； Ryad Chellali(1964—)，男，法國人，教授，博士，主要研究方向：機器人、虛擬和增強現實、機器學習; 邢尹(1992—)，女，江蘇南通人，碩士研究生，主要研究方向：機器學習、全球導航衛星系統。

1001- 9081(2017)12- 3493- 05

10.11772/j.issn.1001- 9081.2017.12.3493

(*通信作者電子郵箱rchellali@njtech.edu.cn)

TP301.6

A