閆 李，李國森，瞿博陽，馬佳慧

(中原工學(xué)院 電子信息學(xué)院，河南 鄭州 450007)

0 引 言

為提高粒子群算法(PSO)[1-5]的尋優(yōu)性能，研究人員提出許多解決方案。張新明等[6]將趨優(yōu)算子與萊維飛行(levy flight)策略引入粒子群算法，以平衡算法的全局和局部尋優(yōu)能力。Aydilek[7]融合螢火蟲算法提出了螢火蟲-粒子群混合算法，以避免早熟收斂。Elsayed等[8]在算法中采用交叉操作和參數(shù)自適應(yīng)機(jī)制，以提高解的多樣性。袁小平等[9]引入社會(huì)學(xué)習(xí)策略以提升PSO的全局搜索能力，并采用Levy Flight策略使種群擺脫局部最優(yōu)陷阱。

盡管上述研究在一定程度上提高了標(biāo)準(zhǔn)PSO算法的尋優(yōu)性能，但PSO算法進(jìn)化后期收斂速度慢、尋優(yōu)精度低等不足仍需要進(jìn)一步深入研究。因此，本文提出基于信息微傳遞機(jī)制的粒子群算法(IMPSO)，該算法具有以下3個(gè)方面的特點(diǎn)：①采用信息微傳遞機(jī)制，提高種群的多樣性；②引入逃離策略，防止種群陷入局部最優(yōu)；③設(shè)計(jì)了一種動(dòng)態(tài)邊界化策略，提高算法搜索效率。最后，本文選取具有不同特性的測(cè)試函數(shù)在6種算法上進(jìn)行性能對(duì)比以驗(yàn)證IMPSO算法的有效性。

1 標(biāo)準(zhǔn)粒子群算法

假設(shè)MaxIter表示算法最大迭代次數(shù)，種群規(guī)模為NP，搜索空間維度為D。第i個(gè)粒子的位置表示為xi=(xi1,xi2,…xiD)，其速度表示為vi=(vi1,vi2,…viD),標(biāo)準(zhǔn)PSO算法通過其個(gè)體歷史最優(yōu)值pbesti=(pbesti1,pbesti2，…，pbestiD)和全局最優(yōu)值gbesti=(gbesti1,gbesti2，…，gbestiD)對(duì)個(gè)體進(jìn)行迭代更新[10,11]。其位置和速度更新定義如下

(1)

(2)

2 基于信息微傳遞機(jī)制的粒子群算法

2.1 信息微傳遞機(jī)制

標(biāo)準(zhǔn)PSO在整個(gè)進(jìn)化過程中所有粒子個(gè)體跟隨全局最優(yōu)解進(jìn)行搜索，增加了收斂到最優(yōu)解的速度，同時(shí)會(huì)導(dǎo)致早熟收斂問題[12]。本文提出信息微傳遞機(jī)制，利用適應(yīng)度值對(duì)種群分組，每一組由若干層組成，逐層傳遞最優(yōu)信息實(shí)現(xiàn)種群進(jìn)化。具體步驟如下：

(2)信息逐層傳遞：在種群進(jìn)化過程中，第一層粒子集體學(xué)習(xí)種群全局最優(yōu)信息gbest，而第n層(n>1)每個(gè)粒子分別學(xué)習(xí)第n-1層相應(yīng)粒子的個(gè)體歷史最優(yōu)信息pbest，有利于減緩信息傳播的速度。另外，根據(jù)適應(yīng)度值調(diào)整粒子速度的變化大小，個(gè)體適應(yīng)度值越大，產(chǎn)生的速度越小，有利于減緩收斂。反之，產(chǎn)生較大的速度避免局部最優(yōu)。因此，第一層粒子速度更新如下

(3)

其余層粒子的速度更新如下

(4)

其中，fitness(i)是第i個(gè)粒子適應(yīng)度值。ε為極小的正常數(shù)，避免分母為零。另外，引入rand2啟發(fā)于文獻(xiàn)[13]，可以改善算法收斂速度[13]。以圖1為例說明信息傳遞過程，每個(gè)粒子給予一個(gè)編號(hào)。按照式(3)、式(4)，13號(hào)粒子將會(huì)學(xué)習(xí)9號(hào)粒子的pbest。同理，9號(hào)粒子和5號(hào)粒子將分別學(xué)習(xí)5號(hào)粒子和1號(hào)粒子的pbest，而1號(hào)粒子直接學(xué)習(xí)全局最優(yōu)gbest。最終實(shí)現(xiàn)了13號(hào)-9號(hào)-5號(hào)-1號(hào)粒子的信息傳遞和學(xué)習(xí)。

圖1 信息微傳遞機(jī)制

2.2 逃離策略

(5)

其中，dxi表示第i個(gè)粒子與種群中適應(yīng)度值最差粒子的歐氏距離，Dx表示所有粒子離適應(yīng)度值最差粒子的最大歐氏距離，計(jì)算為Dx=max{dxj|j=1,2,…,NP}，w(t) 表示種群中適應(yīng)度最差的粒子。一方面，粒子不受全局最優(yōu)引導(dǎo)，根據(jù)最差解產(chǎn)生新的進(jìn)化方向，避免粒子的趨同性；另一方面，根據(jù)與最差粒子的距離自適應(yīng)更新速度，當(dāng)距離最差粒子近時(shí)，產(chǎn)生較大的速度以遠(yuǎn)離最差解。

2.3 動(dòng)態(tài)邊界化策略

標(biāo)準(zhǔn)粒子群算法在整個(gè)搜索空間中尋優(yōu)，搜索空間不隨進(jìn)化過程而改變，增加了粒子尋優(yōu)的盲目性和工作量[15]。為了提高尋優(yōu)速度和搜索效率，本文采用動(dòng)態(tài)邊界化策略，每組的邊界范圍均不相同，主要思想是依據(jù)組內(nèi)最優(yōu)粒子x產(chǎn)生一個(gè)動(dòng)態(tài)搜索邊界范圍[BL,BU]以防止組內(nèi)粒子的位置超出界限。假設(shè)整個(gè)搜索空間邊界為[LB,UB]D。在d維，上邊界BUd和下邊界BLd計(jì)算如下

BUd= min(2·rand·xd,UBd)

(6)

BLd=max(rand·xd,LBd)

(7)

其中，UBd和LBd表示搜索邊界UB和LB的第d維。從公式可以看出，以獲得的最優(yōu)信息x為中心，產(chǎn)生一個(gè)縮小的矩形尋優(yōu)區(qū)域，使得粒子較好地向區(qū)域內(nèi)最優(yōu)解逼近。通過動(dòng)態(tài)地縮小搜索范圍，忽略適應(yīng)度較大且不相關(guān)的區(qū)域，達(dá)到高效尋優(yōu)的目的。

2.4 實(shí)現(xiàn)步驟

步驟1設(shè)置算法參數(shù)以及初始化種群。

步驟2采用信息微傳遞機(jī)制。依據(jù)粒子適應(yīng)度和種群平均適應(yīng)值計(jì)算劃分的組數(shù)φ，并將整個(gè)種群適應(yīng)度值按升序排列進(jìn)行分組分層。如果粒子屬于第一層，則按照式(3)更新速度；否則按照式(4)進(jìn)行更新。

步驟3判斷是否采用逃離策略。計(jì)算種群平均速度vavg，如果當(dāng)前粒子的速度小于vavg，則按照式(5)更新粒子速度。

步驟4依據(jù)式(2)更新粒子位置。采用動(dòng)態(tài)邊界化策略，即根據(jù)每組內(nèi)適應(yīng)度最優(yōu)粒子x，通過式(6)、式(7)計(jì)算其組內(nèi)搜索邊界。若位置超過該邊界，則置為邊界值。

步驟5若未達(dá)到最大迭代次數(shù)MaxIter，則將所有組個(gè)體重新組成一個(gè)種群，以實(shí)現(xiàn)各個(gè)組之間信息的交流，并轉(zhuǎn)至步驟2，否則輸出結(jié)果。

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

3.1 實(shí)驗(yàn)設(shè)置

為了驗(yàn)證本文提出的IMPSO算法的性能，實(shí)驗(yàn)選用10個(gè)經(jīng)典測(cè)試函數(shù)[13,17]。函數(shù)表達(dá)式和搜索區(qū)間見表1。f1～f5是單峰函數(shù)；f6～f10是多峰函數(shù)，存在多個(gè)局部極值。所選測(cè)試函數(shù)具有不同的優(yōu)化難度，可以有效評(píng)估算法的收斂速度、尋優(yōu)精度等性能。將IMPSO算法與HSPSO算法[7]、RDPSO算法[8]、ESPSO算法[18]、BLPSO算法[19]、CHPSO算法[20]和基本PSO算法[21]進(jìn)行對(duì)比。IMPSO算法參數(shù)設(shè)置：學(xué)習(xí)因子c=2，慣性權(quán)重w=0.7298。所有算法的種群大小NP為50，獨(dú)立實(shí)驗(yàn)次數(shù)為30。所有實(shí)驗(yàn)在Matlab2016b版本下運(yùn)行，運(yùn)行環(huán)境為Intel Core i3-6100CPU, 3.7 GHz, 4 G內(nèi)存。

表1 基準(zhǔn)測(cè)試函數(shù)

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

3.2.1 固定迭代次數(shù)的性能分析

實(shí)驗(yàn)參數(shù)設(shè)置如下：所有算法最大迭代次數(shù)MaxIter=100，測(cè)試函數(shù)維度D分別取50和100。采用最優(yōu)值、平均值、最差值和標(biāo)準(zhǔn)差作為指標(biāo)進(jìn)行對(duì)比。實(shí)驗(yàn)結(jié)果見表2。從表2中可以看出，在單峰函數(shù)f1～f5中，IMPSO算法的最優(yōu)值、平均值、最差值都優(yōu)于其它6種算法，均能收斂到最優(yōu)解。對(duì)于復(fù)雜的多峰函數(shù)f6～f10，IMPSO算法均成功跳出局部最優(yōu)，且得到的解精度很高，尤其在函數(shù)f6、f8、f10上找到了理論最優(yōu)值。而其它算法一定程度上陷入了早熟收斂。當(dāng)函數(shù)維度由50維變成100維，IMPSO算法仍可以找到相應(yīng)函數(shù)的最優(yōu)解。另外，通過對(duì)比所有算法在測(cè)試函數(shù)上的標(biāo)準(zhǔn)差，IMPSO算法得到的標(biāo)準(zhǔn)差明顯較小?？梢员砻?，對(duì)于單峰函數(shù)和多峰函數(shù)，IMPSO 在尋優(yōu)精度和算法穩(wěn)定性上表現(xiàn)良好，總體上優(yōu)于比較的算法?？梢?，采用信息微傳遞機(jī)制可以避免算法過早陷入局部最優(yōu)，利用逃離策略提高了種群多樣性，引入動(dòng)態(tài)邊界化策略加快了尋優(yōu)效率和搜索精度，從而算法得到的結(jié)果更接近理論最優(yōu)值。圖2給出算法在維數(shù)D=50下的4個(gè)測(cè)試函數(shù)(f1、f3、f5、f7)的收斂曲線。從圖1中可以直觀地看到，在進(jìn)化初期，IMPSO算法的曲線下降更快，比其它6種算法顯示出更較好的尋優(yōu)能力，說明IMPSO算法收斂速度更快。在進(jìn)化中后期，其它6種算法均不同程度的陷入早熟收斂，出現(xiàn)陷入局部最優(yōu)的現(xiàn)象，而IMPSO算法有效避免了該現(xiàn)象，且快速尋找到最優(yōu)解，表現(xiàn)出更好的收斂速度和尋優(yōu)性能。以上結(jié)果表明，IMPSO 算法具有更好的收斂速度。因此，IMPSO算法在尋優(yōu)精度、穩(wěn)定性和收斂速度方面表現(xiàn)良好。

表2 算法在固定迭代次數(shù)下在50維和100維的測(cè)試結(jié)果

表2(續(xù))

圖2 函數(shù)進(jìn)化曲線

3.2.2 固定收斂精度的性能分析

表3 固定精度下的最小、平均和最大收斂代數(shù)及成功率對(duì)比

4 結(jié)束語

針對(duì)粒子群算法易陷入局部最優(yōu)，并導(dǎo)致算法收斂速度慢、尋優(yōu)精度不高的不足，提出了基于信息微傳遞機(jī)制的粒子群算法(IMPSO)。該算法采用信息微傳遞機(jī)制使整個(gè)種群分組分層尋優(yōu)，增強(qiáng)種群多樣性，避免算法早熟；利用逃離策略通過遠(yuǎn)離最差解促使趨同性的粒子改變飛行方向，提高全局勘探能力，防止陷入局部最優(yōu)；使用動(dòng)態(tài)邊界化策略縮小粒子的搜索區(qū)域，增加算法尋優(yōu)的效率。實(shí)驗(yàn)結(jié)果表明，IMPSO相比于其它所對(duì)比的PSO改進(jìn)算法，具有更快的收斂速度和更高的尋優(yōu)精度。下一步工作中，將嘗試使用IMPSO算法解決實(shí)際工程問題。