粒子群算法概述

【摘要】介紹了基本粒子群算法的原理和流程，歸納了離散粒子群優化算法的研究現狀和改進，包括改進的二值離散粒子群優化算法、離散量子粒子群優化算法、模糊離散粒子群優化算法，簡要分析了粒子群算法在各個領域的應用。

【關鍵詞】粒子群算法 群體智能 應用

【中圖分類號】O411.1 【文獻標識碼】A 【文章編號】1009-8585(2011)06-00-02

1 基本粒子群算法介紹

1995年美國電氣工程師Eberhart和社會心理學家Kennedy 基于鳥群覓食行為提出了粒子群優化算(partical swarm optimization，PSO)，簡稱粒子群算法。

1.1 基本粒子群算法的原理

粒子群優化算法中，每個優化問題的潛在解都是搜索空間中的一只鳥，稱之為“粒子”。每個粒子的位置代表被優化問題在搜索空間中的潛在解。例如，在一個D維的目標搜索空間中，每個粒子看成是空間內的一個點。設群體由m個粒子構成，m也被稱為群體規模。所有的粒子都有一個由被優化的函數決定的適應值(Fitness value)，每個粒子還有一個速度決定他們飛翔的方向和距離。粒子們追隨當前的最優粒子在解空間中搜索。PSO初始化為一群隨機粒子(隨機解)，然后通過迭代找到最優解。在每一次迭代中，粒子通過跟蹤兩個“極值”來更新自己。一個是粒子本身所找到的最優解，稱為個體極值;另一個極值是整個種群目前找到的最優解，稱為全局極值。

假設在一個D維的目標搜索空間中，有m個粒子組成一個群落，其中第i個粒子表示為一個D維的向量

即第i個粒子在D維的搜索空間中的位置。將Xi代入一個目標函數就可以計算出其適應值，根據其適應值的大小衡量的優劣。第i個粒子的“飛行”速度也是一個D維的向量，記為;第i個粒子迄今為止搜索到的最優位置稱為個體極值，記為

整個粒子群迄今為止搜索到的最優位置為全局極值，記為

在每次迭代中，粒子根據以下式子更新速度和位置:

其中，是迭代數，r1和r2為[0，1]之間的隨機數，這兩個參數是用來保持群體的多樣性。c1也c2為學習因子，也稱加速因子，其使粒子具有自我總結和向群體中優秀個體學習的能力，從而向自己的歷史最優點(個體極值)和群體內歷史最優點(全局極值)靠近。

為了改善基本粒子群算法的收斂性能，Shi和Eberhart在1998年的IEEE國際進化計算學術會議上發表了題為“A modified particle swarm optimizer”的論文，引入了慣性權重，逐漸地大家都默認這個改進粒子群算法為標準的粒子群算法。

在標準的粒子群算法中，Shi和Eberhart添加了一個慣性權重到速度更新公式，而位置更新公式與基本粒子群算法的位置更新公式相同。即

1.2 基本粒子群算法的流程

1)初始化粒子群，即隨機設定各粒子的初始位置x和初始速度v;

2)計算每個粒子的適應度值;

3)對每個粒子，比較它的適應度值和它經歷的最好位置的適應度值;若更好，更新;

4)對每個粒子，比較它的適應度值和群體所經歷的最好位置的適應度值;若更好，更新;

5)根據位置和速度的更新公式調整粒子的位置和速度;

6)若達到結束條件(足夠好的位置或最大迭代次數)，結束;否則，轉步驟2。

2 離散離子群算法介紹

2.1 二進制離散粒子群優化算法

由于基本粒子群優化算法主要針對連續函數進行搜索運算，但許多實際工程問題都描述為離散的組合優化問題。傳統粒子群優化算法局限于速度-位移更新算子，不能有效拓展到離散及組合優化領域。為此Kennedy和Eberhart于1997年提出了一種二進制離散粒子群優化算法。

二進制離散粒子群優化算法中，每個粒子的位置使用二進制編碼，粒子的速度定義為“粒子位置改變的概率”。這里的概率是指每一位取一個狀態或另一狀態的可能性。這時，粒子群算法離散二進制模型的粒子的速度公式為:

vid = vid＋c1r1(pid－xid)＋c2r2(pgd－xid)

其中，pid和xid在整數集{0，1}內取值，vid的值表示為概率形式，限制在[0.0，1.0]內取值，r1、r2是0～1之間的隨機數。

相應地，粒子位置的更新規則如下:

其中，是(0，1)區間上均勻分布的隨機變量;，用來限制速度。

為了將粒子群算法離散化，文獻[5]重新給出算法由當前的狀態變量決定粒子將被判定為1或0的概率，即有:

Kennedy等提出使用Sigmoid函數求參數s。Sigmoid函數是神經網絡中常用的一種模糊函數，其表達式如式(2.2)所示:

當取得時，閾值s的取值范圍在[0.0025，0.9975]。修改后的離散粒子群優化算法與基本粒子群優化算法流程相類似，但粒子速度和位置的更新公式修改為:

其中，是[0，1]之間的隨機數，算法中其他參數都和基本粒子群優化算法的參數相同。

2.2 改進的二值離散粒子群優化算法

基本的二進制離散粒子群算法同基本粒子群優化算法類似，都會由于粒子在運動過程中產生惰性而發生早熟收斂。為解決這一問題，楊紅孺等于2005年基于基本二進制離散粒子群優化算法，提出了改進的二值離散粒子群優化算法。新算法利用基本粒子群算法中“粒子依賴自身經驗及粒子群全體經驗，同時克服自身飛行惰性”的思想，改進了粒子的更新運動公式，并將離散的二值由0、1改為—1、1。

2.3 離散量子粒子群優化算法

Yang S.Wang等人于2004年提出離散量子粒子群優化算法(quantum discrete PSO)，是量子粒子群優化算法在離散問題上的改進算法。算法將量子粒子群算法中的粒子離散化，成為離散的粒子矢量。

2.4 模糊離散粒子群優化算法

為解決旅行商問題，陳震亦于2004年提出了一種新型的模糊自適應粒子群優化算法，龐巍等于2005年提出了模糊離散粒子群優化算法。算法使用模糊矩陣表示粒子位置和速度，迭代過程中加入歸一化和解模糊化運算。

3 粒子群算法的應用介紹

粒子群優化算法(Particle Swarm Optimization，簡稱PSO)是一類基于群體智能(Swarm Intelligence)的隨機優化算法。粒子群優化算法自從提出之后，由于其概念簡單、實現方便，同時又有深刻的智能背景，立刻引起了優化及演化計算等領域的學者們的廣泛關注，在短期內迅速得到了國際演化計算研究領域的認可，并且由于其在解決復雜的組合優化問題方面所具有的優越性能，因而特別適合工程應用與優化。粒子群算法已被廣泛地應用于函數優化、優化問題求解、工程設計優化領域、電力系統領域、機器人控制領域、交通運輸領域、通信領域、計算機領域、工業生產優化領域、生物醫學領域和電磁學領域 。

a)在優化問題求解方面，粒子群算法已被有效應用于約束優化問題求解(最小最大化問題)、多目標優化問題求解、整數規劃問題、旅行商問題求解等。

b)在工程設計與優化方面，粒子群算法被用于神經網絡進化、模糊神經元網絡過則的提取、電路設計、數字濾波器設計、布局優化、半導體器件綜合、控制器參數優化、系統模式與狀態估計等。

c)在電力系統領域。粒子群算法被用于實現電能優化、電壓控制、提高電站可靠性以及電容其優化配置問題等。在機器人控制領域中，粒子群算法被用于機器人振動抑制軌跡規劃以及移動機器人路徑規劃等。

d)在交通運輸領域，粒子群算法被用于解決車輛路徑問題以及交通控制問題。在通信領域，粒子群算法被用于解決路由選擇及移動通信基站布置與優化問題等。

e)在計算機領域，粒子群算法被用于任務分配、模式識別、圖像處理及數據挖掘等問題。

f)在工業生產領域，粒子群算法被應用于原料混合優化和計算機控制研磨優化等問題。

g)在生物醫學領域，粒子群算法被用于生物醫學圖像配準或圖像數據的幾何排列、基因分類等問題。

h)在電磁學領域，粒子群算法被應用與求解非線性磁介質磁場、電磁場中的多層平面屏蔽罩優化、原聲場旁瓣槽相控陣列綜合問題等。

粒子群算法概念簡單，具有很強的發現較好解的能力，并不容易陷入局部最優。PSO算法的應用十分廣泛，有著較好的發展前景。目前為了進一步完善粒子群算法已經提出了很多改進方法，但由于實際問題的多樣性和復雜性，這些PSO算法不具有通用性，或者參數的設置要求使用者具備較高的經驗，否則難以達到理想的效果，因此還有問題值得做進一步的研究。而開拓PSO算法的新的應用領域也是一項很有意義的工作。

參考文獻

[1] Eberhart R C，and Kennedy J.A new optimizer using particles swarm theory，Proc.SixthInternational Symposium on Micro Machine and Human Science，Nagoya，Japan，IEEE Service Center，Piscataway，NJ，1995:39-43.

[2] Kennedy J，Eberhart R C.Particle Swarm optimization.Proceedings of IEEE International Conference on Neural Networks Vol.IV，pp.1942-1948.IEEE service center，Piscataway，NJ，1995.

[3] Shi Y. Eberhart R C. A Modified Particle Swarm Optimizer.In IEEE International conference of、Evolutionary Computation. Anchorage.Alaska.1998:69-73.

[4] Kennedy J.Eberhart R.C.A discrete binary version of the particle swarm algorithm.IEEE Press，1997:4104-4109.

[5] 楊紅孺，高洪元，龐偉正等.基于離散粒子群優化算法的多用戶檢測器.哈爾濱工業大學學報.2005.37(9):1303-1306.

[6] Yang S.Wang M.Jiao L.A quantum particle swarm optimization.Proceeding of the 2004 IEEE Congress on Evolutionary Computation.2004.1:320-324.

[7] 陳震亦.粒子群優化算法研究及其在TSP問題中的應用[D].碩士學位論文.福州大學.2004.

[8] 龐巍，王康平，周春光等.模糊離散粒子群優化算法求解旅行商問題.小型微型計算機系統.2005.26(8):1331-1334.

[9] 紀震，廖惠連，吳青華.粒子群算法及應用[M].北京科學出版社.2009.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文