基于社會(huì)等級淘汰機(jī)制的GWO_PSO算法

張子豪,靳其兵

(北京化工大學(xué) 信息科學(xué)與技術(shù)學(xué)院,北京 100029)

群智能優(yōu)化算法是一種由自然界中,群體動(dòng)物的活動(dòng)啟發(fā)而產(chǎn)生的全局優(yōu)化算法。典型的智能優(yōu)化算法包括粒子群優(yōu)化(Particle swarm optimization,PSO)[1]算法,差分進(jìn)化(Differential evolution,DE)[2]算法,鯨魚優(yōu)化算法(Whale optimization algorithm,WOA)[3],人工蜂群(Artificial bee colony,ABC)[4]算法,布谷鳥(Cuckoo search,CS)[5]算法等。智能優(yōu)化算法在機(jī)器學(xué)習(xí)算法[6-8]、系統(tǒng)辨識[9,10]以及PID控制方面[11]也有很多的應(yīng)用。

Mirjalili等[12]由灰狼獵食以及灰狼種群中的等級制度得到啟發(fā),于2014年提出灰狼優(yōu)化(Grey wolf optimizer,GWO)算法,其結(jié)構(gòu)簡單,參數(shù)少,易于編程,尋優(yōu)性能較好,但其自身仍然存在收斂精度不足的問題。近年來,對此有很多學(xué)者提出了對灰狼算法的改進(jìn)方法,文獻(xiàn)[13]通過加入混沌策略和對收斂因子加入自適應(yīng)策略,使算法精度和穩(wěn)定性都有了一定的提高;文獻(xiàn)[14]通過改進(jìn)收斂因子的方法,使其不易陷入局部最優(yōu);文獻(xiàn)[15]引入PSO的最優(yōu)解記憶思想,采用佳點(diǎn)集策略和改進(jìn)收斂因子的策略,提升了算法的性能;文獻(xiàn)[16]引入差分進(jìn)化算法的和灰狼算法混合的策略和優(yōu)勝劣汰法則,改進(jìn)了灰狼算法的尋優(yōu)能力。

1 GWO算法原理

灰狼算法是受到灰狼狩獵覓食這一自然現(xiàn)象啟發(fā),而提出的群智能優(yōu)化算法,灰狼優(yōu)化算法在設(shè)計(jì)中考慮了狼群中的社會(huì)等級,模仿狼群尋找、包圍、攻擊獵物的狩獵模式。

(1)社會(huì)等級(Social hierarchy)。

該算法設(shè)計(jì)了3種統(tǒng)治階級的狼和普通的狼,統(tǒng)治階級的狼分為α狼、β狼、δ狼,組成狼群的普通狼為ω狼,其分別對應(yīng)的是最優(yōu)解、次優(yōu)解、第三優(yōu)解和候選解[17]。

(2)圍獵(Encircling prey)。

灰狼在搜索獵物的過程中,會(huì)逐漸地接近獵物并包圍它,該行為的數(shù)學(xué)模型如下

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

(1)

式中:t指當(dāng)前時(shí)刻,A和C是協(xié)同系數(shù),Xp是頭狼的位置,X是指灰狼ω狼群的位置。

協(xié)同系數(shù)A、C分別為

A=2a·r1-a,C=2·r2,a=2-2*(t/tmax)

(2)

式中:a由2線性衰減到0,r1和r2是[0,1]之間的隨機(jī)數(shù)。

(3)狩獵(Hunting)。

在每次迭代過程中,保留當(dāng)前種群中的最優(yōu)的3只灰狼,即適應(yīng)度值最優(yōu)的3個(gè)解,α狼、β狼、δ狼,頭狼根據(jù)他們自身所在位置,判斷狼群與自己的距離,并通過商議,得出狼群所需移動(dòng)的距離。該行為的數(shù)學(xué)模型可表示為

Dα=|C1·Xα-X|,Dβ=|C2·Xβ-X|,

Dδ=|C3·Xδ-X|

(3)

X1=Xα-A1·(Dα),X2=Xβ-A2·(Dβ),

X3=Xδ-A3·(Dδ)

(4)

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

(5)

式中:Dα、Dβ、Dδ分別表示3種頭狼與獵物之間的距離,X1、X2、X3分別表示α狼、β狼、δ狼的位置,式(5)表示ω狼根據(jù)α狼、β狼、δ狼的位置更新整個(gè)狼群的位置。

2 PSO算法原理

PSO算法是Kennedy和Eberhart提出的一種群智能優(yōu)化算法。粒子群優(yōu)化算法的基本思想是利用種群中不同粒子之間的信息共享,使群體由隨機(jī)分布到有序分布,其速度向量的思想,對于群智能優(yōu)化算法來講是有開創(chuàng)意義的。

粒子群優(yōu)化算法將每一個(gè)粒子隨機(jī)分布在解域空間內(nèi),設(shè)粒子的位置為X,根據(jù)適應(yīng)度值設(shè)置局部最優(yōu)Xpbest和全局最優(yōu)Xgbest,Xpbest表示當(dāng)前代適應(yīng)度值最優(yōu)的粒子,Xgbest表示歷史代到目前最優(yōu)的粒子。根據(jù)局部最優(yōu)和全局最優(yōu)可以得到一個(gè)速度矢量V,其公式為

V(t+1)=ωV(t)+c1r1(Xpbest(t)-X(t))+

c2r2(Xgbest(t)-X(t))

(6)

式中:c1=2,c2=2,ω表示慣性因子,通常由大到小線性收斂,值大時(shí)主要進(jìn)行全局搜索,值小時(shí)進(jìn)行局部搜索。其更新公式為

ω(t)=ωmax-(ωmax-ωmin)*t/tmax

(7)

式中:tmax表示迭代的最大代數(shù),通常ωmax=0.9,ωmin=0.4。

根據(jù)得到的速度向量V更新粒子群中的每一個(gè)粒子,其表達(dá)式為

X(t+1)=X(t)+V(t+1)

(8)

3 灰狼_粒子群智能優(yōu)化算法

針對灰狼算法中仍然存在尋優(yōu)精度低,收斂速度慢的問題,本文提出了一種灰狼_粒子群智能優(yōu)化(Grey wolf optimizer_particle swarm optimization,GWO_PSO)算法。

3.1 GWO_PSO算法改進(jìn)思路

(1)混沌映射。

混沌映射具有隨機(jī)性、周期性的特點(diǎn)。在許多智能優(yōu)化算法中,混沌映射都起到了很好的效果,如文獻(xiàn)[18]采用了Iterative映射的方法初始化狼群。

Logistic映射通過迭代的方式產(chǎn)生,是一種具有確定性、類似隨機(jī)性、非周期的、收斂性的偽隨機(jī)序列,其分布均勻。為使灰狼狼群更隨機(jī)地分布,引入Logistic映射對灰狼狼群進(jìn)行初始化。Logistic映射的公式為

uk+1=auk(1-uk)

(9)

從圖1中可以看出,當(dāng)a=4時(shí),Logistic在[0,1]分布最廣,其中uk?{0,0.25,0.5,0.75,1}。如圖2所示,Logistic映射的分布更加隨機(jī),因此選用Logistic映射用于初始化灰狼種群。

圖1 參數(shù)a對應(yīng)的Logistic映射

圖2 兩種混沌映射的分布

(2)等級制度。

灰狼算法中提出的等級制度沒有體現(xiàn)出3只頭狼的優(yōu)先級的差別,容易偏離目標(biāo)值,導(dǎo)致精度不足。為了凸顯灰狼算法的等級制度,提出灰狼算法的等級制度思想,其基本思想就是在更新灰狼位置時(shí),加上一個(gè)等級權(quán)重,分別為η1、η2、η3,三者的關(guān)系為

η1∶η2∶η3=4∶3∶2

(10)

通常取η1=2、η2=1.5、η3=1。

(3)速度向量。

灰狼算法中的位置更新只體現(xiàn)了灰狼和獵物之間的距離,并沒有體現(xiàn)出灰狼尋優(yōu)的方向,其對于解的判定只有位置信息而沒有方向矢量信息,其優(yōu)化能力還有一定地提升空間。受粒子群優(yōu)化算法中速度向量V的啟發(fā),根據(jù)式(3)、(4)、(5)計(jì)算得到頭狼及狼群的位置,引入速度向量V,其更新公式為

(11)

式中:ω為慣性因子,ηi為等級權(quán)重,k為協(xié)同系數(shù)。

通常ωmax=0.6,ωmin=0,ω的選擇對于尋優(yōu)效果有著重要影響,其更新公式為式(7)。

協(xié)同系數(shù)k的公式為

k=0.1*rand

(12)

灰狼狼群的位置更新公式為式(8)。

通過引入速度向量,增加了尋優(yōu)方向矢量信息,提高了收斂速度和收斂精度。

(4)淘汰機(jī)制。

一個(gè)灰狼種群中,存在一些老弱病殘的灰狼,隨著自然選擇,會(huì)被新生的狼群代替,同時(shí)統(tǒng)治階級的狼有更多的繁衍機(jī)會(huì)。在每一代ω狼中,選取適應(yīng)度值在排在后三分之一的灰狼予以淘汰,同時(shí)由新一代的灰狼替代被淘汰的老弱病殘,其更新公式為

(13)

式中:η1、η2、η3為等級權(quán)重。

淘汰機(jī)制的主要流程為:

(1)根據(jù)適應(yīng)度值排序ω狼,并對適應(yīng)度值排后三分之一的灰狼Xold予以淘汰。

(2)根據(jù)式(13)得到Xnew,替換Xold,與之前的灰狼形成新的種群。

淘汰機(jī)制強(qiáng)化了等級制度在灰狼算法中的作用,使算法的精度和收斂速度有所提高。

3.2 GWO_PSO算法流程

通過以上改進(jìn),提高了灰狼算法的精度和收斂速度,經(jīng)過總結(jié),可以將其歸納成如下步驟:

步驟1初始化。采用Logistic混沌映射,初始化灰狼種群X,并初始化參數(shù);

步驟2計(jì)算適應(yīng)度值。計(jì)算灰狼狼群X的適應(yīng)度值,根據(jù)適應(yīng)度值設(shè)α狼、β狼、δ狼,其包含的獵物信息分別是Xα、Xβ、Xδ,通過式(3)和式(4)得到X1、X2、X3;

步驟3根據(jù)式(5)獲取ω狼群的獵物信息;

步驟4根據(jù)式(11)計(jì)算速度向量V,并將其代入式(8)更新種群位置;

步驟5淘汰機(jī)制。根據(jù)步驟2所計(jì)算的適應(yīng)度值,進(jìn)行排序,淘汰后三分之一的灰狼Xold,并根據(jù)式(13)得到Xnew;

步驟6計(jì)算灰狼適應(yīng)度值,和上一代迭代的值比較,根據(jù)適應(yīng)度值選擇新的α狼、β狼、δ狼,得到X1、X2、X3;

步驟7判斷Xα的適應(yīng)度值是否達(dá)到結(jié)束條件,若滿足條件,則最優(yōu)值為Xα;若不滿足條件,則重復(fù)步驟4-7。GWO_PSO優(yōu)化算法流程如圖3所示。

圖3 GWO_PSO算法流程圖

4 函數(shù)優(yōu)化實(shí)驗(yàn)及結(jié)果分析

為測試GWO_PSO算法的有效性,本文采用12個(gè)經(jīng)典的測試函數(shù),其表達(dá)式如表1所示。

表1 12個(gè)測試函數(shù)表

續(xù)表1

為了體現(xiàn)本文所提算法對灰狼優(yōu)化算法的改進(jìn)效果,本節(jié)將對GWO_PSO算法與其他改進(jìn)灰狼算法進(jìn)行比較,分別選取F1～F12函數(shù)比較,測試函數(shù)F9為2維,其余函數(shù)為30維。將GWO_PSO與LGWO[19]、HGWO[20]、PGWO[21]、CGWO[22]比較,運(yùn)算500次得到的平均值及標(biāo)準(zhǔn)差,其結(jié)果如表2所示。部分函數(shù)適應(yīng)度收斂曲線如圖4-6所示。

表2 GWO_PSO與4種灰狼算法的尋優(yōu)效果比較

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

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

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

5 結(jié)論

本文提出了一種基于淘汰機(jī)制的GWO_PSO算法,引入了Logistic混沌映射策略初始化種群,使初始種群分布更加均勻;提出等級制度,突出了GWO算法中狼群的等級機(jī)制;引入速度向量思想,提高收斂精度及速度;提出了狼群中的淘汰機(jī)制,剔除了狼群中的“害群之馬”。同時(shí)根據(jù)狼群社會(huì)中的等級制度,讓狼群中等級更高的狼擁有繁衍權(quán),提高了算法的精確度,提高了算法的收斂速度。在系統(tǒng)辨識問題中,該算法取得了很好的應(yīng)用效果。