改進粒子速度和位置更新公式的粒子群優(yōu)化算法

李二超,高振磊

(蘭州理工大學電氣工程與信息工程學院,甘肅 蘭州 730050)

粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法是美國心理學家Kennedy和電氣工程師Eberhart受鳥類和魚類覓食行為啟發(fā)而提出的一種基于群體智能理論的演化計算技術[1]. 該算法因其計算內(nèi)存需求少、控制參數(shù)少等優(yōu)點得到廣泛關注,并被應用于求解諸多實際優(yōu)化問題,如路徑規(guī)劃[2]、優(yōu)化調度[3]、參數(shù)辨識[4]、圖像分割[5]等.

然而,標準PSO算法存在一些固有缺陷,如搜索精度低、局部搜索能力差,尤其求解復雜非線性多峰函數(shù)時容易陷入局部極小解出現(xiàn)“早熟”收斂[6]. 針對以上缺陷,國內(nèi)外學者做了大量改進研究,其中對粒子速度和位置更新公式的改進是研究熱點之一. Shi等[7]首次在速度更新項中引入隨迭代次數(shù)線性遞減的慣性權重w,以更好平衡算法全局開發(fā)能力與局部勘探能力. Liu等[8]指出PSO算法求解過程本身就是一個非線性過程,w呈非線性變化能更好改善算法性能,因此他提出基于Logistic混沌映射的非線性變化的w.對w的改進還有基于余弦函數(shù)[9]和基于Sigmoid函數(shù)非線性變化的w[10]等. Deep等[11]將粒子速度更新公式中個體最優(yōu)和群體最優(yōu)替換為二者線性組合,以此來增大粒子的搜索空間,從而使算法有更多可能搜索到全局最優(yōu)解. 胡旺等[12]提出一種簡化PSO算法,嘗試舍棄粒子速度項,由個體最優(yōu)粒子和群體最優(yōu)粒子來引導粒子更新,實驗結果表明這種改進極大提高了算法性能. Liu等[13]在簡化PSO算法[12]基礎上,引入粒子“維數(shù)信息”概念,將粒子位置更新分解為3種模式,3種模式分別具有改善全局開發(fā)能力、改善局部勘探能力、提高算法收斂速度的功能,并基于概率來選擇相應模式更新粒子位置. 陸松建等[14]在文獻[11-12]的基礎上提出一種均值簡化粒子群算法,該算法舍棄速度更新項,將文獻[11]對速度更新項的改進思想用于對位置更新的改進. Zhang等[15]提出2種不同的位置更新公式,并在算法不同迭代時期選擇相應公式,以此來改善算法性能. Liu等[8]在文獻[15]的研究基礎上,在當前粒子適應度值與種群中所有粒子的平均適應度值之間建立一種數(shù)學關系pi,提出一種自適應位置更新策略來更好平衡算法的全局開發(fā)能力和局部勘探能力. Cheng等[16]基于社會學習的思想,改進速度和位置更新機制,粒子速度和位置更新時不再向個體最優(yōu)和群體最優(yōu)學習,而向一些優(yōu)于自身的個體學習.

本文結合以上分析,借鑒文獻[8,11-13]的改進思想,提出一種新的粒子位置和速度自適應更新策略,引用文獻[8]中的自適應判定機制,并將文獻[13]提出的粒子維度信息引入粒子速度更新公式,將其與其他6種改進PSO算法在12個不同類型的測試函數(shù)上進行尋優(yōu)測試,證明了本文所提算法的有效性.

1 相關工作

1.1 標準粒子群優(yōu)化算法

標準PSO算法中,粒子通過學習自身歷史經(jīng)驗(pbest)與群體經(jīng)驗(gbest)尋找最優(yōu)粒子. 對于求解變量為X={x1,x2,…,xD}、目標函數(shù)為min{f(x)}的優(yōu)化問題,標準PSO算法粒子更新公式為式(1)和式(2).

vid(t+1)=wvid(t)+c1r1(pbestid-xid(t))+c2r2(gbestd-xid(t)),

(1)

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

(2)

式中,vid(t+1)和xid(t+1)分別為粒子i在t+1代的速度和位置;w是慣性權重,標準PSO算法中w隨迭代次數(shù)線性遞減;c1和c2為學習因子,通常取值為2;r1和r2是[0,1]均勻分布的隨機數(shù).

1.2 粒子速度更新公式的改進

(3)

圖1 MeanPSO算法和PSO算法粒子進化過程Fig.1 Particle evolution process of MeanPSO algorithm and PSO algorithm

MeanPSO算法和PSO算法中粒子運動過程如圖1所示.

從圖1可看出,MeanPSO算法中粒子搜索區(qū)間更廣,使得算法在進化前期有更大可能搜索到全局最優(yōu)解[14].

1.3 粒子位置更新公式的改進

文獻[13]提出一種帶有平均維度信息的分層簡化粒子群優(yōu)化(PHSPSO)算法,PHSPSO算法舍棄PSO算法中粒子速度更新項,并引入平均維度信息概念,即每個粒子所有維信息的平均值,計算公式為式(4). 同時PHSPSO算法將粒子位置更新公式分解為3種模式,分別為式(5)、(6)、(7).

(4)

xid(t+1)=wxid(t)+c1r1(pbestid-xid(t)),

(5)

xid(t+1)=wxid(t)+c2r2(gbestd-xid(t)),

(6)

xid(t+1)=wxid(t)+c3r3(pad-xid(t)),

(7)

其中,式(5)有助于算法的全局開發(fā)能力;式(6)有助于算法的局部勘探能力,幫助算法跳出局部最優(yōu);式(7)有助于提升算法的收斂速度.在迭代過程中,算法基于概率選擇不同的模式來更新粒子位置.

文獻[8]指出采用“X=X+V”來更新粒子位置有助于提高算法的局部勘探能力,而“X=wX+(1-w)V”有助于提高算法的全局開發(fā)能力,基于此本文提出一種自適應粒子位置更新機制,如式(8)、(9)所示.

(8)

(9)

式中,fit(·)為粒子的適應度值,N為種群中粒子個數(shù).式(8)中pi表示當前粒子適應度值與種群中所有粒子平均適應度值的比值,當pi較大時,當前粒子的適應度值遠大于種群中所有粒子平均適應度值,此時應采用“X=wX+(1-w)V”更新粒子位置以增強算法的全局開發(fā)能力,否則采用“X=X+V”來更新粒子位置,來保證算法的局部勘探能力.

2 改進算法

2.1 粒子速度和位置自適應更新策略

本文結合以上分析提出一種新的自適應粒子速度和位置更新策略,如式(10)、(11)所示.

(10)

(11)

上述自適應策略借鑒文獻[8]中pi作為自適應判定條件.當pi>δ時,當前粒子的適應度值遠大于種群中所有粒子平均適應度值,表明算法處于搜索初期或者當前粒子分布較為分散,此時應采用式(10)更新粒子速度和位置.式(10)在速度更新項中引入個體最優(yōu)和群體最優(yōu)的線性組合,能夠使粒子的搜索空間更廣,從而提高算法搜索到全局最優(yōu)解的可能性,而位置更新則采用“X=wX+(1-w)V”來提高算法的全局搜索能力;當pi<δ時,當前粒子的適應度值與種群中所有粒子平均適應度值相差不大,表明算法處于搜索中后期或者當前粒子分布較為集中,此時應采用式(11)更新粒子速度和位置.在式(11)中,位置更新采用“X=X+V”來保證算法局部勘探能力,防止算法在求解復雜多峰函數(shù)時陷入局部最優(yōu),而將粒子平均維度信息pad引入到粒子速度更新公式中,提高算法的收斂速度[13].

圖2 慣性權重隨迭代次數(shù)變化圖Fig.2 The variation of inertia weight with iteration times

2.2 慣性權重的選取

慣性權重w是PSO算法的重要參數(shù)之一,它可以平衡算法全局開發(fā)能力和局部勘探能力,標準PSO算法采用線性遞減w,這種線性調整的方式可以在一定程度上平衡算法開發(fā)能力與勘探能力,而在面對復雜非線性多維函數(shù)優(yōu)化問題時,算法容易陷入局部最優(yōu)解. 因此,為更好改善算法性能,一些學者提出慣性權重非線性調整策略. 本文采用文獻[8]提出的基于Logistic混沌映射非線性變化慣性權重w.

混沌映射作為一種非線性映射,因其所產(chǎn)生的混沌序列具有良好隨機性和空間遍歷性,在進化計算中得到廣泛應用,其中Logistic映射應用較為廣泛,它可以產(chǎn)生[0,1]之間的隨機數(shù). 式(12)給出了Logistic映射的定義,w的定義如式(13).

r(t+1)=4r(t)(1-r(t)),r(0)=rand, 其中,r0≠{0,0.25,0.75,1},

(12)

(13)

式中,wmax=0.9,wmin=0.4;r(t)是由式(12)迭代產(chǎn)生的隨機數(shù).慣性權重隨迭代次數(shù)的變化如圖2所示.

2.3 算法實現(xiàn)

算法實現(xiàn)步驟如下:

步驟1 參數(shù)初始化,包括種群規(guī)模N,最大迭代次數(shù)Tmax=1 000,學習因子c1和c2,慣性權重w;并在搜索空間內(nèi)隨機初始化粒子位置、速度;

步驟2 根據(jù)給定目標函數(shù)計算所有粒子適應度值;

步驟3 比較種群中所有粒子的適應度值與其經(jīng)歷過的最優(yōu)位置適應度值的優(yōu)劣,若前者更優(yōu),則用粒子的當前位置替代粒子的個體歷史最優(yōu)位置;

步驟4 比較種群中所有個體最優(yōu)位置的適應度值與整個群體經(jīng)歷過的最優(yōu)位置的適應度值的優(yōu)劣,若前者更優(yōu),則更新全局最優(yōu)位置;

步驟5 根據(jù)式(8)計算pi,若pi>δ,則利用式(10)更新粒子的速度和位置;否則,利用式(11)更新粒子的速度和位置;

步驟6 判斷是否滿足終止條件,若滿足,則算法終止并輸出最優(yōu)值;否則,轉至步驟2.

3 仿真實驗及結果分析

3.1 基本測試函數(shù)

為驗證所提算法有效性,本文選取12個具有不同特性的測試函數(shù)[13,15],將本文算法與線性遞減慣性權重粒子群優(yōu)化(LDWPSO)算法[7]、均值粒子群優(yōu)化(MeanPSO)算法[11]、社會學習粒子群優(yōu)化(SL-PSO)算法[16]、基于概率分層的簡化粒子群優(yōu)化(PHSPSO)算法[13]、基于終端交叉和轉向擾動的粒子群優(yōu)化(TCSPSO)算法[15]、一種基于自適應策略的改進粒子群優(yōu)化(MPSO)算法[8]進行對比測試. 12個測試函數(shù)的相關描述如表1所示. 其中函數(shù)f1、f2、f3、f4、f5是單峰函數(shù),主要用于測試算法的收斂速度和尋優(yōu)精度;函數(shù)f6、f7、f8、f9、f10、f11、f12是多峰函數(shù),主要用于測試算法跳出局部最優(yōu)避免“早熟”收斂的能力.

表1 12個基本測試函數(shù)Table 1 12 basic test functions

續(xù)表1 Table 1 continued

3.2 閾值參數(shù)δ取值對算法性能的影響

文獻[8]中閾值δ取值為[0,1]之間的隨機數(shù),本文認為閾值δ隨機變化不利于對當前粒子狀態(tài)準確判斷,從而影響算法性能.本文將進行一組實驗來驗證此觀點,進而確定閾值δ最佳取值.實驗選取表1中4個測試函數(shù)(D=100),算法獨立運行50次,取最優(yōu)結果的平均值作為比較,具體結果見表2.由表2知,δ取0.8時,對于單峰函數(shù)f4,算法收斂精度最高;而對于多峰函數(shù)f10、f12,算法收斂速度最快;對于函數(shù)f11,算法的收斂精度要遠優(yōu)于δ取1和rand時的結果.故本文δ取0.8. 表2中括號內(nèi)數(shù)字代表算法求得最優(yōu)解時的平均迭代次數(shù)(取整).

3.3 與其他改進PSO算法對比

本文使用Matlab軟件進行仿真,不同PSO算法設置相同種群規(guī)模N=100、最大迭代次數(shù)Tmax=1 000和變量維數(shù)D=30,其他參數(shù)設置與原文保持一致,具體見表3. 每個算法獨立運行50次,記錄50次運行結果的平均值(Mean value)和標準差(Standard deviation)來評價算法性能,結果見表4. 為更直觀對比各算法求解精度和收斂速度,圖3給出各算法求解12個測試函數(shù)時適應度值變化曲線.

表3 各PSO算法的參數(shù)設置Table 3 Parameter setting of each PSO algorithm

表2 參數(shù)δ不同取值的優(yōu)化結果比較Table 2 Comparison of optimization results with different values of parameter δ

表4 7種算法求解12個測試函數(shù)的結果對比(D=30)Table 4 Results comparison of 7 algorithms for 12 test functions(D=30)

續(xù)表4 Table 4 continued

圖3 12個測試函數(shù)的收斂曲線(30維)Fig.3 Convergence curves of 12 test functions(30 dimensions)

分析表4和圖3可知改進算法(IPSO-VP)在30維f1、f2、f3、f4、f55個單峰函數(shù)上,無論是求解精度、收斂速度還是穩(wěn)定性均優(yōu)于6個對比算法,且在函數(shù)f1、f2、f3、f5上IPSO-VP算法均能求得最優(yōu)值. 對于多峰函數(shù)f6、f7、f8、f9,雖然IPSO-VP與MeanPSO、PHSPSO、TCSPSO 算法均能求得函數(shù)最優(yōu)值且求解性能穩(wěn)定,但從圖3可看出IPSO-VP算法收斂速度更快. 對于多峰函數(shù)f10、f11、f12,IPSO-VP算法求解性能明顯優(yōu)于除SL-PSO算法外的5個算法,雖然SL-PSO算法的求解精度與IPSO-VP算法相同,但從圖3收斂曲線可看出IPSO-VP算法收斂更快,約迭代100～200次之后就完成收斂.

為進一步驗證IPSO-VP算法優(yōu)越性,將7種算法分別在60維和100維的12個測試函數(shù)上進行尋優(yōu)測試,表5、表6分別記錄了各算法在60維、100維的12個測試函數(shù)上獨立運行50次所得結果的平均值和標準差.

表5 7種算法求解12個測試函數(shù)結果的平均值和標準差(D=60)Table 5 Mean value and standard deviation of 7 algorithms for 12 test functions(D=60)

表6 7種算法求解12個測試函數(shù)結果的平均值和標準差(D=100)Table 6 Mean value and standard deviation of 7 algorithms for 12 test functions(D=100)

從表5和表6可看出,對于函數(shù)f1、f2、f3、f5、f7、f8、f9,無論是60維還是100維,IPSO-VP算法均能求得函數(shù)最優(yōu)解;f10、f11、f123個多峰函數(shù)的局部極小值個數(shù)會隨著變量維數(shù)的增加呈指數(shù)級增長[17],求解難度增大,但IPSO-VP算法對這3個函數(shù)的求解結果依然有很高的精度,且明顯優(yōu)于其他6個算法. IPSO-VP、MeanPSO、PHSPSO、TCSPSO算法在函數(shù)f6、f7、f8、f9上的求解結果相同,為進一步比較這4種算法優(yōu)劣,圖4給出了4種算法求解100維的4個多峰函數(shù)的適應度值變化曲線,可以看出IPSO-VP算法收斂速度更快.

圖4 4個測試函數(shù)的收斂曲線(100維)Fig.4 Convergence curves of four test functions(100 dimensions)

3.4 算法時間復雜度分析

標準PSO算法時間復雜度為O(nmD)[18],其中n為粒子數(shù),m為算法迭代次數(shù),D為問題維數(shù),本文IPSO-VP算法利用式(10)、(11)來更新粒子速度和位置,與標準PSO算法相比僅多一項自適應判定,因此,改進策略并未增加算法時間復雜度,本文算法時間復雜度仍為O(nmD).并且,由圖3收斂曲線可看出,在求解精度相同情況下,本文算法所需迭代次數(shù)更少. 綜上分析,當種群規(guī)模、問題維數(shù)和迭代次數(shù)相同時,本文算法的時間復雜度并未增加.

4 結論

本文提出一種改進粒子速度和位置更新公式的粒子群算法,算法中引入一種自適應粒子速度和位置更新策略,同時采用基于Logistic混沌的非線性慣性權重,實驗結果表明,改進算法具有較快的收斂速度和較高的尋優(yōu)精度,同時改進算法解決維數(shù)較高的多峰函數(shù)問題具有良好性能和潛在應用價值. 未來工作中,應用改進算法求解實際優(yōu)化問題是值得研究的內(nèi)容.