一種帶變異算子的粒子群算法

(朔州師范高等?？茖W(xué)校 數(shù)學(xué)與計(jì)算機(jī)系,山西 朔州 036000)

通過觀察和模擬鳥類覓食行為,我們得到了粒子群算法(PSO),這是一種通過隨機(jī)搜索找到最優(yōu)解的算法.由于算法簡單易行,因此被普遍應(yīng)用于神經(jīng)網(wǎng)絡(luò)和函數(shù)優(yōu)化領(lǐng)域.

PSO算法也存在缺點(diǎn),如收斂慢,容易困于局部收斂.因此,本文提出一種基于變異算子的粒子群算法(MPSO),該算法根據(jù)一定概率改變運(yùn)行過程中發(fā)現(xiàn)的當(dāng)前個(gè)體極值，從而跳出局部收斂,然后執(zhí)行全局搜索.通過性能函數(shù)測(cè)試,新算法能有效進(jìn)行全局尋優(yōu),且提高收斂進(jìn)度和解的精確度.

1 標(biāo)準(zhǔn)粒子群優(yōu)化算法(PSO)

該P(yáng)SO算法需要開始設(shè)置一組隨機(jī)粒子.也就是說,在D維空間中隨機(jī)設(shè)置m個(gè)粒子,其中粒子k的位置表示為xk=(xk1,xk2,…,xkD),k=1,2,…,m,粒子k的行進(jìn)速度是vk=(vk1,vk2,…,vkD),到目前為止,粒子k找到的最佳位置為pbk=(pbk1,pbk2,…,pbkD),整個(gè)粒子種群所找到的全局最佳位置為gb=(gb1,gb2,…,gbd),每個(gè)粒子的速度和位置的計(jì)算如下:

(1)

(2)

其中,k=1,2,…,m是粒子數(shù),i=1,2,…,n是運(yùn)行次數(shù),d=1,2,…,D是維數(shù);c1和c2是加速常數(shù),它們代表粒子運(yùn)動(dòng)到gb和pb位置的權(quán)重;vkd∈[vmin,vmax],vmin和vmax是常數(shù),根據(jù)問題具體設(shè)定;r1和r2是介于[0,1]之間的隨機(jī)數(shù);w是慣性系數(shù),通常在0.1～0.9之間,如果算法運(yùn)行時(shí)w線性減小,該算法的收斂性能將更優(yōu)越[1],因此本文算法w采用以下形式:

(3)

(其中當(dāng)前運(yùn)行次數(shù)是i,算法運(yùn)行總的次數(shù)是imax;最小慣性系數(shù)是wmin,最大慣性系數(shù)是wmax).

2 帶變異算子的粒子群算法

文獻(xiàn)[2]提出了一種速度變動(dòng)PSO算法,該算法是改變粒子速度以跳出局部最優(yōu).本文效仿該思想,提出在合適的時(shí)機(jī)按一定幾率修改粒子的個(gè)體極值pbk的粒子群算法(MPSO),從而粒子的行進(jìn)方向得以變動(dòng).通過這種方式,粒子可以在其它區(qū)域中搜索最佳值,跳出局部最優(yōu)值,并改善全局收斂.

然而,當(dāng)執(zhí)行變異操作時(shí),通常難以控制,因此必須首先確定變動(dòng)的時(shí)機(jī).這個(gè)時(shí)機(jī)與粒子群的行進(jìn)狀況有關(guān),粒子群的行進(jìn)狀況可以通過種群適應(yīng)度的方差來給出.

有m個(gè)粒子,favg——這群粒子當(dāng)前的平均速度,fk——第k粒子適應(yīng)度,σ2——粒子群的種群適應(yīng)度方差,則:

(4)

其中f為歸一化定標(biāo)因子,f的值是:f=max{1,max{|fk-favg|}},k=1,2,…，m.

[注]:群體適應(yīng)方差σ2的大小可反映粒子群的“收斂”程度.σ2較小粒子群接近收斂(全局收斂或者局部收斂); 相反,粒子群是非收斂的并且需要隨機(jī)搜索.因此,如果σ2值很小并且問題的理論最優(yōu)值差算法所產(chǎn)生的實(shí)際最優(yōu)值很遠(yuǎn),我們認(rèn)為該算法已經(jīng)局部收斂.

若算法困于局部收斂,則讓粒子k的個(gè)體極值pbk根據(jù)概率p變異.

若算法困于局部收斂,則讓粒子k的個(gè)體極值pbk根據(jù)概率p變異.

(5)

fm(理論最佳值),f(gb)(gb適應(yīng)度),μ(收斂精確度),γ值通常遠(yuǎn)小于σ2的最大值.

粒子k的個(gè)體極值pbk作如下變動(dòng):

① 首先生成一個(gè)與正態(tài)分布N(0,1)匹配的隨機(jī)數(shù)r.

②pbk變異:pbk=pbk×(1+r)

具體算法流程圖1所示.

圖1 算法流程圖

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

由三個(gè)性能測(cè)試函數(shù)Griewank函數(shù)、Rosenbrock函數(shù)、Ackley函數(shù)(求最小值)來驗(yàn)證本文MPSO算法的性能,同時(shí)與標(biāo)準(zhǔn)PSO算法、文獻(xiàn)[2]的算法作仿真分析和比較.三個(gè)性能測(cè)試函數(shù)[2]如下:

Griewank函數(shù)

(6)

Rosenbrock函數(shù)

(7)

Ackley函數(shù)

(8)

表1 實(shí)驗(yàn)參數(shù)

上述三個(gè)性能測(cè)試函數(shù)是多峰值函數(shù),具有大量局部極點(diǎn),最小值為零.實(shí)驗(yàn)的參數(shù)見表1,其中:算法的種群大小都設(shè)置為50,收斂精確度μ=10-7,c1=c2=2,最大運(yùn)行次數(shù)設(shè)定為1 000,慣性系數(shù)w:

其中i為當(dāng)前的運(yùn)行次數(shù),imax為總運(yùn)行次數(shù),wmin為最小慣性系數(shù),wmax為最大慣性系數(shù),慣性系數(shù)w從0.9線性遞減到0.1.表2出示了運(yùn)行20次后得的結(jié)果.

表2 三種算法的仿真結(jié)果

為了更好地反映三種算法的收斂性能,如圖2、圖3、圖4所示.為了比較,縱坐標(biāo)是適應(yīng)度的對(duì)數(shù).

圖2 Griewank函數(shù)，xk =[-50,50],D=30最佳適應(yīng)度進(jìn)化曲線

圖3 Resenbrock函數(shù)xk =[-50,50],D=30最佳適應(yīng)度進(jìn)化曲線

圖4 Ackley函xk∈[-50,50],D=30最佳適應(yīng)度進(jìn)化曲線

從表2的數(shù)據(jù)和圖2、圖3、圖4可以發(fā)現(xiàn),MPSO算法較PSO算法和文獻(xiàn)[2]的算法更接近最優(yōu)解,全局收斂性能、收斂進(jìn)度和精確度更好.

4 結(jié)論

為了更好的找到全局最優(yōu)解,文中效仿文獻(xiàn)[3]的算法,在標(biāo)準(zhǔn)PSO算法的基礎(chǔ)上,做了改進(jìn),得到了具有變異算子的粒子群算法(MPSO).驗(yàn)證結(jié)果顯示,該算法的改進(jìn)方案是可行的,得到的結(jié)果更接近最佳值,全局收斂性能更好.