一、建模思想
微粒群算法（粒子群算法）是從20世紀(jì)90年代初發(fā)展起來的一種群體智能算法。基本思想是模擬鳥群和魚群的群體行為來構(gòu)造隨機(jī)優(yōu)化算法。

美國的社會(huì)心理學(xué)家Kennedy和電氣工程師Eberhart早期在對(duì)鳥群的群體行為進(jìn)行研究時(shí)發(fā)現(xiàn)。雖然每一個(gè)個(gè)體具有非常簡單的行為規(guī)則，但群體的行為非常復(fù)雜。比如鳥群在覓食或?qū)ふ覘⒌氐臅r(shí)候使用簡單的規(guī)則確定自己的飛行方向和飛行速度。建立仿真模型時(shí)就采用了以下的三條簡單規(guī)則：

（1）飛離最近的個(gè)體，避免碰撞；
（2）飛向目標(biāo)；
（3）飛向群體中心。

從這幾點(diǎn)看來，鳥類尋找棲息地和對(duì)一個(gè)特定問題求解很類似。尋找棲息地的過程就是尋找最優(yōu)解的過程。已經(jīng)找到棲息地的鳥會(huì)引導(dǎo)它周圍的鳥飛向棲息地。一只鳥就是一個(gè)粒子。對(duì)一個(gè)優(yōu)化問題來說，一只鳥的位置就是一個(gè)解，那建立仿真模型的關(guān)鍵就是微粒能夠飛向解空間并且在最好解的位置降落。
Pi ---- 當(dāng)前最好位置
Pg ---- 全局最好位置
S個(gè)微粒Xi

比如在一個(gè)空間當(dāng)中S個(gè)微粒Xi，它們的初始位置以及飛行速度都是隨機(jī)的。最優(yōu)解在某一個(gè)位置，在飛行過程當(dāng)中，每一個(gè)微粒都有它自己所經(jīng)歷過的最好位置Pi，所有的這些微粒又有一個(gè)全局最好位置Pg。微粒的飛行是有一定記憶特性的，它會(huì)向著Pi和Pg飛行。在飛行的過程中又會(huì)產(chǎn)生新的Pi和Pg，直到找到最優(yōu)解。

二、基本微粒群算法

2.1 算法原理

不失一般性，我們使所要求的最優(yōu)解問題為：

對(duì)于這個(gè)最優(yōu)化問題，微粒群算法的求解模型是這樣的：
初始化S個(gè)微粒 {X1,X2,…….,Xs}。設(shè)：
Xi = { Xi1,Xi2,…….Xin }為微粒i的當(dāng)前位置
Vi = { Vi1,Vi2,…….,Vin }為微粒i的當(dāng)前速度
Pi = { Pi1,Pi2,…….,Pin }為微粒i的當(dāng)前最好速度
(Pi是迭代過程中產(chǎn)生的，指的是微粒i所經(jīng)歷過的具有最好適應(yīng)值的位置，也稱個(gè)體最好位置。)

迭代公式為：

定義Pg(t)為全局最好位置：

有以上的基本定義，基本微粒群算法的描述為：

從（3）可以看出，C1是調(diào)節(jié)微粒飛向自身最好位置的步長，C2是調(diào)節(jié)微粒飛向全局最好位置的步長。為了在進(jìn)化過程中，微粒能夠留在搜索空間，一般要給Vi一個(gè)限定范圍：
-Vmax <= Vi <= Vmax
-Xmax <= Xi <= Xmax
Vmax = kXmax , 0 <= k <=1.0
以上是基本微粒群算法的基本模型。下面是算法流程。

2.2 算法流程
（1）初始化
i. 設(shè)定種群規(guī)模S
ii. 在 [ -Xmax , Xmax ]產(chǎn)生均勻分布Xi
iii. 在 [ -Vmax , Vmax ]產(chǎn)生均勻分布Vi
iv. 令Pi = Xi

（2）計(jì)算每個(gè)微粒的適應(yīng)值f( Xi )

（3）求取Pi

（4）求取Pg

（5）對(duì)速度和位置進(jìn)行進(jìn)化

（6）判斷是否達(dá)到結(jié)束條件，否就返回步驟（2）

2.3 算法分析
從上面的算法流程可以看出，基本微粒群算法相對(duì)來說比較簡單，計(jì)算量較小，那么基本微粒群算法的效果怎么樣，能否達(dá)到問題優(yōu)化目的。下面我們做一個(gè)算法分析：

把（3）式化簡為： Vi(t+1) = G1 + G2 + G3 （5）
其中 G1 = Vi(t)
G2 = C1r1[ Pi(t) - Xi(t) ]
G3 = C2r2[ Pi(t) - Xi(t) ]
那么，G1是微粒先前的速度，G2稱為認(rèn)知部分，考慮微粒自身的經(jīng)驗(yàn)，表示微粒對(duì)本身的思考。G3稱為“社會(huì)”部分，表示微粒對(duì)社會(huì)信息的共享。

那么，我們可以看出，G1是微粒原先的速度項(xiàng)，G2，G3是對(duì)速度的修正。

如果沒有 Vi(t+1) = G1， 微粒保持原來的速度不變，一只飛向搜索的邊界。

如果包含認(rèn)知部分Vi(t+1) = G1 + G2，則進(jìn)化的性能變差，主要是因?yàn)樾畔⑷狈涣?#xff0c;即沒有社會(huì)信息共享，微粒之間沒有交互，使得一個(gè)規(guī)模為S的群體等價(jià)于運(yùn)行了S個(gè)單個(gè)微粒。因而得到最優(yōu)解的可能性很小。

如果只包含社會(huì)部分，即 Vi(t+1) = G1 + G3，這樣微粒在相互作用下有能力達(dá)到新的搜索空間，但對(duì)與復(fù)雜的問題容易陷入局部最優(yōu)點(diǎn)，這一點(diǎn)已經(jīng)由Eberhart進(jìn)行了證明。

如果不要速度項(xiàng)，只保留認(rèn)知部分和社會(huì)部分，即Vi(t+1) = G2 + G3，那么這時(shí)微粒的速度將取決于歷史最優(yōu)位置與群體最優(yōu)位置，從而導(dǎo)致速度無記憶性。假如有一個(gè)微粒處在了整體最優(yōu)位置，它將停止進(jìn)化，其它的微粒向著這個(gè)最優(yōu)位置飛去，并在這個(gè)位置的周圍搜索，這說明沒有第一項(xiàng)的話，算法有很強(qiáng)的局部搜索能力。

通過以上分析，我們可以發(fā)現(xiàn)G2，G3使得微粒群算法具有局部收斂能力，G1則保證算法的全局收斂能力，這一點(diǎn)也是比遺傳算法好的地方。

三、改進(jìn)微粒群算法

前邊是整個(gè)基本微粒群算法的基本原理、算法流程、算法分析。基本微粒群算法有很多優(yōu)點(diǎn)，比如，算法簡單，計(jì)算量小，全局搜索能力強(qiáng)等。但人們?cè)诶没疚⒘Ｈ核惴?#xff0c;求解最優(yōu)化問題時(shí)，也發(fā)現(xiàn)了基本微粒群算法的一些缺點(diǎn)：比如前邊提到了基本微粒群算法第一部分保證全局搜索能力，第二、三部分保證局部搜索能力。對(duì)于不同的問題，如何確定局部搜索能力和全局搜索能力的比例關(guān)系，對(duì)求解過程非常重要。于是有人提出了帶慣性權(quán)重的改進(jìn)微粒群算法：

Vi(t+1) = wVi(t) + C1r1[ Pi(t) - Xi(t) ] + C2r2[ Pi(t) - Xi(t) ]
Xi(t+1)= Xi(t)+ V(t+1)

w稱為慣性權(quán)重，取值范圍一般在 [0.9 ,1.2]計(jì)算時(shí)收斂速度較快。
慣性權(quán)重類似于模擬褪火算法中的溫度，較大的w有較好的全局收斂能力，單容易在最優(yōu)解處發(fā)生震蕩，而較小的w有較強(qiáng)的局部收斂能力。從這一點(diǎn)看，隨著迭代次數(shù)的增加，w應(yīng)不但減少，以而使算法在初期具有較強(qiáng)的全局收斂能力，晚期具有較強(qiáng)的局部收斂能力。

一種典型的遞減方法是線性遞減方法：
w(t) = 0.9 – 0.5*t/maxNumber （6）

maxNumber為最大截止代數(shù)，t為迭代次數(shù)，這種方法對(duì)于4個(gè)測試函數(shù)測試效果很好。

四、備注
PSO算法常有如下n種重要的控制參數(shù)：
（1）微粒群的規(guī)模S
（2）認(rèn)知學(xué)習(xí)系數(shù)C1
（3）社會(huì)學(xué)習(xí)系數(shù)C2
（4）控制微粒飛行的速度Vmax
（5）慣性權(quán)重系數(shù)w

五、應(yīng)用實(shí)例

總結(jié)

以上是生活随笔為你收集整理的微粒群算法（一、简介）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。