粒子群算法的邊界問題研究

方 田

（中冶華天工程技術(shù)有限公司，江蘇 南京210019）

0 引言

粒子群算法（Particle Swarm Optimization Algorithm），縮寫為PSO，是近年來發(fā)展起來的一種新的進(jìn)化算法。它是Kennedy和Eberhart受人工生命研究結(jié)果的啟發(fā)、通過模擬鳥群覓食過程中的遷徙和群聚行為而提出的一種基于群體智能的全局隨機搜索算法，1995年IEEE國際神經(jīng)網(wǎng)絡(luò)學(xué)術(shù)會議發(fā)表了題為Particle Swarm Optimization的論文，標(biāo)志著PSO算法誕生。[1]該算法具有很好的生物社會背景，對非線性、多峰問題均具有較強的全局搜索能力，在科學(xué)研究與工程實踐中得到了廣泛的關(guān)注和應(yīng)用。[2]

在粒子群算法的進(jìn)化計算過程中，經(jīng)常會遇到被搜索空間邊界約束的情況。邊界問題理論上并不會對粒子群算法的造成巨大的破壞，但在實際應(yīng)用中卻會造成計算資源的極大浪費。同時，在有限的進(jìn)化次數(shù)限制下，會對算法效果產(chǎn)生較大影響。

本文就粒子群算法的邊界問題進(jìn)行了研究和分析，并提出一些解決方案以供參考。

1 粒子群算法原理

粒子群算法最初是受到飛鳥集群活動的規(guī)律性啟發(fā)，進(jìn)而利用群體智能建立的一個簡化模型。其生物學(xué)模型主要源于生物學(xué)家Frank Heppner提出的鳥類棲息模型。[3]社會心理學(xué)研究成果揭示了社會性群體中的個體之間會發(fā)生信息交流，并產(chǎn)生趨同認(rèn)知。以鳥群為例，每只飛鳥之間會通過聲音或動作交流其個體的認(rèn)知信息，同時，獨立的飛鳥個體會趨向于跟隨群體的大方向飛行。這樣，每個個體就會在自身經(jīng)驗的基礎(chǔ)上，獲得了群體的經(jīng)驗知識，增加了覓食的成功率。如果將每只飛鳥作為一個智能計算體(agent)，將這樣的一組智能體作為族群，用計算機來模擬其覓食過程，就構(gòu)建了基本的粒子群算法思想，而所謂食物就是算法的目標(biāo)函數(shù)。這樣的基本粒子群算法也被稱之為鳥群算法。

在粒子群算法中，每個粒子都是一個智能體，具有以下幾個功能：

1）運動功能：能在計算空間中自由運動。

2）判斷功能：能判斷自身的適應(yīng)度。

3）記憶功能：能記憶自身的歷史經(jīng)驗。

4）交流功能：能和整個群體交流各自的經(jīng)歷。

這樣的粒子集合就構(gòu)成了粒子群，該粒子群是一個智能體的群落，同時具有個體不具備的群體智能。

基于以上思想，基本粒子群算法表述如下：

其中vij(t)代表第i個粒子在第t次進(jìn)化時的速度；xij(t)表示第i個粒子在第t次進(jìn)化時的位置；pbest,ij(t)是第i個粒子的個體歷史最佳值；gbest,j(t)是群體歷史最佳值；w是粒子運動的慣性因子；c1是自身記憶影響因子；c2是群體影響因子；r1j(t)，r2(t)是隨機因子；i是粒子序號；j是計算空間的維度序號。

2 邊界問題的產(chǎn)生和分析

由上一章節(jié)可以看到，基本粒子群算法兼顧了種群中每個粒子的慣性、自身經(jīng)驗和群體經(jīng)驗，在進(jìn)化計算過程中模擬了鳥群覓食的社會性群體機制，達(dá)到了全局搜索的目的。但是在實際應(yīng)用中，有一個情況不可忽略，那就是實際問題的搜索空間一般都是是有界的，也就是說群體是被限制在了一個封閉的空間中，單獨的個體并不能任意運動。當(dāng)單個個體突破了空間界限的限制，就會給算法結(jié)構(gòu)帶來破壞，造成以下一些問題：

1）適應(yīng)度函數(shù)失效：超出適應(yīng)度函數(shù)的定義域，導(dǎo)致判據(jù)失效，得到錯誤的結(jié)論。

2）解區(qū)間錯誤：在搜索空間之外，無法得到有效解。

3）計算資源浪費：在搜索空間之外不會得到有效經(jīng)驗，也不會對群體知識進(jìn)行改進(jìn)，這樣的計算完全是浪費。

4）延誤進(jìn)化進(jìn)程：粒子個體在走出限制空間之后，由于慣性原因，會在錯誤的空間產(chǎn)生滯留，嚴(yán)重影響算法收斂速度。

針對這樣一些問題，在算法上有必要增加一定的機制加以限制，使粒子的運動限制在搜索空間范圍內(nèi)，增加算法效率，改善優(yōu)化搜索效果。在實踐過程中，筆者發(fā)現(xiàn)可以采用以下一些方式對算法加以改進(jìn)：

1）增加搜索空間外的適應(yīng)度定義，可以將該區(qū)域的適應(yīng)度設(shè)為最小值。這樣，可以依靠粒子自身的智能回歸正確的空間。

2）當(dāng)粒子運動到空間邊界時，強制該粒子停止運動，當(dāng)前速度置為0，粒子的適應(yīng)度用當(dāng)前所處的邊界位置計算。

3）將空間邊界設(shè)置為反射面，當(dāng)粒子碰撞到空間邊界時，就產(chǎn)生反射作用，讓粒子根據(jù)一定的機制反彈回原空間，并保持一定的速度。

以上幾種方式從不同的的角度來處理粒子群算法的邊界問題，各有優(yōu)缺點。

增加適應(yīng)度定義的方法可以保持粒子群算法機制上的完善，充分發(fā)揮粒子的智能和自主性。但是這樣會犧牲一部分算法效率，也就是犧牲掉粒子自主糾錯的計算時間。強制粒子停止的方法可以最大化的節(jié)約邊界問題的錯誤糾正時間，但是，粒子一旦停止后，就會喪失原運動過程的慣性體系，影響種群的多樣性。讓粒子反射的方法可以杜絕邊界問題的產(chǎn)生，同時，也有利于保持種群多樣性。但是反射過程的運動計算在一定程度上增加了計算時間消耗。

3 結(jié)語

通過上述研究可知，粒子群算法是一種優(yōu)秀的群體智能優(yōu)化算法，它機理清晰，應(yīng)用廣泛。粒子群算法的邊界問題影響到算法的效率和最終結(jié)果，必須加以重視。在實際應(yīng)用中，采用適當(dāng)?shù)姆椒梢詫吔鐔栴}加以處理，使算法更加完善。

［1］Kennedy J,Eberhart R.Particle swarm optimization [C]//Proceedings of the 4th IEEEInternational Conference on Neural Networks.Piscataway:IEEEService Center,1995:1942-1948.

［2］Garnier S,Gautrais J,Theraulaz G.The biological principles of swarm intelligence[J].Swarm Intelligence,2007,30(1):3-31.

［3］Banks A,Vincent J,Anyakoha C.A review of particle swarm optimization.Part I:background and development[J].Natural Computing,2007,45(6):55-57.