基于正態(tài)分布衰減慣性權(quán)重的粒子群優(yōu)化算法

徐浩天，季偉東，孫小晴，羅 強(qiáng)

哈爾濱師范大學(xué)計(jì)算機(jī)科學(xué)與信息工程學(xué)院，黑龍江哈爾濱 150025

本研究使用改進(jìn)參數(shù)設(shè)置方式，提出正態(tài)分布衰減慣性權(quán)重粒子群優(yōu)化(normal distribution decay inertial weight particle swarm optimization, NDPSO)算法，針對慣性權(quán)重進(jìn)行改進(jìn)．NDPSO算法以正態(tài)分布曲線進(jìn)行權(quán)重衰減，該正態(tài)分布曲線是一種非線性衰減曲線，早期衰減緩慢，中期衰減迅速，后期衰減趨于平緩，且權(quán)重衰減步數(shù)動(dòng)態(tài)變化．該衰減策略充分利用了慣性權(quán)重可以提升傳統(tǒng)PSO性能的作用．通過計(jì)算機(jī)仿真對比PSO、LDWPSO、EXPPSO、CFPSO、GDIWPSO、基于動(dòng)態(tài)加速度系數(shù)的粒子群算法(particle swarm optimization based on dynamic acceleration coefficients, PSO-DAC)[18]和LUO[19]提出的慣性權(quán)重自適應(yīng)粒子群算法(inertia weight adaptive particle swarm optimization, 本研究簡稱PSO-LH)以及NDPSO算法在8個(gè)標(biāo)準(zhǔn)測試函數(shù)中的收斂速度和收斂精度，證明NDPSO算法綜合性能最佳．

1 粒子群優(yōu)化算法及其改進(jìn)算法

基本PSO算法中，速度和位移更新公式[1]為

vid(t+1)=ωvid(t)+c1r1[pbest(t)-xid(t)]+

c2r2[gbest(t)-xid(t)]

(1)

xid(t+1)=xid(t)+vid(t+1)

(2)

其中，vid(t+1)和xid(t+1)分別為粒子i在第t+1代的第d維速度和位置；c1和c2為學(xué)習(xí)率；r1和r2為[0, 1]間均勻分布的隨機(jī)數(shù); pbest(t)為粒子個(gè)體在第t代所得的最優(yōu)位置信息； gbest(t)為種群在第t代所得的最優(yōu)位置信息； 慣性權(quán)重ω計(jì)算式[12]為

(3)

其中，ωmax和ωmin分別為最大和最小加權(quán)系數(shù)；tmax為最大迭代次數(shù)．文獻(xiàn)[12]的實(shí)驗(yàn)證明該參數(shù)能加快算法的收斂速度，且動(dòng)態(tài)變化的ω比固定的ω效果更好，當(dāng)ω從0.9動(dòng)態(tài)衰減到0.4時(shí)性能最佳.

EXPPSO算法[13]中的ω與LDWPSO算法中的ω不同，ω被遞減的指數(shù)函數(shù)e-αE替代，其中，αE為影響移動(dòng)步長的大小，由當(dāng)前迭代次數(shù)控制，則速度公式修改為

vid(t+1)=e-αEvid(t)+

c1r1[pbest(t)-xid(t)]+

c2r2[gbest(t)-xid(t)]

(4)

由于指數(shù)函數(shù)的特點(diǎn)，算法前期搜索步長較大，擴(kuò)大了搜索區(qū)域，保證了前期的全局搜索能力．后期較小的步長減緩粒子更新速度，避免極值問題．YAN等[13]通過實(shí)驗(yàn)證明，指數(shù)衰減策略可以很快找到最優(yōu)解．

受非線性指數(shù)權(quán)重衰減的啟發(fā)，本研究提出的NDPSO算法將從線性衰減和非線性衰減兩個(gè)角度進(jìn)行研究．其中，ω是以正態(tài)分布曲線進(jìn)行衰減．在前期一定次數(shù)的迭代過程中，ω始終保持較大的數(shù)值，使算法的全局搜索能力持續(xù)最大，令算法能快速收斂到最優(yōu)解所在的區(qū)域內(nèi)．中期ω迅速衰減，全局搜索能力慢慢減弱，局部搜索能力逐漸增強(qiáng)，并最終使得兩種搜索能力保持動(dòng)態(tài)平衡．后期ω減小到一定值后，算法不斷迭代，令其局部搜索能力達(dá)到最強(qiáng)．可見，該算法充分利用了ω對PSO算法收斂速度和能力的影響，動(dòng)態(tài)變化的ω引導(dǎo)算法避免陷入局部最優(yōu)，并且保證了收斂的速度．

2 NDPSO算法

針對現(xiàn)有的慣性權(quán)重線性衰減PSO算法存在的衰減機(jī)制落后、速度較慢和易陷入局部最優(yōu)等缺點(diǎn)，本研究引入正態(tài)分布曲線提出NDPSO算法，既保證了粒子群優(yōu)化算法速度快的特性，還較好的克服了易陷入局部最優(yōu)的缺點(diǎn)．

正態(tài)分布也叫常態(tài)分布，是連續(xù)隨機(jī)變量概率分布的一種，在自然界和人類社會(huì)普遍存在．一般正態(tài)分布的函數(shù)公式為

(5)

其中，x為隨機(jī)變量；μ為正態(tài)分布的位置參數(shù)，描述正態(tài)分布的集中趨勢位置;θ描述了正態(tài)分布數(shù)據(jù)分布的離散程度.

為尋找合適的正態(tài)分布曲線，滿足衰減機(jī)制，首先針對正態(tài)分布曲線的核心參數(shù)進(jìn)行仿真分析．取θ=0.200 0～0.700 0， 由正態(tài)分布的算法機(jī)制可知，θ越大，圖形越扁平，如圖1．從圖1可見，當(dāng)θ=0.200 0時(shí)，曲線十分陡峭，隨著θ增至0.400 0～0.500 0時(shí)，曲線基本滿足NDPSO算法的要求．文獻(xiàn)[11]通過大量實(shí)驗(yàn)證明，若ω以線性或非線性衰減，則0.9～0.4是較佳衰減值．本研究經(jīng)大量仿真實(shí)驗(yàn)得到μ=0，θ=0.443 3為最佳值．故為使x=0時(shí)，f(x)=0.9， 設(shè)θ=0.443 3． 此時(shí)，正態(tài)分布曲線ω從0.9開始遞減．將式(5)應(yīng)用到標(biāo)準(zhǔn)PSO算法中，得到ω的非線性變化公式，如式(6)，速度更新則沿用式(1)．

(6)

其中，tmax為最大迭代次數(shù)；t為當(dāng)前迭代次數(shù)；θ=0.443 3．

圖1 正態(tài)分布曲線圖Fig.1 (Color online) Normal distribution picture

為適應(yīng)ω的變化特點(diǎn)，引入如式(7)的λ， 并采用式(8)為粒子群位置公式，使算法的搜索步長隨著粒子的適應(yīng)度值變化而動(dòng)態(tài)變化．

(7)

xid(t+1)=xid(t)+λvid(t+1)

(8)

從圖1可見，當(dāng)x>0時(shí)，正態(tài)分布曲線呈“Z”型．在迭代剛開始時(shí)，由于初期整個(gè)解空間很大，為了加快收斂速度，ω保持0.9或比0.9略小的值，令算法以一個(gè)較大的步長搜索整個(gè)解空間，全局搜索能力此時(shí)達(dá)到最大，且收斂速度增加，也不易陷入局部最優(yōu)．在經(jīng)過一定的迭代次數(shù)后，ω開始迅速衰減，全局搜索能力逐步減弱；隨著ω減小，搜索步長減小，算法達(dá)到全局搜索和局部搜索的平衡．當(dāng)?shù)鷮⒁Y(jié)束時(shí)，ω的值已經(jīng)極小，此時(shí)算法進(jìn)入局部搜索，步長小，搜索不會(huì)遺漏最優(yōu)解，由于后期能搜索的解空間已經(jīng)相當(dāng)小，所以收斂速度不會(huì)降低，這就令算法在保證速度的同時(shí)，能精確找到最優(yōu)解．

1)初始化種群中粒子的位置和速度；

2)將粒子的pbest設(shè)置為當(dāng)前個(gè)體最優(yōu)值，將gbest設(shè)置為初始群體中全局最優(yōu)；

3)計(jì)算每個(gè)粒子的適應(yīng)度值；

4)對每個(gè)粒子，若粒子適應(yīng)度值優(yōu)于pbest，則更新pbest；

5)對每個(gè)粒子，若粒子適應(yīng)度值優(yōu)于gbest，則更新gbest；

6)根據(jù)當(dāng)前迭代次數(shù)和式(6)計(jì)算ω的值，根據(jù)式(7)更新λ的值；

從《試點(diǎn)辦法》的規(guī)定來看，值班律師參與認(rèn)罪認(rèn)罰案件始于偵查階段。但是《試點(diǎn)辦法》對值班律師的參與方式并沒有明確的規(guī)定?！对圏c(diǎn)辦法》僅僅在第10條中規(guī)定:人民檢察院在審查起訴過程中應(yīng)當(dāng)聽取值班律師的意見，犯罪嫌疑人簽署具結(jié)書時(shí)值班律師具有在場權(quán)。這表明值班律師在認(rèn)罪認(rèn)罰案件中的參與程度還是有限的。

7)用式(1)和式(9)更新粒子的速度和位置；

8)判斷算法終止準(zhǔn)則是否滿足，如果滿足，算法停止；否則轉(zhuǎn)向3)．

NDPSO算法的核心部分是ω的更新衰減策略，每次迭代都使用新的ω值來更新粒子的速度和位置．這樣局部搜索能力和全局搜索能力在算法優(yōu)化的每個(gè)階段都能發(fā)揮應(yīng)有的作用．這種 “Z”型曲線使算法不易陷入局部最優(yōu)，且收斂速度很快．

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

通過對8個(gè)典型標(biāo)準(zhǔn)測試函數(shù)(表1，各函數(shù)具體表達(dá)式請掃描論文末頁右下角二維碼查看)的測試，比較NDPSO算法與其他改進(jìn)PSO算法的性能．其中，f1到f4為單峰函數(shù)，f1(x)是一個(gè)簡單的單峰二次函數(shù)，最小值為0，f3(x)的全局最小值位于拋物線形山谷中，很難找到最小值；f5(x)到f8(x)為多峰函數(shù)，f6(x)和f7(x)都具有多個(gè)局部最小值，很難找到最小值．對比算法分別為PSO、LDWPSO、 CFPSO、 EXPPSO、 PSO-DCA和PSO(LH)．

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

PSO算法的參數(shù)有3種，ω、r1和r2、c1和c2． 其中，ω是控制當(dāng)前速度對新產(chǎn)生速度的影響，用于平衡局部搜索和全局搜索能力；r1和r2是[0, 1]內(nèi)的隨機(jī)數(shù)；c1和c2為學(xué)習(xí)率，用來控制自身記憶和整個(gè)種群之間的相對影響．

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

為保持實(shí)驗(yàn)的一致性，設(shè)置搜索維數(shù)為30，種群規(guī)模為30，最大迭代次數(shù)為1 000，c1=c2=2， π=3.141 59，ωmax=0.9，ωmin=0.4， 其余參數(shù)分別按照對應(yīng)論文設(shè)置．每個(gè)算法計(jì)算20次，最優(yōu)解取平均值．文獻(xiàn)[12]指出，ω從0.9到0.4進(jìn)行線性與非線性曲線衰減最佳，故為充分發(fā)揮正態(tài)分布曲線的優(yōu)勢，本研究設(shè)NDPSO的μ=0，θ=0.443 3．

3.2 仿真結(jié)果及比較

通過Matlab仿真，得到不同算法在8個(gè)測試函數(shù)中的收斂曲線如圖2．8種算法的最優(yōu)解如表2．其中，灰底數(shù)據(jù)為8個(gè)算法中精度最高的解．

函數(shù)f1(x)到f4(x)是簡單的單峰測試函數(shù)，對比圖2(a)至(d)和表2可見，NDPSO算法在保證收斂速度的同時(shí)，收斂精度也遠(yuǎn)大于其他改進(jìn)PSO算法．由于f1(x)至f4(x)測試函數(shù)的單峰性，函數(shù)求解相對簡單，EXPPSO和CFPSO算法的收斂速度可得到最大發(fā)揮，NDPSO算法的收斂速度次之．但是，EXPPSO和CFPSO算法是通過犧牲收斂精度換取速度，導(dǎo)致性能不如NDPSO和LDWPSO算法． 而且從圖2(a)至(d)可見， 隨著迭代次數(shù)的增加，NDPSO算法的收斂曲線下降明顯，收斂速度和步長隨著迭代次數(shù)動(dòng)態(tài)調(diào)整，保證了算法在加快收斂速度的同時(shí)仍能保持最優(yōu)解的精度．LDWPSO算法的收斂精度雖略次于NDPSO算法，但收斂速度大不如NDPSO算法．與NDPSO算法機(jī)理相似的GDIWPSO算法，雖然較其他算法有兼顧速度和精度的優(yōu)勢，但NDPSO算法綜合效果更優(yōu)． PSO-DAC和PSO(LH)算法無論是收斂速度還是收斂精度都遠(yuǎn)遜于NDPSO算法，這兩種算法的慣性權(quán)重機(jī)制都未能發(fā)揮ω的作用．在單峰函數(shù)求解上，NDPSO算法能同時(shí)滿足收斂速度和收斂精度要求．

圖2 不同算法在8個(gè)測試函數(shù)中的收斂曲線圖Fig.2 (Color online) Convergence curves of different algorithms in eight test functions

表2 不同算法在8個(gè)測試函數(shù)中的平均最優(yōu)解1)

1)帶陰影的數(shù)據(jù)為8個(gè)算法中精度最高的解

函數(shù)f5(x)到f8(x)是較為復(fù)雜的多峰函數(shù)，算法很容易陷入局部最優(yōu)，導(dǎo)致無法收斂．結(jié)合圖2(e)至(h)和表2發(fā)現(xiàn)，NDPSO算法在多峰函數(shù)上性能依然出色．在收斂速度上，NDPSO算法的表現(xiàn)比其他改進(jìn)的PSO算法更好，且收斂精度也大幅提高．從圖2(f)和(h)可見，NDPSO算法收斂速度最快且找到的最優(yōu)解精度最高．與之相比，線性權(quán)重衰減策略的衰減機(jī)制在復(fù)雜的多峰函數(shù)只能保證收斂精度，不能保證快速收斂．由于多峰函數(shù)的特殊性，求解較為復(fù)雜，極易陷入局部最優(yōu)．而NDPSO算法幾乎不會(huì)陷入局部最優(yōu)，其ω衰減機(jī)制保證了前期的收斂步長，防止陷入局部最優(yōu)導(dǎo)致算法無法進(jìn)行．

綜上可見，NDPSO算法不管在單峰函數(shù)問題還是多峰函數(shù)問題上，總體性能都優(yōu)于PSO、LDWPSO、CFPSO、 EXPPSO、GDIWPSO、PSO-DAC和PSO(LH)算法．

結(jié) 語

本研究利用正態(tài)分布的曲線特征，提出了一種基于正態(tài)分布衰減慣性權(quán)重的粒子群算法NDPSO．該算法前期緩慢收斂，中期加速收斂，后期趨于平緩，保證了算法在前期的全局搜索能力，中期局部搜索能力與全局搜索能力的平衡，后期強(qiáng)化了局部搜索能力．理論分析和實(shí)驗(yàn)數(shù)據(jù)比較發(fā)現(xiàn)，其他線性衰減權(quán)重PSO、收縮因子PSO和高斯分布PSO相比，NDPSO算法在簡單的單峰函數(shù)測試中有著不俗的收斂速度和收斂精度，而在多峰函數(shù)測試中也始終能收斂到最優(yōu)解和保持較快的收斂速度，說明NDPSO充分利用了ω對PSO算法收斂機(jī)制的影響，能解決多種優(yōu)化問題．