基于維度學(xué)習(xí)狩獵搜索策略的改進(jìn)灰狼算法

周建新,鄭日成,侯宏瑤

(華北理工大學(xué)電氣工程學(xué)院,河北唐山 063210)

0 引言

在智能優(yōu)化領(lǐng)域,解決優(yōu)化問題通常是在規(guī)定的搜索空間和約束條件下尋找到全局最優(yōu)值。在現(xiàn)實(shí)中,大多數(shù)的優(yōu)化問題都面臨著以下問題：計(jì)算成本高、非線性約束、搜索環(huán)境復(fù)雜,以及帶有一定的干擾性。因此,面對這些復(fù)雜問題,最佳控制點(diǎn)往往很難找到。但隨著SI算法的出現(xiàn),可以快速尋找到最佳控制點(diǎn),為解決復(fù)雜優(yōu)化問題提供了一種全新的思路。目前SI算法可以分為兩類。第1類為非自然啟發(fā)式算法,主要有禁忌搜索(TS)、正余弦算法(SCA)、模擬退火算法(SA)以及向量加權(quán)平均算法(INFO)等;第2類為自然啟發(fā)式算法,其中經(jīng)典的是粒子群算法(PSO)、蟻群算法(ACO),近些年來,許多學(xué)者也提出了一些新興的智能優(yōu)化算法,例如灰狼算法(GWO)、跳蛛優(yōu)化算法(JSOA)、蛇優(yōu)化算法(SO)、沙貓群算法(SCSO)、鵜鶘優(yōu)化算法(POA)、白鯊優(yōu)化算法(WSO)、金豺優(yōu)化算法(GJO)等。雖然各類算法有不同的迭代過程,但它們對于解決具有連續(xù)搜索空間的復(fù)雜問題都有優(yōu)良的效果。

灰狼優(yōu)化算法主要通過模擬灰狼群體狩獵行為而被Mirjalili等于2014年提出,由于在解決函數(shù)優(yōu)化問題上具有收斂速度快和參數(shù)控制少等優(yōu)點(diǎn)而受到廣泛關(guān)注。目前,灰狼算法在故障診斷、路徑規(guī)劃、電池狀態(tài)預(yù)測、分類識別[1-4]等領(lǐng)域被廣泛應(yīng)用。雖然灰狼算法已被廣大學(xué)者關(guān)注并應(yīng)用,但基本的GWO算法與其他SI算法一樣,都有易陷入局部最優(yōu)值等缺陷。為此,如何加快GWO算法的全局尋優(yōu)能力成為當(dāng)前研究的熱點(diǎn)。文獻(xiàn)[5]通過迭代次數(shù)改變收斂因子大小來改進(jìn)灰狼算法,從而提高算法的尋優(yōu)性能;文獻(xiàn)[6]通過Tent映射和SA算法來改進(jìn)灰狼算法,提高了種群的收斂精度;文獻(xiàn)[7]提出了布谷鳥和灰狼算法結(jié)合的混合算法來提高收斂精度,從而促進(jìn)灰狼的尋優(yōu)過程;文獻(xiàn)[8]采用正余弦算法優(yōu)化灰狼算法;文獻(xiàn)[9]提出差分進(jìn)化和灰狼結(jié)合的混合算法,使得灰狼個(gè)體的全局探索能力得到提升;文獻(xiàn)[10]通過在灰狼算法的位置更新中引入粒子群算法的更新機(jī)制,從而提高灰狼群體的多樣性和自身的尋優(yōu)能力。雖然大多數(shù)改進(jìn)方法能改善基本GWO算法的性能,但算法在收斂精度和收斂速度之間依然難以取得平衡。

因此,為了解決上述問題,采用了PWLCM映射—準(zhǔn)反向?qū)W習(xí)策略進(jìn)行初始化和非線性余弦收斂因子來提高種群的收斂速度,同時(shí)引入變權(quán)重對第一候選解進(jìn)行位置更新,最后采用維度學(xué)習(xí)狩獵搜索策略產(chǎn)生的候選解和第一候選解進(jìn)行比較,從而選出全局最優(yōu)解。仿真結(jié)果表明,改進(jìn)的灰狼算法能顯著提高算法的優(yōu)化精度。

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

在GWO中,灰狼可分為α、β、σ、ω4個(gè)等級,如圖1所示。

圖1 灰狼群體社會等級示意圖

在GWO算法求解各類復(fù)雜優(yōu)化問題時(shí),其尋優(yōu)過程主要分為包圍、追捕、攻擊3個(gè)階段[11]。

1.1 包圍

在GWO中,灰狼狩獵過程中通過式(1)、式(2)實(shí)現(xiàn)對獵物的包圍：

X(t+1)=Xp(t+1)-AD

(1)

D=|CXp(t)-X(t)|

(2)

式中：X(t+1)為灰狼位置;Xp為獵物的位置;D為灰狼與獵物距離;A、C為控制系數(shù)。

A、C定義如式(3)和式(4)決定。

A=2ar1-a

(3)

C=2r2

(4)

式中：r1、r2為在[0,1]內(nèi)的隨機(jī)數(shù)向量;a為收斂因子。

1.2 追捕

在自然界中,雖然狼群狩獵過程通常由頭狼α引導(dǎo),其他等級的狼配合對獵物進(jìn)行包圍、追捕和攻擊,但在追捕的過程中,獵物位置Xp是未知的,因此根據(jù)α(潛在最優(yōu)解)、β和σ對獵物的位置有更多認(rèn)知的這一特性建立模型,迭代過程中采用α、β和σ來指導(dǎo)ω的移動(dòng),從而實(shí)現(xiàn)全局優(yōu)化。其灰狼位置更新如式(5)～式(7)所示：

(5)

(6)

(7)

1.3 攻擊

在灰狼攻擊的過程中,收斂因子a在迭代過程中起著至關(guān)重要的作用,其更新公式如式(8)所示：

a=2-2t/T

(8)

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

2 混合算法改進(jìn)策略

2.1 PWLCM映射—準(zhǔn)反向?qū)W習(xí)策略

在群智能算法中,種群初始化伴隨著隨機(jī)性,但這種隨機(jī)生成的種群位置會造成算法種群分布不均,且難以維持種群的多樣性,從而導(dǎo)致算法搜索范圍小,尋優(yōu)精度差。然而PWLCM混沌映射可以讓初始種群分布范圍更廣,且分布更加均勻,從而維持種群的多樣性,改善算法的全局尋優(yōu)能力。其數(shù)學(xué)表達(dá)式如式(9)所示：

(9)

式中p=0.4。

PWLCM混沌映射也存在受限周期和不穩(wěn)定周期點(diǎn)。因此在種群初始化過程中引入準(zhǔn)反向?qū)W習(xí)策略,如式(10)所示[12]：

(10)

經(jīng)過PWLCM混沌映射和準(zhǔn)反向?qū)W習(xí)策略求得N個(gè)反向解進(jìn)行合并,然后將從這2N個(gè)個(gè)體適應(yīng)度值進(jìn)行排序,從中篩選出適應(yīng)值高的N個(gè)個(gè)體當(dāng)做種群初始化的最終種群。

2.2 收斂因子的改進(jìn)

在灰狼個(gè)體迭代過程中,其全局尋優(yōu)和局部尋優(yōu)主要依據(jù)a決定[13]。然而收斂因子a是一個(gè)線性遞減的數(shù)值,但在處理一些實(shí)際問題中,收斂因子往往不能進(jìn)行全局搜索,容易使算法早熟,陷入局部最優(yōu)。因此為了提高灰狼個(gè)體的搜查能力,采用非線性的余弦收斂因子并增加一個(gè)隨機(jī)擾動(dòng)因子來替代線性收斂因子,如式(11)所示。在迭代前期,a(t)的值較大,有利于灰狼個(gè)體進(jìn)行全局搜查;在迭代后期,非線性的余弦因子a(t)的值減小緩慢,有利于灰狼個(gè)體在局部范圍內(nèi)尋找最優(yōu)個(gè)體,從而使GWO算法的全局搜查和局部探索能力得到平衡[14]。

a(t)=(amax-amin)cos[(t·π)/(2Tmax)]+μ

(11)

式中：amax=2;amin=0;μ=2rand-1。

2.3 改進(jìn)位置更新公式

在式(7)中,傳統(tǒng)灰狼位置更新僅依靠α,β,σ狼的平均值進(jìn)行,忽略了灰狼種群中的等級差異,在實(shí)際優(yōu)化過程中,與實(shí)際最優(yōu)解最接近的α狼具有更高的領(lǐng)導(dǎo)力,因此,在位置更新中提高α狼的權(quán)重,并減少σ狼的權(quán)重,以及增加上一代最優(yōu)解對本代α狼進(jìn)行牽引,從而提高算法的尋優(yōu)能力與個(gè)體間的聯(lián)系。如式(12)所示。

(12)

式中：r3為[0,1]之間的隨機(jī)數(shù);best為上一代種群最優(yōu)解。

2.4 引入維度學(xué)習(xí)狩獵搜索策略

在維度學(xué)習(xí)狩獵(dimension learning-based hunting,DLH)搜索策略中[15],為每只狼構(gòu)建鄰域,增強(qiáng)個(gè)體間交流,加速尋優(yōu)過程。

2.4.1 初始化階段

將N只灰狼在(li,uj)范圍內(nèi)進(jìn)行隨機(jī)分布,如式(13)所示

Xij=lj+randj(0,1)×(uj-lj)i∈(1,N),j∈(1,D)

(13)

式中：D為向量的維數(shù);N為灰狼個(gè)數(shù);lj和uj為上下邊界。

2.4.2 運(yùn)動(dòng)階段

在維度學(xué)習(xí)狩獵搜索的運(yùn)動(dòng)策略中,首先通過式(12)計(jì)算出灰狼位置作為第一候選位置Xigwo(t+1),其次計(jì)算當(dāng)前灰狼位置Xi(t)與Xigwo(t+1)之間的歐幾里得距離Ri(t),如式(14)所示：

Ri(t)=‖Xi(t)-Xigwo(t+1)‖

(14)

以Ri(t)為半徑,構(gòu)造鄰域Ni(t),如式(15)所示：

Ni(t)={Xj(t)|Di(Xi(t),Xj(t))≤Ri(t),Xj(t)∈pop}

(15)

式中Di為Xi(t)到Xj(t)的歐氏距離。

其次通過多鄰域?qū)W習(xí),計(jì)算候補(bǔ)位置Xidlh,d(t+1)：

Xidlh,d(t+1)=Xi,d(t)+rand×(Xn,d(t)-Xr,d(t))

(16)

式中Xidlh(t+1)為DLH策略的第二候選位置。

2.4.3 選擇和更新階段

通過比較Xigwo(t+1)和Xidlh,d(t+1)的適應(yīng)度值來選擇位置更優(yōu)的個(gè)體,計(jì)算公式如下：

(17)

在改進(jìn)GWO中,共有2只候選狼,通過選擇2種候選狼中的最優(yōu)狼來更新個(gè)體位置,從而避免算法陷入局部最優(yōu)解。其流程框圖如圖2所示。

圖2 PDGWO流程圖

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

3.1 測試函數(shù)和實(shí)驗(yàn)設(shè)置

為了驗(yàn)證PDGWO算法的優(yōu)異,本文利用GWO算法、PSO算法、CSGWO算法,以及文獻(xiàn)[5]提出的IGWO算法進(jìn)行了測試。其中,單峰基準(zhǔn)測試函數(shù)為F1：Sphere,F2：Schwefel′s2.22,F3：Schwefel′s1.2,F4：Schwefel′s2.21,F5：Rosenbrock,F6：Quartic。多峰基準(zhǔn)測試函數(shù)為F7：Rastrigin,F8：Ackley,F9：Griewank。為保證實(shí)驗(yàn)的公平性,避免實(shí)驗(yàn)發(fā)生的偶然性,因此對這5種算法進(jìn)行30次測試。實(shí)驗(yàn)參數(shù)設(shè)置為：種群規(guī)模pop=30,迭代次數(shù)Tmax=500,收斂因子α上限為2、下限為0,分別在30維度和100維度下測試算法的性能,選擇100維度來驗(yàn)證PDGWO算法處理各種復(fù)雜問題的能力,其結(jié)果有助于評估算法的穩(wěn)定性與精確性。記錄每次實(shí)驗(yàn)的結(jié)果,然后取平均值和標(biāo)準(zhǔn)差。測試結(jié)果如表1、表2所示。

表1 30維度下基準(zhǔn)函數(shù)測試結(jié)果

表2 100維度下基準(zhǔn)測試函數(shù)結(jié)果

3.2 實(shí)驗(yàn)結(jié)果與分析

3.2.1 求解精度

通過仿真觀察記錄實(shí)驗(yàn)數(shù)據(jù),當(dāng)維度為30時(shí),PDGWO算法在單峰函數(shù)F1、F2、F3和F4上的求解效果明顯優(yōu)于其他算法,并取得了很好的精確度,其中在函數(shù)F1上,PDGWO算法的標(biāo)準(zhǔn)差為0,其他算法的標(biāo)準(zhǔn)差分別為3.33×10-28,1.80×10-37,3.79×10-27,22.2,說明該算法具有很好的穩(wěn)定性。而在函數(shù)F5上,各類算法的求解差別很小,但PDGWO算法相較其他算法而言更為精確。在函數(shù)F6上,PDGWO算法的求解平均值達(dá)到了0.000 082,而其他算法大多在0.001 68左右,由此可見,PDGWO在面對Quartic函數(shù)尋優(yōu)結(jié)果有了進(jìn)一步提升。在多峰函數(shù)F7、F9上,PDGWO的收斂結(jié)果達(dá)到了理想最優(yōu)值0,說明算法可以高水平地實(shí)現(xiàn)對Rastrigin和Griewank函數(shù)的尋優(yōu)。同其他算法相比,大幅度提高了算法的準(zhǔn)確度。針對F8：Ackley函數(shù),PDGWO算法的平均值明顯高于其他測試算法,證明了PDGWO對該函數(shù)的求解精度得到了進(jìn)一步的提升,而標(biāo)準(zhǔn)差達(dá)到了0,證明了PDGWO具有很高的穩(wěn)定性。在100維度時(shí),其他算法的求解精度有明顯下降,而PDGWO算法在F1～F4函數(shù)的求解精度只有稍許下降,在函數(shù)F6：Quartic中,算法之間的尋優(yōu)結(jié)果相似,但PDGWO較其他算法有著一定地提高。在F7：Rastrigin,F8：Ackley,F9：Griewank函數(shù)中,算法的尋優(yōu)結(jié)果和30維時(shí)一樣,證明了算法在F7～F9函數(shù)問題時(shí),維度基本不對函數(shù)的尋優(yōu)造成影響。

通過表1、表2中記錄的平均值與測試值對比,PDGWO對于100維度與30維度的求解結(jié)果相差較小,這表明PDGWO算法具備適應(yīng)復(fù)雜問題尋優(yōu)的能力。

3.2.2 收斂過程

圖3展示了PSO、GWO、IGWO、CSGWO、PDGWO在100維度的情況下對單峰、多峰函數(shù)的尋優(yōu)曲線。在F1～F4中,PDGWO算法迭代更快,收斂性更好;在F5中,各個(gè)算法的收斂結(jié)果相差不大,但提出的PDGWO算法在第12次尋優(yōu)結(jié)果已經(jīng)到了98.9761,而CSGWO,IGWO,GWO在第120代尋優(yōu)結(jié)果在100左右,由此可見在解決F5：Rosenbrock函數(shù)問題時(shí),即使用少量的迭代次數(shù)也能求得一個(gè)較精確的解,較其他算法提高了尋優(yōu)的效率;在函數(shù)F6中,雖然收斂曲線不像F1～F4收斂函數(shù)那樣明顯,但較其他算法收斂圖有較大的提升。在多峰函數(shù)F7～F9中,PDGWO算法尋優(yōu)精度更高,穩(wěn)定性和魯棒性更好。

(a)F1

(b)F2

(c)F3

(d)F4

(e)F5

(f)F6

(g)F7

(h)F8

(i)F9

4 結(jié)束語

針對GWO算法存在尋優(yōu)精度低、求解速度慢等問題,提出融入PWLCM映射—準(zhǔn)反向?qū)W習(xí)策略和維度學(xué)習(xí)改進(jìn)的灰狼算法。在Matlab上的仿真結(jié)果表明,提出的PDGWO算法在單峰函數(shù)、多峰函數(shù)的收斂精度有明顯地提高,且該算法在處理高維問題時(shí)有更好的穩(wěn)定性和魯棒性。PDGWO算法同其他算法相比也有明顯的優(yōu)勢,下一步將繼續(xù)研究并將PDGWO算法用于解決實(shí)際問題中。