一種優(yōu)化的灰狼算法

楊寒石, 吳皓月, 孔德貴

(1.黑龍江大學(xué) 電子工程學(xué)院, 哈爾濱 150080; 2.黑龍江大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院, 哈爾濱 150080)

0 引 言

傳統(tǒng)灰狼算法(Grey wolf algorithm，GWA)是一種模擬狼群狩獵行為的智能算法，已經(jīng)廣泛應(yīng)用于無(wú)人機(jī)航路規(guī)劃和電機(jī)控制等研究領(lǐng)域[1-4]。然而，GWA算法存在局部開(kāi)發(fā)能力較弱、早熟收斂和初始種群分布不均勻等問(wèn)題。針對(duì)這些問(wèn)題，學(xué)者們主要從種群初始化、控制參數(shù)、狼群搜索機(jī)制以及灰狼位置更新策略等方面對(duì)GWA算法進(jìn)行了優(yōu)化[5-7]。2015年，Saremi等將進(jìn)化種群動(dòng)態(tài)算子(Evolutionary population dynamic, EPD)引入到GWA算法中，顯著提高了算法的局部搜索能力和收斂速度[8]。2017年，龍文等采用佳點(diǎn)集法替代GWA算法中利用隨機(jī)數(shù)初始化種群的方法，增加了初始種群的多樣性[9]。2020年，甄永琦等將差分進(jìn)化算法(Differential evolution algorithm，DEA)與GWA算法相結(jié)合，利用DE算法的交叉算子和變異算子改進(jìn)灰狼位置更新公式，提高了GWA算法的局部開(kāi)發(fā)能力[10]。2020年，劉彬等利用競(jìng)爭(zhēng)策略動(dòng)態(tài)更新α狼、β狼和δ狼的位置，提高了GWA算法的全局搜索能力[11]。2021年，王穎等結(jié)合云模型理論，通過(guò)動(dòng)態(tài)權(quán)重法調(diào)整收斂因子，平衡GWA算法的全局搜索和局部開(kāi)發(fā)能力[12]。2021年，Mohammad等將維度學(xué)習(xí)搜索策略(Dimensional learning high，DLH)引入傳統(tǒng)灰狼算法，提高了算法的全局搜索能力和標(biāo)準(zhǔn)測(cè)試函數(shù)的尋優(yōu)精度[13]。這些對(duì)GWO算法的優(yōu)化均未考慮灰狼個(gè)體經(jīng)驗(yàn)對(duì)灰狼位置更新的影響以及算法后期種群多樣性喪失的問(wèn)題,會(huì)導(dǎo)致GWO算法局部開(kāi)發(fā)能力差、過(guò)早收斂和收斂精度低等問(wèn)題。針對(duì)這些問(wèn)題，本文從四個(gè)方面優(yōu)化了傳統(tǒng)的GWO算法，這里稱之為優(yōu)化的灰狼算法(Optimized grey wolf agorithm, OGWA)。第一，利用Cat映射和反向?qū)W習(xí)初始化種群，增加初始種群的多樣性；第二，在灰狼位置更新公式中引入粒子群算法(Particle swarm optimization,PSO)的個(gè)體經(jīng)驗(yàn)公式，避免算法提前收斂停滯；第三，用非線性控制參數(shù)替換傳統(tǒng)灰狼算法的線性控制參數(shù)，使收斂因子在算法前期緩慢遞減，在后期迅速遞減，改善了算法的搜索能力和開(kāi)發(fā)能力；第四，利用Levy飛行理論對(duì)α狼進(jìn)行全局搜索，維持算法后期種群的多樣性，降低算法后期陷入局部最優(yōu)的風(fēng)險(xiǎn)。通過(guò)與GWA算法、PSO算法和蟻群算法(Ant colony optimization,ACO)的仿真比較發(fā)現(xiàn)，LIGWA算法具有較高的求解精度和良好的穩(wěn)定性。

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

GWA算法是一種通過(guò)模擬灰狼群體等級(jí)制度和狩獵行為來(lái)實(shí)現(xiàn)參數(shù)尋優(yōu)的算法。GWA算法中將灰狼群體分為四個(gè)社會(huì)等級(jí)：第一等級(jí)是灰狼群體的領(lǐng)導(dǎo)者，稱為α狼，負(fù)責(zé)對(duì)狼群的狩獵對(duì)象、棲息地選擇等決策;第二等級(jí)稱為β狼，負(fù)責(zé)協(xié)助α狼管理群體;第三等級(jí)稱為δ狼，主要負(fù)責(zé)偵察和狩獵等工作；第四等級(jí)稱為ω狼，社會(huì)地位最低，需要服從前三個(gè)等級(jí)狼的領(lǐng)導(dǎo)。

(1)

(2)

(3)

式中：Rand1和Rand2表示[0,1]間的隨機(jī)數(shù)；a為線性控制參數(shù)，其值隨著迭代次數(shù)的增大線性遞減，計(jì)算如式(4)所示：

(4)

式中tmax為最大迭代次數(shù)。

在灰狼狩獵過(guò)程中，當(dāng)種群搜索到獵物位置時(shí)，α狼、β狼和δ狼距離獵物位置最近，因此，可以依據(jù)α狼、β狼和δ狼的位置Xα、Xβ和Xδ計(jì)算灰狼向獵物移動(dòng)的位置，具體如式(5)～式(8)所示。

首先由式(5)～式(7)計(jì)算出其余灰狼的移動(dòng)方向。

(5)

(6)

(7)

然后由式(8)更新灰狼的位置：

(8)

2 優(yōu)化的灰狼算法

2.1 Cat混沌映射和反向?qū)W習(xí)相結(jié)合的種群初始化策略

2015年，劉建軍等采用混沌映射初始化種群，可以增加初始種群的均勻性；2019年，張新明等在種群初始化的過(guò)程中引入反向?qū)W習(xí)理論可以增加初始種群的多樣性[14-15]。本文將Cat混沌映射和反向?qū)W習(xí)兩種方法相結(jié)合對(duì)種群進(jìn)行初始化，提高初始種群的多樣性和均勻性。Cat混沌映射具有較好的遍歷均勻性，可以使初始種群均勻分布，Cat映射的數(shù)學(xué)描述如式(9)所示[16]:

(9)

利用Cat混沌映射和反向?qū)W習(xí)初始化種群,首先,要利用Cat混沌映射產(chǎn)生N×D維初始解矩陣C，這里N代表種群規(guī)模，D代表維度。然后，利用反向?qū)W習(xí)理論為C中的每個(gè)初始解產(chǎn)生與之對(duì)應(yīng)的反向解，得到反向解矩陣O，計(jì)算公式為：

(10)

最后對(duì)初始解矩陣C和反向解矩陣O合并，得到2N×D維解矩陣J，對(duì)J中D個(gè)列向量的元素從小到大進(jìn)行排序，選取每一個(gè)列向量中較小的前N個(gè)元素作為初始解，組成N×D維的優(yōu)良種群矩陣。

2.2 引入粒子群個(gè)體位置更新策略

在灰狼狩獵的過(guò)程中，從式(5)～式(8)可以看出，灰狼的位置主要是根據(jù)α狼、β狼和δ狼的位置Xα、Xβ和Xδ進(jìn)行更新的，在位置更新中忽略了灰狼個(gè)體經(jīng)驗(yàn)，容易導(dǎo)致算法過(guò)早收斂[17-18]。相比較而言，PSO算法在位置更新方面有不容易過(guò)早收斂的優(yōu)勢(shì)。在優(yōu)化的灰狼算法中，利用PSO算法中更新粒子個(gè)體位置信息的方法更新灰狼個(gè)體的位置信息，灰狼位置更新式(8)可以寫成式(11)：

(11)

式中，灰狼個(gè)體位置更新公式：

vdi(+1)=w·(vdi(t)+G1·Rand3·(Xdi,α-Xdi(t))+G2·Rand4·(Xdi,β-Xdi(t))+G3·Rand5·(Xdi,δ-Xdi(t)))

(12)

G=2×Rand

(13)

2.3 非線性控制參數(shù)策略

(14)

式中：t為當(dāng)前的迭代次數(shù)；tmax為最大迭代次數(shù)。

圖1 收斂因子的變化曲線

2.4 引入Levy飛行更新α狼位置

在GWA算法中，α狼的位置代表最優(yōu)解。在搜尋獵物的過(guò)程中，所有的灰狼均向α狼靠近，這會(huì)導(dǎo)致種群在迭代過(guò)程中逐漸失去多樣性，使算法過(guò)早收斂[22]。針對(duì)這一不足，利用Levy飛行對(duì)α狼進(jìn)行位置更新，α狼位置更新公式為：

(15)

b=Random(size(αposion))

(16)

(17)

(18)

(19)

式中σu和σv分別由式(20)和式(21)計(jì)算:

(20)

σv=1

(21)

2.5 LIGWA算法步驟

綜上所述，優(yōu)化灰狼算法(LIGWA)的實(shí)現(xiàn)步驟如下：

Step1: 設(shè)置種群規(guī)模N、個(gè)體學(xué)習(xí)參數(shù)G1、G2、G3、δ和tmax。

Step2: 利用上面所述Cat映射和反向?qū)W習(xí)產(chǎn)生初始種群Xi，i=1,2,…,N。

Step3: 計(jì)算種群中灰狼個(gè)體的適應(yīng)度值并從小到大排序，將適應(yīng)度值最小的灰狼位置作為歷史最優(yōu)解Xα，適應(yīng)度值第二小的灰狼位置作為第二最優(yōu)解Xβ，適應(yīng)度值第三小的灰狼位置作為第三最優(yōu)解Xδ。

Step4: 利用式(15)～式(21)對(duì)α狼進(jìn)行全局搜索，更新α狼的位置。

Step5: 利用式(14)計(jì)算非線性控制參數(shù)a*，按照式(2)更新收斂因子。

Step6: 對(duì)除Step 3中確定的α狼、β狼和δ狼之外的灰狼個(gè)體按式(5)～式(7)計(jì)算灰狼移動(dòng)方向。

Step7: 利用式(11)更新灰狼位置。

Step8: 判斷算法當(dāng)前的迭代次數(shù)是否達(dá)到最大迭代次數(shù)tmax，若滿足，則輸出α狼的適應(yīng)度值，否則返回執(zhí)行Step 3重新計(jì)算適應(yīng)度值，更新Xα、Xβ和Xδ。

3 仿真實(shí)驗(yàn)與分析

3.1 標(biāo)準(zhǔn)測(cè)試函數(shù)

為了測(cè)試LIGWA算法的性能，選取6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行仿真實(shí)驗(yàn)，函數(shù)的表達(dá)式如表1所示。其中f1～f3為單峰函數(shù)，用來(lái)檢驗(yàn)算法的尋優(yōu)精度；f4～f6為連續(xù)多峰函數(shù)，用來(lái)檢驗(yàn)算法后期的局部開(kāi)發(fā)能力。

表1 標(biāo)準(zhǔn)測(cè)試函數(shù)

3.2 與GWA算法的比較分析

利用LIGWA算法和GWA算法分別對(duì)表1的函數(shù)進(jìn)行求解。仿真實(shí)驗(yàn)中兩種算法的狼群規(guī)模均為N=30，tmax=1 000。兩種算法分別獨(dú)立運(yùn)行30次，求解函數(shù)的最優(yōu)值、最差值、平均值和標(biāo)準(zhǔn)差。最優(yōu)值代表算法求解函數(shù)得到的最小值，最差值代表算法求解函數(shù)得到的最大值，平均值代表算法的求解精度，標(biāo)準(zhǔn)差代表算法的穩(wěn)定性。仿真實(shí)驗(yàn)結(jié)果如表2所示，函數(shù)收斂曲線如圖2～圖7所示。

表2 LIGWA算法和GWA算法的仿真實(shí)驗(yàn)結(jié)果對(duì)比

圖2 函數(shù)f1的收斂曲線

圖3 函數(shù)f2的收斂曲線

圖4 函數(shù)f3的收斂曲線

圖5 函數(shù)f4的收斂曲線

圖6 函數(shù)f5的收斂曲線

圖7 函數(shù)f6的收斂曲線

從表2中的對(duì)比結(jié)果可知， LIGWA算法在6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)上的求解精度均優(yōu)于GWA算法，其中在函數(shù)f6的計(jì)算上，LIGWA算法的求解精度高出了GWA算法大約1 015個(gè)數(shù)量級(jí)，說(shuō)明LIGWA算法能有效地提高全局搜索能力，降低算法后期陷入局部最優(yōu)的風(fēng)險(xiǎn)。LIGWA算法在函數(shù)f1～f4、f6上的標(biāo)準(zhǔn)差小于GWA算法，而在函數(shù)f5上的標(biāo)準(zhǔn)差比GWA高出1個(gè)數(shù)量級(jí)，表明LIGWA算法在大部分測(cè)試函數(shù)上具有較好的穩(wěn)定性。

由圖2～圖4可以看出，LIGWA算法的求解精度明顯高于GWA算法，說(shuō)明LIGWA算法能有效地提高算法前期的全局搜索能力和函數(shù)求解精度。由圖5～圖7中可以看出，GWA算法在種群迭代到500代之前就已經(jīng)收斂，而LIGWA算法在迭代到500代之后才開(kāi)始收斂，說(shuō)明LIGWA算法能夠提高局部開(kāi)發(fā)能力，改善了GWA算法后期容易陷入局部最優(yōu)和GWA算法收斂早熟的缺陷。由圖2～圖7也可以看出，相比于GWA算法，LIGWA算法的收斂速度較慢，這是由于LIGWA算法在灰狼位置更新過(guò)程中考慮了灰狼個(gè)體經(jīng)驗(yàn)對(duì)位置更新的影響，灰狼位置更新公式變得復(fù)雜，增加了計(jì)算時(shí)長(zhǎng)。所以，LIGWA算法是以犧牲收斂速度來(lái)提高函數(shù)求解精度以及平衡全局搜索和局部開(kāi)發(fā)能力的。

3.3 與其他算法的比較分析

為進(jìn)一步測(cè)試LIGWA算法的性能，將其與PSA算法和ACA算法進(jìn)行對(duì)比分析，實(shí)驗(yàn)結(jié)果如表3所示，其中PSO算法和ACO算法的仿真實(shí)驗(yàn)結(jié)果來(lái)源于徐辰華等數(shù)據(jù)[23]。

表3 不同算法的仿真實(shí)驗(yàn)結(jié)果對(duì)比

從表3可以看出，在單峰函數(shù)和多峰函數(shù)的求解精度上，LIGWA算法的求解精度明顯優(yōu)于PSO算法和ACO算法，其中在函數(shù)f4的求解上，LIGWA算法的求解精度達(dá)到了函數(shù)最小值0；在算法穩(wěn)定性上，LIGWA算法在函數(shù)f1～f6的標(biāo)準(zhǔn)差均小于PSO算法和ACA算法，其中LIGWA算法在函數(shù)f4上的標(biāo)準(zhǔn)差達(dá)到了0，證明本文提出的LIGWA算法是可行的。

4 結(jié) 論

為了解決傳統(tǒng)灰狼算法存在局部開(kāi)發(fā)能力弱、早熟收斂和初始種群分布不均勻等問(wèn)題，提出了一種優(yōu)化的灰狼算法。通過(guò)求解6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)并與GWA算法、PSO算法和ACO算法進(jìn)行對(duì)比，證明了優(yōu)化灰狼算法具有較高的求解精度，改善了GWA算法早熟收斂的缺點(diǎn)，提高了GWA算法后期的局部開(kāi)發(fā)能力，能夠有效地處理單峰和連續(xù)多峰函數(shù)的尋優(yōu)問(wèn)題，解決神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)和極限學(xué)習(xí)機(jī)等機(jī)器學(xué)習(xí)算法中目標(biāo)函數(shù)的優(yōu)化問(wèn)題。