李二超,高振磊

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

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

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

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

1 相關(guān)工作

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

標(biāo)準(zhǔn)PSO算法中,粒子通過學(xué)習(xí)自身歷史經(jīng)驗(yàn)(pbest)與群體經(jīng)驗(yàn)(gbest)尋找最優(yōu)粒子. 對于求解變量為X={x1,x2,…,xD}、目標(biāo)函數(shù)為min{f(x)}的優(yōu)化問題,標(biāo)準(zhǔn)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是慣性權(quán)重,標(biāo)準(zhǔn)PSO算法中w隨迭代次數(shù)線性遞減;c1和c2為學(xué)習(xí)因子,通常取值為2;r1和r2是[0,1]均勻分布的隨機(jī)數(shù).

1.2 粒子速度更新公式的改進(jìn)

(3)

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

MeanPSO算法和PSO算法中粒子運(yùn)動(dòng)過程如圖1所示.

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

1.3 粒子位置更新公式的改進(jìn)

文獻(xiàn)[13]提出一種帶有平均維度信息的分層簡化粒子群優(yōu)化(PHSPSO)算法,PHSPSO算法舍棄PSO算法中粒子速度更新項(xiàng),并引入平均維度信息概念,即每個(gè)粒子所有維信息的平均值,計(jì)算公式為式(4). 同時(shí)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)有助于提升算法的收斂速度.在迭代過程中,算法基于概率選擇不同的模式來更新粒子位置.

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

(8)

(9)

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

2 改進(jìn)算法

2.1 粒子速度和位置自適應(yīng)更新策略

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

(10)

(11)

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

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

2.2 慣性權(quán)重的選取

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

混沌映射作為一種非線性映射,因其所產(chǎn)生的混沌序列具有良好隨機(jī)性和空間遍歷性,在進(jìn)化計(jì)算中得到廣泛應(yīng)用,其中Logistic映射應(yīng)用較為廣泛,它可以產(chǎn)生[0,1]之間的隨機(jī)數(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)生的隨機(jī)數(shù).慣性權(quán)重隨迭代次數(shù)的變化如圖2所示.

2.3 算法實(shí)現(xiàn)

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

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

步驟2 根據(jù)給定目標(biāo)函數(shù)計(jì)算所有粒子適應(yīng)度值;

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

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

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

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

3 仿真實(shí)驗(yàn)及結(jié)果分析

3.1 基本測試函數(shù)

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

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

續(xù)表1 Table 1 continued

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

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

3.3 與其他改進(jìn)PSO算法對比

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

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

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

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

續(xù)表4 Table 4 continued

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

分析表4和圖3可知改進(jìn)算法(IPSO-VP)在30維f1、f2、f3、f4、f55個(gè)單峰函數(shù)上,無論是求解精度、收斂速度還是穩(wěn)定性均優(yōu)于6個(gè)對比算法,且在函數(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個(gè)算法,雖然SL-PSO算法的求解精度與IPSO-VP算法相同,但從圖3收斂曲線可看出IPSO-VP算法收斂更快,約迭代100～200次之后就完成收斂.

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

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

表6 7種算法求解12個(gè)測試函數(shù)結(jié)果的平均值和標(biāo)準(zhǔn)差(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個(gè)多峰函數(shù)的局部極小值個(gè)數(shù)會(huì)隨著變量維數(shù)的增加呈指數(shù)級(jí)增長[17],求解難度增大,但I(xiàn)PSO-VP算法對這3個(gè)函數(shù)的求解結(jié)果依然有很高的精度,且明顯優(yōu)于其他6個(gè)算法. IPSO-VP、MeanPSO、PHSPSO、TCSPSO算法在函數(shù)f6、f7、f8、f9上的求解結(jié)果相同,為進(jìn)一步比較這4種算法優(yōu)劣,圖4給出了4種算法求解100維的4個(gè)多峰函數(shù)的適應(yīng)度值變化曲線,可以看出IPSO-VP算法收斂速度更快.

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

3.4 算法時(shí)間復(fù)雜度分析

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

4 結(jié)論

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