pso:微粒群算法-中文百科頻道

來源背景

為了說明粒子群優化算法的發展和形成背景，首先介紹一下早期的簡單模型，即Boid（Bird-oid）模型。這個模型是為了模拟鳥群的行為而設計的，它也是粒子群優化算法的直接來源。

一個最簡單的模型是這樣的：每一個鳥的個體用直角坐标系上的點表示，随機地給它們賦一個初速度和初位置，程序運行的每一步都按照“最近鄰速度匹配”規則，很快就會使得所有點的速度變得一樣。因為這個模拟太簡單而且遠離真實情況，于是在速度項中增加了一個随機變量，即在叠代的每一步，除了滿足“最近鄰速度匹配”之外，每一步速度還要添加一個随機變化的量，這樣使得整個模拟看起來更為真實。

Heppner設計了一個“谷地模型”來模拟鳥群的覓食行為。假設在平面上存在一個“谷地”，即食物所在地，鳥群開始時随機地分散在平面上，為了尋覓食物所在地，它們按照如下規則運動：

首先假設谷地的位置坐标為，單個鳥的位置和速度坐标分别為和，用當前位置到谷地的距離：

來衡量當前位置和速度的“好壞程度”，離谷地的距離越近，則越“好”，反之越“壞”。假設每一個鳥具有記憶能力，能夠記住曾經達到的最好位置，記作pBest，并記a為系統規定的速度調節常數，rand為一個[0,1]間的随機數，設定速度項按照下述規則變化：

然後假設群體之間可以以某種方式通訊，每個個體能夠知道并記住到當前為止整個群體的最好位置，記為gBest，記b為系統規定的速度調節常數，Rand為一個[0,1]間的随機數，則速度項在經過以上調整後，還必須按照下述規則變化：

在計算機上模拟的結果顯示：當a/b較大時，所有的個體很快地聚集到“谷地”上；反之，粒子緩慢地搖擺着聚集到“谷地”的四周。通過這個簡單的模拟，發現群體能很快地找到一個簡單函數（2-1）的最優點。受該模型啟發，Kennedy和Eberhart設計出了一種演化優化算法，并通過不斷的試驗和試錯，最後将此算法的基本型固定為：

其中符号的意義同上。研究者認為每個個體被抽象為沒有質量和體積，而僅僅具有速度和位置的微粒，故将此方法稱為“粒子群”優化算法。

據此，可對粒子群算法小結如下：粒子群算法是一種基于種群的搜索過程，其中每個個體稱作微粒，定義為在D維搜索空間中待優化問題的潛在解，保存有其曆史最優位置和所有粒子的最優位置的記憶，以及速度。在每一演化代，微粒的信息被組合起來調整速度關于每一維上的分量，繼而被用來計算新的微粒位置。微粒在多維搜索空間中不斷改變它們的狀态，直到到達平衡或最優狀态，或者超過了計算限制為止。

問題空間的不同維度之間唯一的聯系是通過目标函數引入的。很多經驗證據已經顯示該算法是一個非常有效的優化工具。微粒群優化算法的流程圖見圖2-1。

以下給出微粒群算法的比較完整的形式化表述。在連續空間坐标系中，微粒群算法的數學描述如下：設微粒群體規模為N，其中每個微粒在D維空間中的坐标位置向量表示為，速度向量表示為，微粒個體最優位置（即該微粒經曆過的最優位置）記為，群體最優位置（即該微粒群中任意個體經曆過的最優位置）記為。不失一般性，以最小化問題為例，在最初版本的微粒群算法中，個體最優位置的叠代公式為：

群體最優位置為個體最優位置中最好的位置。速度和位置叠代公式分别為：

由于初始版本在優化問題中應用時效果并不太好，所以初始算法提出不久之後就出現了一種改進算法，在速度叠代公式中引入了慣性權重ω，速度叠代公式變為：

雖然該改進算法與初始版本相比複雜程度并沒有太大的增加，但是性能卻有了很大的提升，因而被廣泛使用。一般的，将該改進算法稱為标準微粒群算法，而将初始版本的算法稱為原始微粒群算法。

通過分析PSO算法的收斂行為，Clerc介紹了一種帶收縮因子的PSO算法變種，收縮因子保證了收斂性并提高了收斂速度。此時的速度叠代公式為：

顯然，叠代公式（2-7）和（2-8）并無本質區别，隻要适當選取參數，二者完全相同。

微粒群算法有兩種版本，分别稱為全局版本和局部版本。在全局版本中，微粒跟蹤的兩個極值為自身最優位置pBest和種群最優位置gBest。對應的，在局部版本中，微粒除了追随自身最優位置pBest之外，不跟蹤種群最優位置gBest，而是跟蹤拓撲鄰域中的所有微粒的最優位置nBest。對于局部版本，速度更新公式（2-7）變為：

其中為局部鄰域中的最優位置。

每一代中任意微粒叠代的過程見圖2-2所示。從社會學的角度來看速度叠代公式，其中第一部分為微粒先前速度的影響，表示微粒對當前自身運動狀态的信任，依據自身的速度進行慣性運動，因此參數ω稱為慣性權重（Inertia Weight）；第二部分取決于微粒當前位置與自身最優位置之間的距離，為“認知（Cognition）”部分，表示微粒本身的思考，即微粒的運動來源于自己經驗的部分，因此參數c1稱為認知學習因子（也可稱為認知加速因子）；第三部分取決于微粒當前位置與群體中全局（或局部）最優位置之間的距離，為“社會（Social）”部分，表示微粒間的信息共享與相互合作，即微粒的運動來源于群體中其他微粒經驗的部分，它通過認知模拟了較好同伴的運動，因此參數c2稱為社會學習因子（也可稱為社會加速因子）。

自從PSO算法被提出以來，由于它直觀的背景，簡單而容易實現的特點，以及對于不同類型函數廣泛的适應性，逐漸得到研究者的注意。十餘年來，PSO算法的理論與應用研究都取得了很大的進展，對于算法的原理已經有了初步的了解，算法的應用也已經在不同學科中得以實現。

PSO算法是一種随機的、并行的優化算法。它的優點是：不要求被優化函數具有可微、可導、連續等性質，收斂速度較快，算法簡單，容易編程實現。然而，PSO算法的缺點在于：（1）對于有多個局部極值點的函數，容易陷入到局部極值點中，得不到正确的結果。造成這種現象的原因有兩種，其一是由于待優化函數的性質；其二是由于微粒群算法中微粒的多樣性迅速消失，造成早熟收斂。這兩個因素通常密不可分地糾纏在一起。（2）由于缺乏精密搜索方法的配合，PSO算法往往不能得到精确的結果。造成這種問題的原因是PSO算法并沒有很充分地利用計算過程中獲得的信息，在每一步叠代中，僅僅利用了群體最優和個體最優的信息。（3）PSO算法雖然提供了全局搜索的可能，但是并不能保證收斂到全局最優點上。（4）PSO算法是一種啟發式的仿生優化算法，當前還沒有嚴格的理論基礎，僅僅是通過對某種群體搜索現象的簡化模拟而設計的，但并沒有從原理上說明這種算法為什麼有效，以及它适用的範圍。因此，PSO算法一般适用于一類高維的、存在多個局部極值點而并不需要得到很高精度解的優化問題。

當前針對PSO算法開展的研究工作種類繁多，經歸納整理分為如下八個大類：（1）對PSO算法進行理論分析，試圖理解其工作機理；（2）改變PSO算法的結構，試圖獲得性能更好的算法；（3）研究各種參數配置對PSO算法的影響；（4）研究各種拓撲結構對PSO算法的影響；（5）研究離散版本的PSO算法；（6）研究PSO算法的并行算法；（7）利用PSO算法對多種情況下的優化問題進行求解；（8）将PSO算法應用到各個不同的工程領域。以下從這八大類别着手，對PSO算法的研究現狀作一梳理。由于文獻太多，無法面面俱到，僅撿有代表性的加以綜述。