宋夢培，莫禮平，周愷卿

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

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

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

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]的均勻隨機數(shù)；vi為粒子速度，vi∈[-vmax,vmax]，vmax是用戶設(shè)定的用來限制粒子速度的常量.

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類參數(shù)對標(biāo)準(zhǔn)PSO算法的影響分析

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

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

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

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

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

(ⅱ)當(dāng)c2較大時，粒子的社會認知能力較強，容易陷入局部最優(yōu).

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

3 測試實驗

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

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

表1 測試函數(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的動態(tài)變化對算法性能的影響，按如下策略進行取值：

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

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

3.3 實驗結(jié)果與討論

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

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

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

表3 5個測試函數(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ù)是只有全局極值點而沒有局部極值點的單峰函數(shù)，通常用來測試算法的優(yōu)化精度.由表3和圖3可知：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

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

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

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

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

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