采用動態(tài)權(quán)重和概率擾動策略改進(jìn)的灰狼優(yōu)化算法

陳 闖，Ryad Chellali，邢 尹

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

采用動態(tài)權(quán)重和概率擾動策略改進(jìn)的灰狼優(yōu)化算法

陳 闖1，Ryad Chellali1*，邢 尹2

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

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

元啟發(fā)式算法；灰狼優(yōu)化算法；函數(shù)優(yōu)化；權(quán)值因子；擾動策略

0 引言

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

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

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

1 基本灰狼優(yōu)化算法

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

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

對應(yīng)于GWO算法函數(shù)優(yōu)化問題時，適應(yīng)度最高的個體被賦予α，兩個次優(yōu)個體分別定義為β和δ，剩余的其他個體為ω?；依侨后w狩獵時，由α帶領(lǐng)，β和δ協(xié)助，其余ω聽從指揮，主要進(jìn)行包圍、獵捕和攻擊三個步驟[14]，最終高成功率地捕獲獵物(全局最優(yōu)解)。

首先，灰狼群對獵物進(jìn)行包圍，該過程的數(shù)學(xué)描述為：

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為系數(shù)向量；r1和r2為[0,1]之間取值的隨機向量；a為控制參數(shù)。

其次，灰狼群進(jìn)行獵捕。該過程由α、β和δ狼來引導(dǎo)，更新灰狼個體位置，數(shù)學(xué)描述如下：

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)

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

2 改進(jìn)灰狼優(yōu)化算法

2.1 引入權(quán)值因子

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

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

(12)

C1=C2=C3=2r2

(13)

那么，設(shè)計的位置向量權(quán)重因子分別為：

(14)

(15)

(16)

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

(17)

2.2 概率擾動策略

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

(18)

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

(19)

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

(20)

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

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

算法1 采用動態(tài)權(quán)重和概率擾動改進(jìn)的灰狼優(yōu)化算法。

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 數(shù)值分析與實驗結(jié)果

3.1 測試函數(shù)和實驗設(shè)置

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

表1 單峰基準(zhǔn)測試函數(shù)Tab. 1 Unimodal benchmark test functions

表2 多峰基準(zhǔn)測試函數(shù)Tab. 2 Multimodal benchmark test functions

3.2 實驗結(jié)果與分析

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

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

表3 固定維度多峰基準(zhǔn)測試函數(shù)Tab. 3 Multimodal benchmark test functions with fixed-dimension

表4 單峰基準(zhǔn)測試函數(shù)測試結(jié)果Tab. 4 Test results of unimodal benchmark test functions

表5 多峰基準(zhǔn)測試函數(shù)測試結(jié)果Tab. 5 Test results of multimodal benchmark test functions

表6 固定維度多峰基準(zhǔn)測試函數(shù)測試結(jié)果Tab. 6 Test results of multimodal benchmark test functions with fixed-dimension

為了進(jìn)一步說明IGWO算法的優(yōu)越性， 5種算法對不同函數(shù)的收斂曲線如圖2所示?？紤]到篇幅限制，本文示例性列出了典型的6種基準(zhǔn)測試函數(shù)的收斂曲線，具體為:單峰基準(zhǔn)測試函數(shù)F1和F2，多峰基準(zhǔn)測試函數(shù)F7和F8，固定維度多峰基準(zhǔn)測試函數(shù)F13和F14。

圖2 不同算法對不同基準(zhǔn)測試函數(shù)的目標(biāo)函數(shù)值曲線Fig. 2 Objective function value curves of different algorithms for different benchmark test functions

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

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

4 結(jié)語

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

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] 龍文,蔡紹洪,焦建軍,等.求解高維優(yōu)化問題的混合灰狼優(yōu)化算法[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] 魏政磊,趙輝,韓邦杰,等.具有自適應(yīng)搜索策略的灰狼優(yōu)化算法[J].計算機科學(xué),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] 郭振洲,劉然,拱長青,等.基于改進(jìn)灰狼算法的RBF神經(jīng)網(wǎng)絡(luò)研究[J].微電子學(xué)與計算機, 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ìn)灰狼優(yōu)化算法[J].計算機工程與應(yīng)用,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] 胡宏梅,董恩清.基于粒子群算法的碼書設(shè)計研究[J].微電子學(xué)與計算機,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] 張偉.差分進(jìn)化算法的改進(jìn)研究[D].西安：西安電子科技大學(xué),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—)，男，江蘇宿遷人，碩士研究生，主要研究方向：最優(yōu)化理論、語音信號處理； Ryad Chellali(1964—)，男，法國人，教授，博士，主要研究方向：機器人、虛擬和增強現(xiàn)實、機器學(xué)習(xí); 邢尹(1992—)，女，江蘇南通人，碩士研究生，主要研究方向：機器學(xué)習(xí)、全球?qū)Ш叫l(wèi)星系統(tǒng)。

1001- 9081(2017)12- 3493- 05

10.11772/j.issn.1001- 9081.2017.12.3493

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

TP301.6

A