一種基于聚集檢測的改進(jìn)粒子群優(yōu)化算法①

任丹丹, 陳笑笑, 劉 清

(安徽理工大學(xué)數(shù)學(xué)與大數(shù)據(jù)學(xué)院,安徽 淮南 232001)

0 引 言

粒子群優(yōu)化算法(Particle Swarm Optimization,PSO)[1]是一種啟發(fā)式搜索算法,在理論上具有一定的全局搜索能力。由于參數(shù)設(shè)置簡單、適用范圍廣等優(yōu)點(diǎn),PSO算法現(xiàn)已受到眾多領(lǐng)域的廣泛關(guān)注,比如路徑規(guī)劃[2-4],癌癥基因檢測[5,6]以及電力系統(tǒng)設(shè)計(jì)[7]等。

PSO算法在處理復(fù)雜的多峰函數(shù)時(shí),往往不能收斂到全局最優(yōu)解:易陷入局部最優(yōu)區(qū)域[8,13,14]。為了提升PSO算法對(duì)復(fù)雜函數(shù)的求解能力,徐等[9]在2020年提出基于正態(tài)分布權(quán)值的改進(jìn)粒子群方法(NDWPSO)。NDWPSO通過正態(tài)分布函數(shù)模擬權(quán)值函數(shù),提升了算法的精度。2021年,吳等[10]提出一種動(dòng)態(tài)調(diào)整慣性權(quán)重和學(xué)習(xí)因子的粒子群優(yōu)化算法。該算法在種群進(jìn)化的過程中,自適應(yīng)調(diào)整慣性權(quán)重以及學(xué)習(xí)因子。由于該算法的參數(shù)較多,其收斂效果較好,但是參數(shù)調(diào)節(jié)卻較為繁瑣;2021年,李等[11]提出一種動(dòng)態(tài)自適應(yīng)參數(shù)的粒子群優(yōu)化算法,在速度進(jìn)化公式中引入非線性速度衰減因子,提升了粒子群的穩(wěn)定性;2022年,郭等[12]提出一種多種群并行協(xié)作的粒子群算法,該算法將三個(gè)使用不同進(jìn)化策略的子類群體融合為一個(gè)混合的粒子種群,提升了算法的收斂精度。這一類基于參數(shù)優(yōu)化的改進(jìn)方法,重點(diǎn)關(guān)注慣性權(quán)重、學(xué)習(xí)因子等參數(shù)對(duì)尋優(yōu)結(jié)果的影響,改善了算法的收斂性能。

然而,這些方法卻極易多次聚集于同一個(gè)局部鄰域。當(dāng)粒子群在某個(gè)局部最優(yōu)區(qū)域聚集后,增大慣性系數(shù)或者其他參數(shù),能夠強(qiáng)制粒子群分散到其他區(qū)域。在找到適應(yīng)值更優(yōu)的解之前,粒子全局最優(yōu)位置以及歷史最優(yōu)位置都分布在之前聚集的局部最優(yōu)區(qū)域內(nèi),在現(xiàn)有策略的指引下,可能會(huì)迅速聚集在相同的局部區(qū)域內(nèi)。

為了克服上述問題,提出一種基于聚集檢測的改進(jìn)粒子群優(yōu)化算法(Aggregation detection based PSO),簡記為ADPSO。ADPSO在粒子發(fā)生聚集時(shí),主要通過重新初始化粒子歷史最優(yōu)位置,降低全局學(xué)習(xí)因子,增大歷史最優(yōu)位置學(xué)習(xí)因子以及為每個(gè)粒子增加隨機(jī)搜索能力來提升改進(jìn)粒子群的搜索能力。在標(biāo)準(zhǔn)函數(shù)上的測試結(jié)果表明,改進(jìn)方法比傳統(tǒng)方法具有更好的收斂精度和收斂速度。

1相關(guān)工作

設(shè)F(X)是待求解的目標(biāo)函數(shù)(默認(rèn)最優(yōu)解為最小解),Ω是可行域。正整數(shù)n是粒子群的規(guī)模,Xi(i=1,2,…,n) 是第i個(gè)粒子Pi的位置,正整數(shù)D是粒子搜索空間Ω的維度,F(Xi)是粒子Pi的適應(yīng)度。在粒子群優(yōu)化算法中,適應(yīng)度最優(yōu)的粒子是種群最優(yōu)粒子,其位置記為Gbest。粒子Pi經(jīng)歷的歷史最優(yōu)位置記為Pi_best。

線性權(quán)重粒子群算法(WPSO)

WPSO是一種基于速度線性衰減的改進(jìn)算法,與PSO[1]相比,具有更好的收斂性能。假設(shè)在第k次迭代中,粒子Pi的速度為Vi。WPSO的速度公式:

Vi=WkVi+c1r1(Pi_best-Xi)+c2r2(Gbest-Xi)

(1)

(2)

其中,Vi是D維向量:Vi=(vi,1,vi,2,…,vi,D),iter_max是最大迭代次數(shù),Wk是速度慣性系數(shù),且0

WPSO根據(jù)如下公式更新粒子Pi的位置:

Xi=Xi+Vi

(3)

其中,Xi是一個(gè)D維的向量:Xi=(xi,1,xi,2,…,xi,D) 。

公式(1)和(2)說明,線性遞減的權(quán)值W使得WPSO算法在前期具有較大的速度,全局搜索能力較強(qiáng);在迭代后期,粒子群具有較強(qiáng)的局部搜索能力。WPSO通過權(quán)值W的調(diào)節(jié),來平衡粒子群的全局搜索能力和局部搜索能力。

實(shí)際上,WPSO還存在一個(gè)較為嚴(yán)重的不足:若粒子群聚集于某局部鄰域內(nèi),則很難跳出該區(qū)域。傳統(tǒng)的改進(jìn)方法[3-6]很難阻止粒子再次聚集于該區(qū)域。

2 基于聚集檢測的改進(jìn)粒子群算法(ADPSO)

2.1 WPSO算法的關(guān)鍵問題

當(dāng)WPSO算法發(fā)生聚集時(shí),粒子的歷史最優(yōu)位置都在全局最優(yōu)點(diǎn)Gbest的局部鄰域內(nèi):

Gbest≈Pi_best

(4)

其中,i=1,2,…,n。那么,公式(1)將退化為:

Vi=WkVi+(c1r1+c2r2)(Gbest-Xi)

(5)

公式(4)說明,在粒子群發(fā)現(xiàn)適應(yīng)值更優(yōu)的解之前,粒子的歷史最優(yōu)位置仍然在之前聚集位置附近。當(dāng)前的Gbest與全局最優(yōu)解的位置可能相距甚遠(yuǎn),使用公式(5)更新粒子速度,不一定能找到適應(yīng)值更優(yōu)的解。

針對(duì)這一關(guān)鍵問題,提出一種基于聚集檢測的粒子群優(yōu)化算法,以進(jìn)一步提升粒子群的搜索能力。

2.2 改進(jìn)方法:基于聚集檢測的改進(jìn)粒子群算法(ADPSO)

首先,在粒子群發(fā)生聚集后,更新每個(gè)粒子的歷史最優(yōu)位置。 假設(shè)粒子Pi的位置為Xi,且向量Xi的任意分量xi,j(j=1,2,…,D)的取值范圍為:xi,j∈[a,b],全局最優(yōu)位置Gbest的第j個(gè)分量記為Gbestj。由于Gbest是目標(biāo)函數(shù)的一個(gè)局部最優(yōu)解,在其δ(δ>0) 鄰域內(nèi)肯定不存在適應(yīng)值更優(yōu)的解。因此,在重新初始化歷史最優(yōu)位置時(shí),通過如下概率函數(shù)來約束粒子最優(yōu)位置:

P(xi,j)=

(6)

從公式(6)可知,所有粒子的歷史最優(yōu)位置以更大的概率落入Gbest的δ鄰域之外。

其次,降低全局最優(yōu)位置的影響力,防止粒子再次聚集在其局部鄰域之中:減小全局最優(yōu)位置的學(xué)習(xí)因子c2,并適當(dāng)增大粒子歷史最優(yōu)位置的學(xué)習(xí)因子c1。

假設(shè),粒子群在第ith次迭代時(shí)發(fā)生聚集。為了降低全局最優(yōu)位置Gbest的影響力,可減小學(xué)習(xí)因子c2,并增大學(xué)習(xí)因子c1:

(7)

(8)

最后,增加隨機(jī)搜索能力,提升收斂速度。按公式(3)更新Xi之后,隨機(jī)選擇向量Xi的一個(gè)分量xi,j,進(jìn)行如下操作:

Xitest1=(xi,1,xi,2,…,xi,j+β,…,xi,D)

(9)

Xitest2=(xi,1,xi,2,…,xi,j-β,…,xi,D)

(10)

(11)

(12)

1)設(shè)置基本參數(shù):迭代次數(shù)iter_max>0,N>0,D>0;設(shè)粒子位置X和飛行速度V為隨機(jī)值。學(xué)習(xí)因子恢復(fù)速率參數(shù)α>0,局部鄰域半徑δ>0。

2)計(jì)算粒子Pi的適應(yīng)度F(Xi),計(jì)算歷史最優(yōu)位置Pi_best,更新全局最優(yōu)位置Gbest。

3)公式(1-3):更新粒子速度和位置;公式(9-12):在Xi的某一維度上進(jìn)行線性的折半查找搜索。若粒子群發(fā)生聚集,則轉(zhuǎn)4);否則轉(zhuǎn)5)。

4)公式(6):以一定的概率初始化每個(gè)粒子的歷史最優(yōu)位置;公式(7-8):c1,c2的取值。

5)若迭代次數(shù)達(dá)到iter_max或當(dāng)前最優(yōu)解符合精度要求,則算法終止;否則,轉(zhuǎn)2)。

3 實(shí)驗(yàn)結(jié)果

3.1 參數(shù)設(shè)置

實(shí)驗(yàn)使用六種常用的標(biāo)準(zhǔn)函數(shù)來測試改進(jìn)算法的收斂速度和收斂精度,并將結(jié)果與WPSO[8]、權(quán)值正態(tài)分布的粒子群算法(NDWPSO)[9]以及吸引排斥粒子群算法(ARPSO)[15]的結(jié)果相比,以驗(yàn)證ADPSO算法的有效性。ADPSO的參數(shù)設(shè)置如下:c1=c2=2.0;wmax=0.9,wmin=0.4;δ=1,α=0.005,β=0.02;若ADPSO發(fā)生聚集,則動(dòng)態(tài)調(diào)整相關(guān)參數(shù)。WPSO的c1,c2,wmax以及wmin與ADPSO算法中對(duì)應(yīng)參數(shù)的設(shè)置一致。其他算法的參數(shù)均已調(diào)制最優(yōu)。所有算法的最大迭代次數(shù)iter_max=20000,N=20。測試函數(shù)如表1所示:

表1 六個(gè)測試函數(shù)的名稱與表達(dá)式

3.2 收斂精度對(duì)比

六個(gè)測試函數(shù)均具有全局最小解,記為Xoptimal。本文選擇絕對(duì)誤差作為算法收斂精度的評(píng)價(jià)標(biāo)準(zhǔn):

error=(|f(Gbest)-f(Xoptimal)|)

(13)

表2給出了四種算法在六種測試函數(shù)上的收斂精度:十次實(shí)驗(yàn)結(jié)果的均值。

表2 ADPSO算法與其他三種對(duì)比算法的收斂精度對(duì)比表。

從表2可知,ADPSO算法在F1,F2,F4,F5以及F6,這五個(gè)函數(shù)上的收斂精度明顯優(yōu)于其他三種對(duì)比算法;在F3上的收斂精度與WPSO和ARPSO算法的收斂精度基本相當(dāng)。

對(duì)于F1,四種算法都能收斂到全局最小解的局部區(qū)域,ADPSO算法具有更高的收斂精度。各算法在F2上的收斂精度都有明顯的下降:F2函數(shù)的波谷區(qū)域非常平坦,導(dǎo)致粒子只能緩慢地接近全局最優(yōu)解。利用了部分梯度信息的ADPSO算法,具有更優(yōu)的收斂精度。F3和F4是高維多峰函數(shù),在全局最優(yōu)解的周圍分布著大量的局部極優(yōu)區(qū)域,尋優(yōu)難度很大。ADPSO具有較好的收斂性能:收斂精度明顯高于其他三種粒子群優(yōu)化方法。F5和F6是二維多峰函數(shù),尋優(yōu)難度同樣很大;ADPSO算法的收斂精度都在10-4以內(nèi),正常情況下,能夠滿足實(shí)際應(yīng)用的精度要求。

3.3 收斂速度對(duì)比

圖1給出四種算法在測試函數(shù)上的“最優(yōu)值-迭代次數(shù)”收斂曲線。

(A) 四種算法在F1(X)上的收斂曲線

(B) 四種算法在F2(X)上的收斂曲線

(C) 四種算法在F3(X)上的收斂曲線

(D) 四種算法在F4(X)上的收斂曲線

(F) 四種算法在F6(X)上的收斂曲線

從圖1可知,在F1和F4上,ADPSO算法在前2500迭代就可以收斂到誤差精度小于102。F2的波谷區(qū)域非常平坦,導(dǎo)致傳統(tǒng)的ARPSO,WPSO以及NDWPSO,很難搜索到全局最優(yōu)解。ADPSO算法需要15000次左右的迭代才能找到全局最優(yōu)解。F3是一個(gè)高維且多峰的函數(shù),尋優(yōu)難度很大。ADPSO大約需要20000次迭代能夠收斂到誤差精度小于10的區(qū)域。其他對(duì)比算法的誤差精度則在102,與改進(jìn)算法的收斂精度有較大差距。在F5和F6函數(shù)上, ADPSO在前2000次迭代就能收斂到全局最優(yōu)解附近,具有明顯的優(yōu)勢。

4 結(jié) 論

本文提出了一種基于聚集檢測的改進(jìn)粒子群優(yōu)化算法,簡稱為ADPSO算法。針對(duì)當(dāng)前粒子群算法存在的易早熟、收斂精度不高的問題,ADPSO算法在粒子群發(fā)生聚集時(shí),重新初始化每個(gè)粒子的歷史最優(yōu)位置、動(dòng)態(tài)調(diào)整學(xué)習(xí)因子并且利用某一維度上的梯度信息,引導(dǎo)粒子搜索潛在的最優(yōu)解。改進(jìn)的ADPSO算法能夠保持較好的全局搜索能力,并同時(shí)具有較好的局部搜索精度。在六個(gè)測試函數(shù)上的實(shí)驗(yàn)結(jié)果表明,ADPSO與WPSO,ARPSO以及NDWPSO等算法相比,具有更好的更高的收斂精度和更快的收斂速度,具有更強(qiáng)的實(shí)際應(yīng)用能力。