宋夢(mèng)培，莫禮平，周愷卿

(吉首大學(xué)信息科學(xué)與工程學(xué)院，湖南 吉首 416000)

粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法，是Kennedy博士和Eberhart博士于1995年通過(guò)研究鳥(niǎo)群聚集和遷徙的覓食行為而提出的一種基于群體的自適應(yīng)搜索優(yōu)化技術(shù)[1-2].由于PSO算法具有操作簡(jiǎn)單、易于實(shí)現(xiàn)和魯棒性好等優(yōu)點(diǎn)，因此該算法一經(jīng)提出就引起了學(xué)者們的極大興趣.SHI等[3]在粒子群算法中引入慣性因子，以平衡算法的全局搜索能力和局部搜索能力.這一改進(jìn)算法被稱(chēng)為標(biāo)準(zhǔn)PSO算法.Suganthan[4]提出了一種基于動(dòng)態(tài)鄰域的PSO模型.該模型中，用每個(gè)粒子的當(dāng)前鄰域極值代替全局極值，結(jié)合不同的領(lǐng)域結(jié)構(gòu)有效地改進(jìn)算法的收斂性.Higashi Natsuki等[5]在PSO算法中引入自適應(yīng)的變異算子，從而提高了粒子跳出局部極值的能力和粒子的尋優(yōu)概率.LI等[6]提出了一種能夠增強(qiáng)粒子之間交流的動(dòng)態(tài)學(xué)習(xí)策略，該策略能有效提高算法的運(yùn)行效率.張寅等[7]提出了一種混沌策略，該策略通過(guò)在迭代停滯時(shí)初始化粒子位置來(lái)保證粒子的多樣性.XIA等[8]通過(guò)定期對(duì)變量空間進(jìn)行劃分，逐步縮小搜索區(qū)域，來(lái)提高算法的收斂速度和尋優(yōu)精度.Mahdavi等[9]提出了一種基于變量效應(yīng)的協(xié)同多級(jí)進(jìn)化策略，該策略通過(guò)決策變量將問(wèn)題分解，減少了求解復(fù)雜度.改進(jìn)后的粒子群算法能較大概率地找到問(wèn)題的全局最優(yōu)解，并且已成功應(yīng)用于約束優(yōu)化問(wèn)題[10-11]、調(diào)度問(wèn)題[12]、圖形圖像處理[13]、數(shù)據(jù)挖掘[14]和電力系統(tǒng)調(diào)控[15]等領(lǐng)域.盡管學(xué)者們對(duì)標(biāo)準(zhǔn)PSO算法展開(kāi)了廣泛的討論，但是關(guān)于慣性權(quán)值和學(xué)習(xí)因子對(duì)算法性能的影響并沒(méi)有作詳細(xì)探究.筆者擬選取慣性權(quán)值和學(xué)習(xí)因子2類(lèi)參數(shù)，基于標(biāo)準(zhǔn)PSO算法，通過(guò)分析2類(lèi)參數(shù)不同的取值策略對(duì)常用測(cè)試函數(shù)的優(yōu)化結(jié)果的影響，來(lái)探究2類(lèi)參數(shù)對(duì)算法性能的影響.

1 標(biāo)準(zhǔn)PSO算法的基本框架與描述

1.1 算法框架

標(biāo)準(zhǔn)PSO算法的基本框架如圖1所示.

圖1 標(biāo)準(zhǔn)PSO算法的基本框架Fig. 1 Basic Framework of the Standard PSO Algorithm

假設(shè)在一個(gè)D維的目標(biāo)搜索空間中，有N個(gè)粒子組成一個(gè)群落，粒子自身最優(yōu)位置為個(gè)體極值pbest，當(dāng)前全局的最優(yōu)位置為全局極值gbest.每個(gè)粒子追隨當(dāng)前的最優(yōu)粒子在解空間中運(yùn)動(dòng)，并根據(jù)如下公式來(lái)更新自己的速度和位置：

vi+1=wvi+c1r1(pbesti-xi)+c2r2(gbestt-xi)，

(1)

xi+1=xi+vi+1.

(2)

其中：w為慣性權(quán)值；c1和c2為學(xué)習(xí)因子，分別反映粒子的自我學(xué)習(xí)能力和向群體最優(yōu)粒子學(xué)習(xí)的能力；r1和r2為[0,1]的均勻隨機(jī)數(shù)；vi為粒子速度，vi∈[-vmax,vmax]，vmax是用戶(hù)設(shè)定的用來(lái)限制粒子速度的常量.

1.2算法描述

標(biāo)準(zhǔn)PSO算法的流程如圖2所示，其中precent為粒子當(dāng)前的適應(yīng)度值.

圖2 標(biāo)準(zhǔn)PSO算法的流程Fig. 2 Flow Chart of the Standard PSO Algorithm

2 2類(lèi)參數(shù)對(duì)標(biāo)準(zhǔn)PSO算法的影響分析

由(1)，(2)式可知，慣性權(quán)值w和學(xué)習(xí)因子c1，c2的取值策略直接影響標(biāo)準(zhǔn)PSO算法的性能.w反映粒子對(duì)當(dāng)前速度的繼承情況：

(ⅰ)當(dāng)w較大時(shí)，粒子的全局搜索能力較強(qiáng)；

(ⅱ)當(dāng)w較小時(shí)，粒子的局部搜索能力較強(qiáng).

學(xué)習(xí)因子c1，c2分別反映粒子的自我學(xué)習(xí)能力和向群體最優(yōu)粒子學(xué)習(xí)的能力：

(ⅰ)當(dāng)c1較大時(shí)，粒子的自我認(rèn)知能力較強(qiáng)，容易偏離最優(yōu)粒子；

(ⅱ)當(dāng)c2較大時(shí)，粒子的社會(huì)認(rèn)知能力較強(qiáng)，容易陷入局部最優(yōu).

筆者將基于標(biāo)準(zhǔn)PSO算法，通過(guò)分析2類(lèi)參數(shù)不同的取值策略對(duì)常用測(cè)試函數(shù)優(yōu)化結(jié)果的影響，來(lái)探究w，c1，c2對(duì)標(biāo)準(zhǔn)PSO算法性能的影響.

3 測(cè)試實(shí)驗(yàn)

3.1 測(cè)試函數(shù)的選取

為了更好地評(píng)價(jià)改進(jìn)參數(shù)后算法性能的優(yōu)劣，選取PSO算法常用的5個(gè)測(cè)試函數(shù)(Sphere，Rosenbrock，Griewank，Ackley，Rastrigrin)進(jìn)行實(shí)驗(yàn)設(shè)計(jì)，其中Sphere和Rosenbrock是單峰函數(shù)，其他均為多峰函數(shù).測(cè)試函數(shù)的具體設(shè)置見(jiàn)表1.

表1 測(cè)試函數(shù)

3.2 參數(shù)變化策略的選取

在標(biāo)準(zhǔn)PSO算法中，慣性權(quán)值最優(yōu)范圍為[0.4,0.9]，學(xué)習(xí)因子通常取常數(shù)2[3].為了探究w，c1，c2的動(dòng)態(tài)變化對(duì)算法性能的影響，按如下策略進(jìn)行取值：

慣性權(quán)值w的動(dòng)態(tài)選取策略為：遞增策略，w=0.4+0.5t/MaxDT；遞減策略，w=0.9-0.5t/MaxDT.

學(xué)習(xí)因子c1和c2的動(dòng)態(tài)選取策略均為：遞增策略，c=1+sin(tπ/MaxDT)；遞減策略，c=2-sin(tπ/MaxDT).其中：t為迭代次數(shù)；MaxDT為最大迭代次數(shù).

3.3 實(shí)驗(yàn)結(jié)果與討論

3.3.1 參數(shù)設(shè)置對(duì)5個(gè)測(cè)試函數(shù)均設(shè)計(jì)15組對(duì)比實(shí)驗(yàn).各組實(shí)驗(yàn)中，基本參數(shù)設(shè)置如下：N=40，MaxDT=1 000，D=5.w，c1，c2的取值見(jiàn)表2.

表2 2類(lèi)參數(shù)的取值

3.3.2 函數(shù)仿真結(jié)果 表3給出了5個(gè)測(cè)試函數(shù)的仿真結(jié)果，圖3～7分別示出了5個(gè)測(cè)試函數(shù)的收斂曲線.

表3 5個(gè)測(cè)試函數(shù)的仿真結(jié)果

圖3 Sphere函數(shù)的收斂曲線Fig. 3 Convergence Curve of Sphere Function

圖4 Rosenbrock函數(shù)的收斂曲線Fig. 4 Convergence Curve of Rosenbrock Function

圖5 Griewank函數(shù)的收斂曲線Fig. 5 Convergence Curve of Griewank Function

圖6 Ackley函數(shù)的收斂曲線Fig. 6 Convergence Curve of Ackley Function

圖7 Rastrigrin函數(shù)的收斂曲線Fig. 7 Convergence Curve of Rastrigrin Function

Sphere函數(shù)是只有全局極值點(diǎn)而沒(méi)有局部極值點(diǎn)的單峰函數(shù)，通常用來(lái)測(cè)試算法的優(yōu)化精度.由表3和圖3可知：

(1)當(dāng)c1，c2為常數(shù)且w采取動(dòng)態(tài)改變策略時(shí)，標(biāo)準(zhǔn)PSO算法的尋優(yōu)精度明顯提高.當(dāng)w遞增時(shí)，收斂速度加快；當(dāng)w遞減時(shí)，尋優(yōu)精度提高.

(2)當(dāng)w為常數(shù)且c1，c2采取動(dòng)態(tài)改變策略時(shí)，標(biāo)準(zhǔn)PSO算法的尋優(yōu)精度顯著提高，且比動(dòng)態(tài)改變w時(shí)的精度更高.當(dāng)c2遞增時(shí)，收斂速度加快.

(3)當(dāng)w遞增時(shí)，標(biāo)準(zhǔn)PSO算法的收斂速度明顯加快.當(dāng)c1，c2同增同減時(shí)，收斂適應(yīng)度值降低；當(dāng)c2遞增時(shí)，尋優(yōu)精度明顯提高.

(4)當(dāng)w遞減時(shí)，標(biāo)準(zhǔn)PSO算法的收斂速度略微降低.但當(dāng)c1遞減時(shí)，收斂適應(yīng)度值明顯降低.

Rosenbrock函數(shù)是只有全局極值點(diǎn)而沒(méi)有局部極值點(diǎn)的非凸病態(tài)函數(shù)，極難收斂于全局極值點(diǎn)，通常用來(lái)評(píng)價(jià)優(yōu)化算法的執(zhí)行效率.由表3和圖4可知：

(1)當(dāng)c1，c2為常數(shù)且w遞增時(shí)，標(biāo)準(zhǔn)PSO算法的收斂速度加快，但尋優(yōu)概率并沒(méi)有明顯提高；當(dāng)c1，c2為常數(shù)且w遞減時(shí)，尋優(yōu)概率略微提高，尋優(yōu)波動(dòng)的范圍明顯縮小.

(2)當(dāng)w為常數(shù)且c1，c2同增同減時(shí)，標(biāo)準(zhǔn)PSO算法的收斂速度加快；當(dāng)w為常數(shù)且c1，c2一增一減時(shí)，收斂適應(yīng)度值降低.c1，c2的動(dòng)態(tài)改變縮小了尋優(yōu)波動(dòng)的范圍，提高了粒子尋優(yōu)概率.

(3)當(dāng)w遞增時(shí)，標(biāo)準(zhǔn)PSO算法的收斂速度明顯加快.當(dāng)c1遞減時(shí)，收斂適應(yīng)度值降低；當(dāng)c1，c2同增同減時(shí)，尋優(yōu)概率提高.

(4)當(dāng)w遞減時(shí)，標(biāo)準(zhǔn)PSO算法的收斂速度略微降低.但當(dāng)c1，c2同增同減時(shí)，收斂適應(yīng)度值降低，算法的尋優(yōu)概率提高.

Griewank函數(shù)是由多個(gè)局部極值點(diǎn)包圍1個(gè)全局極值點(diǎn)的旋轉(zhuǎn)多峰函數(shù)，在5維空間均能找到全局最優(yōu)解.由表3和圖5可知：

(1)當(dāng)c1，c2為常數(shù)且w遞增時(shí)，標(biāo)準(zhǔn)PSO算法的收斂速度加快；當(dāng)c1，c2為常數(shù)且w遞減時(shí)，尋優(yōu)概率提高.

(2)當(dāng)w為常數(shù)且c1，c2同增同減時(shí)，標(biāo)準(zhǔn)PSO算法的收斂速度加快，收斂適應(yīng)度值降低.當(dāng)c2遞減時(shí)，尋優(yōu)概率提高；當(dāng)c2遞增時(shí)，尋優(yōu)精度提高.

(3)當(dāng)w遞增時(shí)，標(biāo)準(zhǔn)PSO算法的收斂速度明顯加快，且c1，c2一增一減時(shí)，收斂適應(yīng)度值降低.當(dāng)c2遞減時(shí)，尋優(yōu)概率提高；當(dāng)c2遞增時(shí)，尋優(yōu)精度提高.

(4)當(dāng)w遞減且c1，c2同增同減時(shí)，標(biāo)準(zhǔn)PSO算法的尋優(yōu)概率和尋優(yōu)精度同步提高，收斂適應(yīng)度值降低.

Ackley函數(shù)是具有很多局部極值的多峰函數(shù)，其圖像是一個(gè)有很多孔峰、起伏不平的曲面，w，c1，c2的動(dòng)態(tài)改變?cè)?維均能找到最優(yōu)解.由表3和圖6可知：

(1)當(dāng)c1，c2為常數(shù)且w遞增時(shí)，標(biāo)準(zhǔn)PSO算法的收斂速度加快；當(dāng)c1，c2為常數(shù)且w遞減時(shí)，尋優(yōu)精度提高.

(2)當(dāng)w為常數(shù)且c2遞增時(shí)，標(biāo)準(zhǔn)PSO算法的收斂速度和尋優(yōu)精度同步提高.

(3)當(dāng)w遞增時(shí)，標(biāo)準(zhǔn)PSO算法的收斂速度明顯加快，且當(dāng)c1遞增時(shí)，尋優(yōu)概率和尋優(yōu)精度同步提高.

(4)當(dāng)w遞減且c1，c2同增同減時(shí)，收斂適應(yīng)度值降低，但收斂速度和尋優(yōu)概率并沒(méi)有明顯改變.

Rastrigrin函數(shù)是典型的多峰函數(shù)，只有1個(gè)被多個(gè)隨余弦函數(shù)波動(dòng)的局部極值包圍的全局極值，很難找到全局極值點(diǎn).由表3和圖7可知：

(1)動(dòng)態(tài)改變w，c1，c2，只能適當(dāng)縮小標(biāo)準(zhǔn)PSO算法尋優(yōu)波動(dòng)的范圍，而不能找到全局的最優(yōu)解.但當(dāng)c1，c2為常數(shù)且w遞增時(shí)，收斂速度明顯加快；當(dāng)c1，c2為常數(shù)且w遞減時(shí)，尋優(yōu)波動(dòng)范圍縮小.

(2)當(dāng)w為常數(shù)且c2遞增時(shí)，標(biāo)準(zhǔn)PSO算法的收斂速度加快；當(dāng)w為常數(shù)且c2遞減時(shí)，尋優(yōu)波動(dòng)范圍縮小.

(3)當(dāng)w遞增時(shí)，標(biāo)準(zhǔn)PSO算法的收斂速度明顯加快，且當(dāng)c1，c2同增同減時(shí)，收斂適應(yīng)度值降低.

(4)當(dāng)w遞減時(shí)，標(biāo)準(zhǔn)PSO算法的收斂速度略微降低，但當(dāng)c1，c2一增一減時(shí)，收斂適應(yīng)度值明顯降低.

4 結(jié)語(yǔ)

基于標(biāo)準(zhǔn)PSO算法，通過(guò)分析慣性權(quán)值和學(xué)習(xí)因子2類(lèi)參數(shù)不同的取值策略對(duì)常用測(cè)試函數(shù)優(yōu)化結(jié)果的影響，來(lái)探究2類(lèi)參數(shù)對(duì)算法性能的影響.實(shí)驗(yàn)結(jié)果表明：

(1)w主要影響標(biāo)準(zhǔn)PSO算法的收斂速度，隨著w的遞增，收斂速度明顯加快；c1，c2主要影響尋優(yōu)精度，隨著c2的遞增，尋優(yōu)精度提高.

(2)w遞減與c1，c2一增一減結(jié)合，對(duì)標(biāo)準(zhǔn)PSO算法性能的優(yōu)化較好；w遞增與c1，c2同增同減結(jié)合，對(duì)算法性能的優(yōu)化效果較好.

(3)當(dāng)w，c1，c2均為動(dòng)態(tài)函數(shù)時(shí)，單峰函數(shù)的尋優(yōu)精度和收斂速度明顯提高，雙峰或多峰函數(shù)波動(dòng)的范圍縮小且尋優(yōu)概率提高.

(4)w，c1，c2的動(dòng)態(tài)改變對(duì)函數(shù)低維優(yōu)化效果明顯，但隨著維數(shù)的增加，尋優(yōu)難度加大，優(yōu)化效果迅速降低.

考慮到慣性權(quán)值和學(xué)習(xí)因子的改變僅對(duì)單峰函數(shù)的優(yōu)化效果較明顯，對(duì)多峰或雙峰函數(shù)并沒(méi)有明顯的優(yōu)化作用，下一步將結(jié)合蟻群算法、遺傳算法等來(lái)探究2類(lèi)參數(shù)對(duì)函數(shù)優(yōu)化效果的影響.