基于信息微傳遞機制的粒子群算法

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

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

0 引 言

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

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

1 標準粒子群算法

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

(1)

(2)

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

2.1 信息微傳遞機制

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

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

(3)

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

(4)

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

圖1 信息微傳遞機制

2.2 逃離策略

(5)

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

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

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

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

(6)

BLd=max(rand·xd,LBd)

(7)

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

2.4 實現(xiàn)步驟

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

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

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

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

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

3 實驗結果與分析

3.1 實驗設置

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

表1 基準測試函數(shù)

3.2 實驗結果及分析

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

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

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

表2(續(xù))

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

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

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

4 結束語

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