對粒子群優化算法的改進及應用

摘要本文首先給出了粒子群優化算法(Particle Swarm Optimization，即PSO)的概念及算法原理，然后對分析了其研究現狀，并詳細闡述了其算法的改進及應用，最后將PSO與其他算法進行比較。

關鍵詞粒子群優化算法 PSO 群體 遺傳算法

中圖分類號:TP39文獻標識碼:A

0 緒論

在鳥群、魚群和人類社會的行為規律的啟發下，由Kennedy和Eberhart在1995年提出的一種基于群智能(Swarm Intelligence)的演化計算技術，即粒子群優化算法(Particle Swarm Optimization，即PSO)。粒子群優化算法的基本思想是群體模型，這個群體模型是模擬鳥類的群體行為得到的。

1 PSO算法原理

粒子群優化算法中，粒子群由個粒子組成，每個粒子的位置代表優化問題在D維搜索空間中潛在的解。根據各自的位置，每個粒子用一個速度來決定其飛行的方向和距離，然后通過優化函數計算出一個適應度函數值(fitness)。粒子是根據如下三條原則來更新自身的狀態:(1)在飛行過程中始終保持自身的慣性;(2)按自身的最優位置來改變狀態;(3)按群體的最優位置來改變狀態。

此算法是基于群體智能理論的優化算法的思想，群體中粒子具有記憶能力，它們相互合作與競爭，這樣會產生群體智能指導優化搜索方式，并在搜索過程中進行調整。

2 PSO算法研究現狀

PSO算法一經提出，就吸引了學術界眾多學者的廣泛重視，目前已經成為一個研究熱點，關于PSO算法應用研究的各種成果不斷涌現。專家研究此算法主要是因為其具有許多優點，如算法收斂速度快，設置參數少，使用的是高效的并行搜索算法等。其研究現狀包括兩方面:算法的改進和應用。

2.1 算法的改進

粒子群優化算法具有如下優點，如:(1)收斂速度快;(2)實現能力強;(3)易于理解;(4)使用過程中需要調整的只是少量參數，但自身也存在不足。如今，基本粒子群優化算法讓許多學者通過三種途徑做了各式各樣的改進，這三種途徑是:(1)使算法離散化;(2)提高收斂速度;(3)提高種群多樣性。

研究發現，要想提高收斂速度的問題，不是修改算法的結構，而是去需要修改PSO算法的速度更新方程。許多專家都在提高收斂速度的問題上進行了研究。比如:(1)Kennedy和Eberhart曾經提出過PSO算法，1998年Y. Shi與R. C. Eberhart首次在此版本的基礎上提出了將慣性權重引入到進化方程中，這樣可以改善其收斂性能，通過調節慣性權重是早期使用最多的提高收斂速度的辦法;(2)Clerc使用收縮因子來達到提高局部收斂速度的目的，這樣能夠確保算法的收斂性;(3)還有一種使用訪求來改進算法，即使用新的函數擴展技術，這樣可以提高PSO算法對復雜問題全局最優解的探測能力，改進后的算法能有效地提高PSO算法的全局收斂性能;(4)Angeline使用遺傳算法中的選擇操作，此種算法的優點是提高了收斂速度，缺點是搜索范圍的能力降低，即不能夠在大范圍內進行搜索，所以無法在全局范圍內搜索到最優解;(5)Lovbjerg提出了一種提高算法性能的方法:即把遺傳算法中的復制和再結合操作引入到算法中。還有其他的方法，比如在基本PSO進化過程中，自適應的變異算法能夠根據群體適應度方差和當前最優解的大小這兩個方面來確定當前最優粒子的變異概率，變異操作可以增強粒子優化算法跳出局部最優解的能力，同時也可避免早熟收斂的問題。

PSO算法作為一種新的隨機搜索算法，仍舊存在著如下缺點:早熟、收斂慢、導致尋優停滯。要解決這個問題，一些研究者提出了通過控制種群多樣性來提高算法性能的方法。主要從兩個方面進行|:一是分析出粒子和種群最優位置的距離，然后對種群進行隨機多代初始化，最后并給能夠減少算法早熟收斂性的不同策略;二是提高全局搜索性能，采用引入遺傳算法的變異操作。

上述各種措施能夠獲得更好的優化結果，特別是針對多模態和較復雜問題，優化效果更好，不好的是會影響到算法的局部收斂速度，使之降低。總歸來說，如果要想提高某種性能，當然，同時也會有其它副作用，需要找出某個問題的具體特點，然后根據領域知識對算法進行改進。

2.2 算法的應用

由于粒子群優化算法有著深刻的智能背景，所以應用的領域非常廣泛，比如目前已經廣泛應用于函數優化、工程技術、神經網絡訓練，人工智能以及其它遺傳算法的應用領域。

PSO算法最早應用于人工神經網絡的訓練問題，最直接應用于多元函數優化方面。應用在神經網絡方面主要指這兩個方面:一是演化神經網絡的權值;二是神經網絡的結構;應用于多元函數優化方面主要包括帶約束的優化問題，多目標優化問題、最大最小值問題。已有的研究成果表明，PSO算法在早期的應用方面，即優化神經網絡方面有很大的潛力，而在第二個應用方面，得到的最優值則不一定是很精確的，這是因為假如所討論的函數受到嚴重的噪音干擾會呈現出非常不規則的形狀。

科學與工程問題，實際上就是函數優化問題，如果不是，則可以將之轉換為此問題進行求解。遺傳算(下轉第102頁)(上接第93頁)法有一個專門的用途即用來解決函數優化問題。函數問題中存在一些復雜函數問題，比如超高維和多局部極值的函數，遺傳算法卻往往不能達到期望的要求，因為收斂速度慢，精度低。大量的實驗研究發現，粒子群優化算法在解決一些典型的函數優化問題時，在優化方面能夠取得比遺傳算法更好的結果。PSO算法與遺傳算法比較類似，應用PSO算法來解決優化問題時，需要兩個重要步驟:第一步是對問題解進行編碼，第二步是選擇適應度函數。應用PSO算法有其優點，比如，首先可以簡化這兩個步驟，其次在進行函數優化時可以避免選擇、交叉、變異等進化操作。實驗證明，對于大多數的非線性函數，PSO算法在優化速度和精度上與遺傳算法相比較均有一定的改善。

模式分類是PSO算法的一個應用方面。其應用的過程是，首先是將訓練模糊前向神經網絡進行模式分類，使用的算法是PSO算法，然后從網絡的輸出中抽取規則，進而取得滿意的效果。對于數據的聚類， DW van der Merwe和AP Enfelbredht已經把粒子群優化算法應用于此方面進行研究，然后通過與-均值聚類算法進行比較，進而得出結論:PSO算法在聚類方面有更大的潛力。

此外，PSO算法在集成電路設計、系統辨識、狀態估計等問題的應用也均有報道。粒子群優化算法的研究剛剛起步，算法的應用還比較少，因此開拓更多新的應用領域是一項很有意義的工作。

3 PSO算法與其他算法比較

“種群”表示一組解空間中的個體集合，在粒子群優化算法和其它進化算法都通用。以遺傳算法為例進行比較，相同點:(1)都對種群進行隨機初始化;(2)都使用適應度函數來評價系統，并進行隨機搜索;(3)往往均會遇到早熟收斂和收斂性能差的缺點;(4)都不能保證收斂到最優點。不同點:(1)PSO算法具有獨特的信息共享機制;(2)遺傳算法中的種群是比較均勻的向最優區域移動，是因為染色體之間互相共享信息，而PSO算法則是單向的信息共享機制，因為粒子是搜索到的最優點后才進行共享信息的;(3)PSO算法的所有粒子收斂于最優解的速度更快。

PSO算法與其它進化算法也有相同點:在進化過程中都保留和利用位置信息。重要的不同點在于PSO算法還保留和利用速度信息。

從以上分析中看出，PSO算法與其它進化算法有相似之處，也有不同之處，各有優缺點。PSO算法具備以下獨特的特性:(1)此算法能夠將粒子的位置模型化;(2)能夠將粒子的速度模型化;(3)此算法能同時將以上兩者模型化;(4)能夠給出進化方程;(5)算法原理更簡單、參數更少、實現更容易，原因是粒子的更新只是通過內部速度來進行的。

4 結論

粒子群優化算法原理簡單，應用范圍極其廣泛，并且其算法與其它算法相比來說，具備一些獨特的特性。可進一步考慮如何將此算法應用于數據挖掘等其它多個領域，也可以考慮能否將此算法與其它算法結合起來用在某個領域。

參考文獻

[1]Jiawei Han，Micheline Kamber.數據挖掘——概念與技術.范明，孟小峰等，譯.北京:機械工業出版社，2001:185-217.

[2]沈艷，郭兵，古天祥.粒子群算法及其與遺傳算法的比較.電子科技大學學報，2005.34(5):72-75.

[3]任斌，豐鎮平.改進遺傳算法與粒子群優化算法及其對比分析.南京師范大學學報，2002.2(2):73-76.