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

方 田

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

0 引言

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

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

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

1 粒子群算法原理

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

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

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

2）判斷功能：能判斷自身的適應度。

3）記憶功能：能記憶自身的歷史經驗。

4）交流功能：能和整個群體交流各自的經歷。

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

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

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

2 邊界問題的產生和分析

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

1）適應度函數失效：超出適應度函數的定義域，導致判據失效，得到錯誤的結論。

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

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

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

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

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

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

3）將空間邊界設置為反射面，當粒子碰撞到空間邊界時，就產生反射作用，讓粒子根據一定的機制反彈回原空間，并保持一定的速度。

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

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

3 結語

通過上述研究可知，粒子群算法是一種優秀的群體智能優化算法，它機理清晰，應用廣泛。粒子群算法的邊界問題影響到算法的效率和最終結果，必須加以重視。在實際應用中，采用適當的方法可以對邊界問題加以處理，使算法更加完善。

［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.