模擬退火自適應(yīng)反向無慣性粒子群優(yōu)化算法

曹文梁, 康嵐蘭, 王 石

(1.東莞職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)工程系,廣東 東莞 523808; 2.江西理工大學(xué) 應(yīng)用科學(xué)學(xué)院,江西 贛州 341000)

0 引 言

粒子群優(yōu)化(particle swarm optimization,PSO)算法是文獻(xiàn)[1]在研究魚群及鳥類等群體覓食行為的過程中提出的一種隨機(jī)仿生進(jìn)化算法。由于其概念簡單且易于實(shí)現(xiàn),自提出以來,受到科研人員廣泛關(guān)注,也是目前應(yīng)用最為廣泛的一種進(jìn)化優(yōu)化算法,PSO已在智能交通、制造、生物科學(xué)、國防等多個不同領(lǐng)域取得了良好的應(yīng)用效果[2-6]。

然而,PSO從設(shè)計(jì)之初就伴隨著收斂速度過慢、易陷入局部最優(yōu)、參數(shù)依賴過大等問題。為加快PSO收斂速度,科研人員將反向?qū)W習(xí)策略引入到PSO中,并對反向策略中關(guān)鍵參數(shù)展開詳細(xì)研究,給出取值建議。然而,理論與實(shí)驗(yàn)分析表明,反向策略的引入雖然加快了粒子群的收斂速度,但同時提高了粒子陷入局部最優(yōu)的概率。

為解決上述問題,本文提出了一種模擬退火自適應(yīng)反向無慣性粒子群優(yōu)化(simulated annealing adaptive opposition-based non-inertial particle swarm optimization,SAONPSO)算法,該算法一方面從參數(shù)調(diào)節(jié)角度出發(fā),對反向策略展開研究,受模擬退火思想(simulated annealing, SA)[7]啟發(fā),提出了一種自適應(yīng)退火策略調(diào)節(jié)反向策略使用概率;另一方面提出一種精英差分變異策略,避免粒子陷入局部最優(yōu);除此之外,為降低參數(shù)控制對算法的影響,引入一種無慣性速度更新公式取代標(biāo)準(zhǔn)PSO算法速度更新公式,最終達(dá)到高精度快速收斂的目的。在11個典型測試函數(shù)上采用多種基于反向?qū)W習(xí)PSO算法進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明, SAONPSO算法在大部分函數(shù)上取得最優(yōu)解的同時,收斂速度得到了顯著提高。

1 反向PSO算法

1.1 標(biāo)準(zhǔn)PSO

PSO算法[1]是一種群智能隨機(jī)進(jìn)化算法,群體中每個粒子表征問題的一個候選解,在解空間中,粒子根據(jù)如下動力方程搜索最優(yōu)解,即

vi,j(t+1)=ωvi,j(t)+c1rand1(pbesti,j-xi,j(t)) +c2rand2(gbestj-xi,j(t))

(1)

xi,j(t+1)=xi,j(t)+vi,j(t+1)

(2)

其中,vi,j(t)、xi,j(t)分別為t時刻第i個粒子在第j維上的速度與位置分量;pbest、gbest分別為粒子當(dāng)前最優(yōu)位置和粒子群全局最優(yōu)位置;i=1,2,…,N;j=1,2,…,D(D為空間維度,N為粒子群規(guī)模);ω∈[0,1]為慣性權(quán)值;c1,c2∈[0,2]分別為認(rèn)知學(xué)習(xí)因子和社會學(xué)習(xí)因子;rand1、rand2分別為[0, 1]區(qū)間上服從均勻分布的隨機(jī)數(shù)。

1.2 一般化的反向?qū)W習(xí)策略

文獻(xiàn)[8]首次提出反向?qū)W習(xí)(opposition-based learning,OBL)策略,目前已應(yīng)用于多種優(yōu)化算法中。其主要思想是:同時評估一個可行解及其反向解,將其中較優(yōu)解保留進(jìn)入下一代進(jìn)化。

(3)

其中,k∈U(0,1)的隨機(jī)數(shù);[da,db]為搜索空間的動態(tài)邊界,且每一維取值為:

daj=min(xi,j),dbj=max(xi,j)

(4)

(5)

使用反向策略的PSO算法稱為反向粒子群優(yōu)化算法。根據(jù)文獻(xiàn)[9]的分析,粒子在每一代的進(jìn)化中,GOBL策略使用概率取0.3時結(jié)果普遍較優(yōu)。

2 精英差分變異策略

由(1)式可見,粒子飛行方向受群體當(dāng)前最優(yōu)位gbest的引導(dǎo),為降低粒子陷入局部最優(yōu)的可能性,本文視gbest為種群精英粒子,受差分演化思想的啟發(fā),對其在每一代中進(jìn)行變異操作,從而提高算法全局探索能力。該變異策略稱為精英差分變異策略(elite differential evolutionary mutation,EDEM),具體公式為:

(6)

其中,r1、r2、r3、r4∈[1,N]為互不相等的隨機(jī)整數(shù);F為尺度系數(shù)。

SAONPSO算法如下:

隨機(jī)初始化含N個粒子的種群P,根據(jù)(3)～(5)式獲得N個粒子的反向粒子,構(gòu)成其反向種群OP,計(jì)算種群P∪OP中每個粒子的適應(yīng)值,選擇其中較優(yōu)的N個粒子作為初始種群P;

While未達(dá)到終止條件時do

根據(jù)(9)式生成GOBL策略概率jr;

If rand(0,1)

根據(jù)(3)～(5)式更新OP,在解空間P∪OP中選取N個適應(yīng)值占優(yōu)的粒子;

更新 pbest 和 gbest;

else

fori=1 toNdo

根據(jù)(2)式、(7)式,獲得第i個粒子的速度與位置向量,并更新粒子適應(yīng)值;

更新pbest和gbest;

end for

end if

forj=1 toNdo

對當(dāng)前gbest 根據(jù)EDEM變異公式(6)式進(jìn)行變異操作;

end for

iff(gbest*)優(yōu)于f(gbest) then

用gbest*位更新當(dāng)前gbest位;

end if

end While

3 無慣性速度更新公式

由標(biāo)準(zhǔn)PSO速度更新公式(1)式可見,粒子飛行方向受慣性動力、認(rèn)知學(xué)習(xí)和社會學(xué)習(xí)3個項(xiàng)引導(dǎo),文獻(xiàn)[9]指出,雖然慣性項(xiàng)使得粒子群保持了種群多樣性,但它同時也降低了粒子群的收斂速度。為進(jìn)一步增強(qiáng)種群局部開發(fā)能力,提高粒子群收斂速度,本文引入一種無慣性速度更新公式(non-inertial velocity update formula, NIV)(7)式取代(1)式引導(dǎo)粒子飛行方向,即

vi(t+1)=s(u(t)-u(t-1))+

c1rand1(pbesti-xi(t))+

c2rand2(gbest-xi(t))

(7)

其中,s∈(0,1)為差分系數(shù)(differential coefficient),用于控制種群搜索范圍,根據(jù)文獻(xiàn)[12]的分析,當(dāng)s取值在0.1～0.2之間,性能普遍達(dá)到最佳,因此本文后續(xù)實(shí)驗(yàn)中取s=0.1;u(t)、u(t-1)分別為種群在t時刻與t-1時刻所有粒子位置均值,即第j維上取值公式為:

(8)

4 SAONPSO算法

本文將EDEM策略與NIV速度更新公式應(yīng)用于反向?qū)W習(xí)PSO算法中,給出了SAONPSO算法，用偽碼描述了SAONPSO算法的基本步驟，其中變量jr為使用GOBL策略的概率。文獻(xiàn)[9]仿真實(shí)驗(yàn)分析表明,當(dāng)jr取0.3時性能較好。然而固定反向策略使用概率并不是一個好的選擇,本文采用SA算法根據(jù)粒子在不同階段的需求自適應(yīng)選擇反向策略使用概率,即

(9)

其中,u(t)、u(t-1)分別為粒子群在迭代第t代與t-1代所有粒子位置均值;f(u(t))、f(u(t-1))分別為其對應(yīng)均值位適應(yīng)值。易知,jr越小,粒子收斂速度越高,然而,當(dāng)種群內(nèi)粒子越聚集時,粒子陷入局部最優(yōu)的可能性越大,此時,反向策略使用概率jr取值增大?？墒沟昧Ｗ颖苊庀萑刖植孔顑?yōu)。

由SAONPSO算法步驟可知,SAONPSO算法主要包含初始種群、GOBL策略、速度與位置更新操作、EDEM變異操作4個部分。其中,速度與位置更新操作的時間復(fù)雜度易知為O(N);初始種群包括個體隨機(jī)生成、反向解生成及種群選擇機(jī)制3個部分,GOBL策略中包括反向解生成和種群選擇機(jī)制部分,其中隨機(jī)個體生成和反向解生成時間復(fù)雜度均為O(N·D),而種群選擇操作的復(fù)雜度為O(N2)。然而,GOBL策略中,若維度D較小,群體規(guī)模N可近似于D;反之,D較大時(D≥100),N通常小于D;因此,GOBL策略計(jì)算復(fù)雜度可計(jì)為O(N·D)。綜上所述,SAONPSO算法的計(jì)算復(fù)雜度也可計(jì)為O(N·D)。

5 數(shù)值仿真實(shí)驗(yàn)及分析

(1) 算法性能測試。SAONPSO算法與5種基于反向?qū)W習(xí)的PSO(OBL-based PSO)進(jìn)行比較,它們分別是OPSO-AEM&NIW[13]、OPSO[14]、GOPSO[5]、OVCPSO[15]和EOPSO[16]。實(shí)驗(yàn)中,為確保對比的公平性,所有算法種群規(guī)模N均取40,其他參數(shù)保持與原文獻(xiàn)一致。

(2) 策略分析。分析EDEM和NIV 2種策略,以及自適應(yīng)反向策略使用概率jr的使用對算法的影響。

(3) 參數(shù)敏感性分析。分析種群規(guī)模取不同值時,對算法性能的影響。

SAONPSO算法默認(rèn)參數(shù)設(shè)置見表1所列。特別地,除SAONPSO算法外其他反向PSO算法jr取值均為0.3。

表1 SAONPSO算法參數(shù)設(shè)置

5.1 實(shí)驗(yàn)設(shè)置

數(shù)值實(shí)驗(yàn)中使用的11個測試函數(shù)見表2所列。按其屬性分為單峰f1～f4和多峰f5～f11兩大類,其中多峰函數(shù)包括簡單多峰函數(shù)f5～f7，帶旋轉(zhuǎn)的多峰函數(shù)f8、f9和移位多峰函數(shù)f10、f113種。為使所有測試函數(shù)在零點(diǎn)位均取得全局最優(yōu)值0,本文參考CEC 2010中的函數(shù)定義,將移位多峰函數(shù)中的參數(shù)f-bias統(tǒng)一設(shè)定為0。表2中,M為D×D隨機(jī)正交矩陣;o為D維隨機(jī)位移向量。

表2 數(shù)值實(shí)驗(yàn)中使用的11個測試函數(shù)

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

5.2.1 算法對比分析

對比實(shí)驗(yàn)中,6種反向PSO算法最大迭代次數(shù)均為10 000,每個測試函數(shù)均運(yùn)行30次,全局最優(yōu)值的均值見表3所列。實(shí)驗(yàn)采用雙尾t檢驗(yàn)對結(jié)果進(jìn)行顯著性差異統(tǒng)計(jì)分析,顯著水平為0.05。表3中,“-”、“+”、“=” 3種符號分別表示SAONPSO算法的性能劣于、優(yōu)于、相當(dāng)于其他5種對比算法。

從表3可以看出,SAONPSO在6種算法中是較優(yōu)的。其中相比OPSO和OVCPSO,在所有測試函數(shù)上均取得顯著優(yōu)勢;雖然在與EOPSO算法的對比中,在f3測試函數(shù)中結(jié)果較劣,但在其他9個測試函數(shù)上均取得最優(yōu)。另外,SAONPSO除f11外,均優(yōu)于或相當(dāng)于GOPSO結(jié)果。特別地,OPSO-AEM&NIW和SAONPSO在大多數(shù)函數(shù)中取得了相當(dāng)?shù)淖顑?yōu)解,但在3個測試函數(shù)f3、f5、f11上,SAONPSO優(yōu)于OPSO-AEM&NIW。

為進(jìn)一步比較OPSO-AEM&NIW和SAONPSO性能上的差異,2種算法在求解精度為10-16、最大迭代次數(shù)為10 000次、統(tǒng)計(jì)適應(yīng)值函數(shù)評估次數(shù)(FES)相同條件下,在11個測試函數(shù)上取值函數(shù)評估次數(shù)比較結(jié)果見表4所列。表4中，F(xiàn)val為函數(shù)值。由表4可知,SAONPSO在所有測試函數(shù)中,FEs均顯著小于OPSO-AEM&NIW,由此可見,SAONPSO顯著提升了反向PSO的收斂速度。

表3 OPSO、GOPSO、OVCPSO、EOPSO OPSO-AEM&NIW和SAONPSO算法在11個測試函數(shù)上的結(jié)果均值

表4 OPSO-AEM&NIW和 SAONPSO算法在11個測試函數(shù)上取值函數(shù)評估次數(shù)比較

5.2.2 策略有效性分析

SAONPSO算法將EDEM和NIV 2種策略融入到GOBL之中,對OBL-based PSO算法進(jìn)行了改進(jìn)。為分析2種策略對算法性能所產(chǎn)生的影響,本文以測試函數(shù)f2、f6為例,分別將EDEM、NIV與GOBL進(jìn)行組合,即GOBL+EDEM、GOBL+NIV與改進(jìn)算法SAONPSO(GOBL+EDEM+NIV)作對比實(shí)驗(yàn),GOBL+EDEM實(shí)驗(yàn)中,慣性系數(shù)ω取固定值0.729 84[14]。EDEM、NIV 2種策略對算法的影響如圖1所示。實(shí)驗(yàn)結(jié)果表明:NIV策略充分獲取環(huán)境信息,利用前2個時刻種群信息差值,指導(dǎo)粒子下一時刻的飛行方向,有效加快了粒子群的收斂速度;EDEM策略則通過對精英粒子(gbest)的擾動,降低粒子陷入局部最優(yōu)的概率,確保粒子群平滑且快速地收斂到全局最優(yōu)值。

圖1 EDEM、NIV 2種策略對算法的影響

5.2.3 參數(shù)敏感性分析

為檢驗(yàn)SAONPSO算法對粒子種群數(shù)目N取值敏感性,本節(jié)以測試函數(shù)f2、f6為例,在種群規(guī)模N分別取20、40、60、80、100的5種情況下對算法展開進(jìn)一步的仿真實(shí)驗(yàn),N取不同值時SAONPSO算法全局收斂過程如圖2所示。由圖2可知,當(dāng)N取值較小(<40)時,算法可能在未取得最優(yōu)值時停沚或需較大開銷才能收斂到最優(yōu)值;當(dāng)N取值較大(>60)時,雖然算法能取得最優(yōu)值,但可能需要花費(fèi)更大的開銷;而種群規(guī)模在40～60之間,算法普遍能以較快的收斂速度取得最優(yōu)值。

圖2 N取不同值時SAONPSO算法全局收斂過程

6 結(jié) 論

本文提出了SAONPSO算法。該算法將EDEM策略和NIV融入到GOBL中,使得反向粒子群優(yōu)化算法在加強(qiáng)空間探索能力的同時,有效避免陷入局部最優(yōu),使算法收斂速度得到顯著提高。除此之外,本文在GOBL基礎(chǔ)上,根據(jù)粒子進(jìn)化不同階段的收斂特性,提出了一種自適應(yīng)選擇反向策略使用概率的方式取代了取固定值的方法,進(jìn)一步避免粒子出現(xiàn)早熟現(xiàn)象。多種測試函數(shù)仿真實(shí)驗(yàn)結(jié)果表明,新算法在獲得高精度解的同時,顯著提高了算法的收斂速度。

下一步將對算法性能展開理論分析,并將其應(yīng)用于高維問題中驗(yàn)證算法有效性。將算法與實(shí)際問題相結(jié)合進(jìn)行研究是未來工作的重要方向。