微粒群算法研究狀況和發展

[摘要] 作為一種新興的自然計算方法， 微粒群（PSO）算法已成為新的研究熱點，它與人工生命，特別是進化策略和遺傳算法有著極為特殊的聯系，已完成的理論和應用研究證明微粒群算法是一種能夠有效解決大多數全局優化問題的新方法。更為重要的是， 微粒群算法的潛在并行性和分布式特點為處理大量的以數據庫形式存在的數據提供了技術保證。 本文介紹了微粒群算法理論的產生和發展過程，分析和介紹了微粒群算法的基本原理以及研究現狀。

[關鍵詞] 微粒群算法 群智能 優化算法

一、引言

近年來，自然啟發的算法越來越引起人們的重視，通過對自然界的觀察，從自然現象尤其是生命現象中人們得到靈感，提出了一些新的求解問題的方法。在這些新的算法中，比較突出的有微粒群算法和蟻群算法，它們又被稱為群智能算法。

1995 年，美國的James Kenney 和Russell Eberhart最早提出了微粒群算法。微粒群算法最初源于對簡單社會系統，如鳥群覓食和魚群行為的模擬，后來在研究中發現它是一種很好的優化工具。PSO方法能夠被用于解決大多數優化問題或者能夠轉化為優化求解的問題。 PSO最早應用于人工神經網絡的訓練方法，現在其應用領域已擴展到多目標優化、數據分類、數據聚類、模式識別、路由計算、生物系統建模、流程規劃、信號處理、機器人控制、決策支持以及仿真和系統辯識等方面，PSO理論和方法為解決這類應用問題提供了新的途徑。

二、PSO算法原理

James Kenney 和Russell Eberhart提出的PSO 基本模型同遺傳算法類似，是一種基于迭代的優化工具。微粒群算法又被認為是一種演化算法（EA）。和其他演化算法相似，也是根據對環境的適應度將群體中的個體移動到好的區域， 不同之處在于它不像其他演化算法一樣對個體使用演化算子，而將每個個體看作是d 維搜索空間中的一個沒有體積沒有質量的微粒，在搜索空間中以一定的速度飛行，并根據對個體和集體的飛行經驗的綜合分析來動態調整這個速度。

在PSO 算法中，用粒子的位置表示待優化問題的解，每個粒子性能的優劣程度取決于待優化問題目標函數確定的適應值，每個粒子由一個速度矢量決定其飛行方向和速率大小。設在一個d維的目標搜索空間中，群體中的第i個微粒可表示為一個d維矢量，Xi=(xi1，xi2，…，xid，)T，微粒i的速度(位置的改變)用矢量Vi =(vi1，vi2，…，vid，)T 表示。第i個微粒前面所過的最佳位置用Pi=(pi1，pi2，…，pid，)T表示。令g為群中最好的微粒，并用上標表示迭代次數，則微粒群的處理按下面兩個公式處理：

式中ω為慣性權重，ω取大值可使算法具有較強的全局搜索能力，ω取小值則算法傾向于局部搜索。式中第1 部分可理解為粒子先前的速度或慣性;第2 部份可理解為粒子的“認知”行為，表示粒子本身的思考能力;第3 部分可理解為粒子的“社會”行為，表示粒子之間的信息共享與相互合作。

在算法實現過程中沒有交叉變異操作，而是以粒子對解空間中最優粒子的追隨進行解空間的搜索。

同遺傳算法相比，PSO的優點在于流程簡單易實現，算法參數簡潔，無需復雜的調整。因此從出現至今，PSO被迅速地應用于函數優化、神經網絡訓練、模糊系統控制、數據聚類、彈道辨識、CDMA多用戶檢測以及原有的一些遺傳算法應用領域。

James Kennedy 和Rui Mendes 引入鄰域拓撲的概念來調整鄰域的動態選擇，系統地分析了不同的種群拓撲結構時對PSO 算法效能的影響，如:影響種群結構的節點連接方式、節點聚合問題、節點間最短平均距離，以及拓撲結構與具體優化問題的相關性等問題，以說明構造種群結構的基本原則。這為具體優化問題的PSO 算法種群結構調整提供了理論基礎。

三、PSO算法特點

與大多數基于梯度應用優化算法不同，PSO是一種概率搜索算法。 雖然概率搜索算法通常要采用較多評價函數，但與梯度方法及傳統的演化算法相比，其優點還是顯著的:

1.魯棒性好。由于無集中控制約束，不會因個別個體的故障影響整個問題的求解。

2.具備分布式的特征。可方便應用分布式算法模型，及利用多處理器并行計算。

3.應用面廣。對問題定義的連續性無特殊要求。

4.以非直接的信息交流方式確保了系統的擴展性。

5.算法實現簡單。

PSO方法易于實現，算法中僅涉及各種基本數學操作，其數據處理過程對CPU 和內存的要求也不高。 且這種方法只需目標函數的輸出值，而無需其梯度信息。 已完成的PSO理論和應用方法研究證明PSO方法是一種能夠有效解決大多數全局優化問題的新方法。 更重要的是，PSO潛在的并行性和分布式特點為處理大量的數據的問題提供了技術保證。

在最初的公式中并沒有慣性權重ω，YuShi Hui 和Russell Eberhart 首次提出了慣性權重ω的概念，并對基本算法中的粒子速度更新公式進行了修正，如式(1)所示，以獲得更佳的全局優化效果。此公式后被廣泛接受并使用。

PSO 算法與其他計算智能方法的一個顯著區別就是所需調整的參數很少，但是這些關鍵參數的設置對算法的精度和效率卻存在顯著影響。 針對算法中的種群規模、迭代次數和粒子速度的選擇方法進行詳細分析，利用統計實驗方法對約束優化問題的求解論證了這三個參數對算法性能的基本影響，并給出了具有一定通用性的三種參數選擇原則。

四、PSO算法改進和發展

微粒群算法作為一種新穎的優化搜索算法，從其出現至今的十余年時間里，研究者們的大部分精力主要集中于對其算法結構和性能的改善方面的研究，主要包括:參數設置、粒子多樣性、種群結構和算法融合。

自身的改進：研究者們發現，控制種群多樣性是保證收斂的全局性的有效手段，可提高算法總體性能，是PSO算法的研究重點。

J.Riget 和J.SVesterstrom設計了一種ARPSO（Attractive and Repusive PSO）算法，它以基本PSO 為基礎，通過多樣性度量控制種群特征，從而實現粒子間吸引和互斥平衡以避免算法收斂性早熟。Morten Lovbjerg 和Thiemo Krink 提出了另一種改善粒子多樣性的途徑———自組織臨界點控制(Self Organized Criticality ，SOC) 方法。Thiemo Krink 等設計一種粒子空間擴展的方法(SPEPSO) 來解決粒子間的沖突和聚集問題，來解決算法搜索多樣性的問題，這種方法同時增強了粒子突破局部極小值的能力。 這種方法中為每個粒子附加一個最小獨立半徑r ，當與其他粒子間的距離小于r時，即認為二者發生“摩擦”，則采取控制措施使之分離。

設計一種處理動態系統優化的自適應PSO算法，通過增加環境檢測和響應兩種新的算法特征解決了PSO對動態系統空間變化的適應性問題。 并首次提出了群體的生命周期問題———種群的隨機多代初始化，為這種基于演化的算法理論開創了新的研究思想。

進化計算中的幾個基本方法，也被分別針對不同的應用加入PSO算法中。

Angeline于1999年就將進化計算中的選擇概念，引入到PSO算法中。通過淘汰適應值高的微粒，保留具有較高適應值的微粒進行復制來加快收斂速度。

Lovbjerg等將交叉算子應用于PSO算法，并給出了算法的具體形式，通過測試函數的仿真實驗說明了算法的有效性。Miranda等人將引入了PSO中變異算子的使用方法。要指出的是，這些算法改進了PSO原有的一些問題，但也在一定程度上削弱了一些PSO的優點。

與其他方法的融合：為了進一步提高PSO 的性能，許多研究者還嘗試了將其與其他計算智能方法相融合，以突破其自身局限。

有人提出了兩種與演化算法相結合的混合型PSO 優化器。通過在基本的PSO 中引入繁殖和子種群的概念，增強其收斂性和尋求最優解的能力。 在每輪迭代中隨機選擇一定的粒子作為父代，通過繁殖公式生成具有新的空間坐標和速度的子代粒子，并取代父代以保持種群規模。 其實這是一種提高對解空間搜索能力和粒子多樣性的數學交叉，可在一定程度上增強系統跳出局部極小的能力。

黃德雙等對小生境(Niche)進行了研究，提出了多子群PSO（Multi-Sub-Swarm PSO）算法對Niche半徑的動態處理，避免兩個子群對同一個極值進行搜索，對多點極值問題的解決提供了一個有效的方法。

彭喜元等在研究論文中提出了一種將PSO 與模擬退火算法相結合的PSOSA 算法性能分析過程中發現的初始參數依賴性問題和算法搜索能力問題。 通過模擬退火算法賦予搜索過程一種時變且最終趨于零的概率突跳性，有效地降低了陷入局部極小的概率，從而獲取更佳的近似最優解。

五、分析和總結

PSO理論的應用方法的實踐研究證明，盡管與各種比較成熟的計算智能方法相比，PSO的研究還不完善，并存在一些有待深入研究和解決的問題，但PSO的研究已成為計算機研究發展的一個重要方向。

PSO具有明顯的潛在優勢。它處理靈活、計算穩定、具備分布式控制和自組織能力。 而且工程問題中日益復雜的信息處理需求，尤其是動態特性突出的問題，為PSO的應用研究提供了廣闊的空間。

但其相關數學分析還比較薄弱，這就導致了現有研究還存在以下幾個主要問題:

PSO算法的數學理論基礎相對薄弱，缺乏具備普遍意義的理論性分析。 算法中涉及的各種參數設置一直沒有確切的理論依據，通常都是按照經驗型方法確定，對具體問題和應用環境的依賴性比較大; 比較性研究不足，也就是說與各種成熟的優化算法之間的基本特性及性能特點的對比研究還不是十分充分，而且還缺乏用于性能評估的標準測試集; 同其他的自適應問題處理方法一樣，PSO也不具備絕對的可信性。 當處理突發事件時，系統的反應可能是不可測單個個體的復雜性、學習能力和推理能力等。 另外，還應擴展PSO與其他各種先進技術(如:神經網絡、模糊邏輯、禁忌搜索和支持向量機等) 的融合，以改善其自身或相應技術方法的性能的，這在一定程度上增加了其應用風險。

在這方面已經有Frans van den Bergh等對標準PSO收斂性進行了研究。曾建潮等對收斂的保證行進行了研究，并提出了一種保證全局收斂的隨機微粒群算法（Guaranteed Global Convergence Stochastic PSO， GGCSPSO）。

在研究方向上，一方面要研究和解決前面指出的弱點和不足之處，另一方面要進一步明確與算法原理相關的重要定義，如:單個個體的復雜性、學習能力和推理能力等。另外，還應擴展PSO與其他各種先進技術(如:神經網絡、模糊邏輯、禁忌搜索和支持向量機等) 的融合，以改善其自身或相應技術方法的性能。利用有效的數學工具對PSO算法的運行行為、收斂性及計算復雜性進行充分的研究。

無論是從理論研究還是應用研究的角度分析，PSO理論及應用研究都是具有重要學術意義和現實價值。

參考文獻:

[1]趙瑩鄭君里:采用粒子集群算法的DS-CDMA 多用戶檢測. 清華大學學報(自然科學版)， Vo l. 44， No. 6. 2004. 840-842

[2]杜天軍陳光劉占辰雷勇:基于PSO算法的彈道辨識網絡及仿真.系統仿真學報，Vol. 16 No. 11. 2004

[3]彭喜元彭宇戴毓豐:群智能理論及應用.電子學報， Vol.31 No.12A Dec. 2003 1983～1988

[4]曾建潮介婧崔志華:微粒群算法.科學出版社，2004

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