簡述粒子群算法的原理及改進

摘要：本文主要介紹了粒子群（Praticle Swarm Optimizer， PSO）算法，它是一種新的基于群體智能的優化算法，是在鳥群覓食行為規律的基礎上提出的。他其結構簡單、參數調整簡單易行，更適合計算機編程處理，但在該算法中，如果粒子速度始終保持較大，容易“飛越”解空間中的最優區域，造成發散現象，收斂不到最優解，如果從慣性權重的自適應方面來調整，就可以很好的解決該問題。

關鍵詞：粒子群優化算法；慣性權重的自適應；收斂性

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)12-2pppp-0c

PSO Algorithm and the Principle of Improving

XU Xu，JIANG Fei

(Department of Computer Science and Technology Suzhou college，Suzhou 234000，China)

Abstract:This text mainly introduced a grain sons(the Optimizer of the Praticle Swarm， PSO) calculate way，it is a kind of new according to community intelligence of excellent turn calculate way，is the foundation which looks for food behavior regulation in the birds up put forward. He its structure is simple，the parameter adjust to go in brief and easily，the more in keeping with calculator weaves a distance a processing，but in that calculate way， if the grain sub- speed keeps always more and greatly，the superior district in the easy \"fly more\" solution space，result in to dissipate of phenomenon，could not refrain from rash action the superior solution，if heavy from the inertial power of adjust from the orientation aspect，it can be good to resolve that problem.

Key words:particle swarm optimization algorithm;the inertial power is heavy of from orientation;Astringency

1 引言

粒子群優化算法（Particle Swarm Optimization，簡稱PSO）是繼遺傳算法（Genetic Algorithms，簡稱GA）、蟻群算法(Ant Colony Optimization，簡稱ACO)之后提出的一種新型進化計算技術，基本思想來源于對鳥群簡化社會模型的研究及對鳥群覓食過程中遷徙和聚集行為的模擬，該算法利用信息共享機制，使個體之間可以相互借鑒經驗以促進整個群體的發展，具有典型的群體智能特性。PSO于1995年由Kennedy博士和Eberhart博士提出[1]，引起了學者們的廣泛關注，成為了一個新的研究熱點，已在化工系統、電力系統、機械設計、通訊、機器人、經濟、圖像處理、生物信息、醫學、運籌學等多個領域中得到了應用[2]。

2 PSO的基本原理

PSO模擬鳥群的捕食行為。設想這樣一個場景：一群鳥在隨機搜索食物。在這個區域里只有一塊食物。所有的鳥都不知道食物在那里。但是他們知道當前的位置離食物還有多遠。那么找到食物的最優策略是什么呢。最簡單有效的就是搜尋目前離食物最近的鳥的周圍區域。PSO從這種模型中得到啟示并用于解決優化問題。PSO中每個優化問題的解都是搜索空間中的一只鳥。我們稱之為“粒子”。所有的粒子都有一個由被優化函數決定的適應值(fitness value)，每個粒子還有一個速度決定他們飛翔的方向和距離。然后粒子們就追隨當前的最優粒子在解空間中搜索。

PSO初始化為一群隨機粒子P(隨機解)。然后通過疊代找到最優解。在每一次疊代中，粒子P通過跟蹤兩個“極值”來更新自己。第一個就是粒子本身所找到的最優解。這個解叫做個體極值點pbest. 另一個極值是整個種群目前找到的最優解。這個極值是全局極值點gbest。在找到這兩個最優解時， 粒子根據如下的公式來更新自己的速度和新的位置：

其中，下標i代表第i個粒子，下標j代表速度（或位置）的第j維，上標k代表迭代代數，如vijk和vijk分別是第i粒子（Pi）在第k次迭代中第j維的速度和位置，兩者均被限制在一定的范圍內；c1和c2是學習因子，通常c1、c2∈[0，4]；r1和 r2是介于[0，1]之間的隨機數；pbest ijk是粒子Pi在第j維的個體極值的坐標；gbestj k是群體在第 j 維的全局極值的坐標。

3 標準PSO算法

粒子群優化算法(Particle Swarm Optimization，PSO )是群體智能算法的一種，它是由美國社會心理學家James Kennedy和電氣工程師Russell Eberhart 在1995年提出的，其基本思想是對鳥群、魚群的覓食過程中的遷徙和聚集行為的模擬，并利用了生物學家Frank Heppner的生物群體模型。

PSO算法不像遺傳算法那樣對個體進行選擇、交叉和變異操作，而是將群體中的每個個體視為多維搜索空間中一個沒有質量和體積的粒子，這些粒子在搜索空間中以一定的速度飛行，并根據粒子本身的飛行經驗以及同伴的飛行經驗對自己的飛行速度進行動態調整，即每個粒子通過統計迭代過程中自身的最優值和群體的最優值來不斷地修正自己的前進方向和速度大小，從而形成群體尋優的正反饋機制。PSO算法就是這樣依據每個粒子對環境的適應度將個體逐步移到較優的區域，并最終搜索、尋找到問題的最優解。

在PSO算法中，用粒子的位置表示待優化問題的解，每個粒子性能的優劣程度取決于待優化問題目標函數確定的適應值，每個粒子由一個速度矢量決定其飛行方向和速率大小。設在一個 維的目標搜索空間中，有 個粒子組成一個群體，其中，在第 次迭代時粒子 的位置表示為Xi(t)=(xi1(t)， xi2 (t) …， xid(t))，相應的飛行速度表示為 。開始執行PSO算法時，首先隨機初始化 個粒子的位置和速度，然后通過迭代尋找最優解，在每一次迭代中，粒子通過跟蹤兩個極值來更新自己的速度和位置：一個極值是粒子本身迄今搜索到的最優解，稱為個體極值，表示為Pbest(t)=( P1best(t)， P2best(t)，…Pdbest(t))；另一個極值是整個粒子群到目前為止找到的最優解，稱為全局極值，表示為Pbest(t)=( P1best(t)， P2best(t)，…Pdbest(t))。在第t+1次迭代計算時，粒子i根據下列規則來更新自己的速度和位置：

式中w-為慣性權重；C1，C2：為兩個學習因子，一般取為2；rand1和rand2為兩個均勻分布在（0，l）之間的隨機數；i=1，2，…，m；k=1，2，…，d。另外，粒子在每一維的速度Vi都被一個最大速度Vmax所限制。如果當前粒子的加速度導致它在某一維的速度超過該維上的最大速度Vmax，則該維的速度被限制為最大速度。式（3）中第1部分可理解為粒子先前的速度或慣性；第2部份可理解為粒子的“認知”行為，表示粒子本身的思考能力；第3部分可理解為粒子的“社會”行為，表示粒子之間的信息共享與相互合作。

4 PSO算法的改進

在標準粒子群算法中，如果粒子速度始終保持較大，容易“飛越”解空間中的最優區域，造成發散現象，收斂不到最優解[3]。為了保證PSO算法的收斂性，慣性權重通常情況下是線性減小的。若 能隨算法迭代的進行而線性減小，將顯著改善算法的收斂性能。令w-max為最大加權系數，w-min為最小加權系數，iter為當前迭代次數，itermax為算法總迭代次數，則有：

一般w-max取值為0.9，W-min取值為0.4。更新過程中，粒子每一維的最大速率限制在Vmax粒子每一維的坐標也被限制在允許范圍之內。同時，個體極值Pbest和群體極值gbest在迭代過程中不斷更新，最后輸出的gbest就是算法

尋到的最優解。

5 結論

本文主要講述了粒子群算法的基本原理和標準算法，介紹了從慣性權重的自適應方面調整來優化PSO的算法，該算法可以保證PSO算法的收斂性，是一種比較比較理想的算法。

參考文獻：

[1]Kennedy J，Eberhart R.Particle Swarm Optimization[C].Proceedings of IEEE International Conference on Neural Networks，Perth， Australia，1995:1942-1948.

[2]劉波，王凌，金以慧，等.微粒群優化算法研究進展[J].化工自動化及儀表，2005，32(3):1-6.

[3]陳曦，傅明.改進粒子群算法在動態交通分配問題中的應用[J].計算技術與自動化，2006，25(2)60-63.

收稿日期：2008-01-26

作者簡介：徐旭（1981-）男，安徽宿州人，助教，碩士在讀，研究方向：數據挖掘。

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