粒子羣優化算法

粒子羣優化算法(Particle Swarm optimization,PSO)又翻譯為粒子羣算法、微粒羣算法、或微粒羣優化算法。是通過模擬鳥羣覓食行為而發展起來的一種基於羣體協作的隨機搜索算法。通常認為它是羣集智能 (Swarm intelligence, SI) 的一種。它可以被納入多主體優化系統(Multiagent Optimization System, MAOS)。粒子羣優化算法是由Eberhart博士和kennedy博士發明。

PSO模擬鳥羣的捕食行為。一羣鳥在隨機搜索食物，在這個區域裏只有一塊食物。所有的鳥都不知道食物在那裏。但是他們知道當前的位置離食物還有多遠。那麼找到食物的最優策略是什麼呢。最簡單有效的就是搜尋離食物最近的鳥的周圍區域。

PSO從這種模型中得到啓示並用於解決優化問題。PSO中，每個優化問題的解都是搜索空間中的一隻鳥。我們稱之為“粒子”。所有的粒子都有一個由被優化的函數決定的適應值(fitnessvalue)，每個粒子還有一個速度決定他們飛翔的方向和距離。然後粒子們就追隨當前的最優粒子在解空間中搜索。

PSO初始化為一羣隨機粒子(隨機解)，然後通過迭代找到最優解，在每一次迭代中，粒子通過跟蹤兩個“極值”來更新自己。第一個就是粒子本身所找到的最優解，這個解叫做個體極值pBest，另一個極值是整個種羣找到的最優解，這個極值是全局極值gBest。另外也可以不用整個種羣而只是用其中一部分最優粒子的鄰居，那麼在所有鄰居中的極值就是局部極值。

在找到這兩個最優值時,粒子根據如下的公式來更新自己的速度和新的位置

(a)

(b)

v[] 是粒子的速度，present[] 是當前粒子的位置。pbest[] 和 gbest[] 如前定義。rand() 是介於(0,1)之間的隨機數。c1，c2是學習因子。通常c1=c2=2。

For each particle

____Initialize particle

END

Do

____For each particle

________Calculate fitness value

________If the fitness value is better than the best fitness value (pBest) in history

____________set current value as the new pBest

____End

____Choose the particle with the best fitness value of all the particles as the gBest

____For each particle

________Calculate particle velocity according equation (a)

________Update particle position according equation (b)

____End

While maximum iterations or minimum error criteria is not attained

在每一維粒子的速度都會被限制在一個最大速度Vmax，如果某一維更新後的速度超過用户設定的Vmax，那麼這一維的速度就被限定為Vmax。

①種羣隨機初始化。

②對種羣內的每一個個體計算適應值(fitness value)。適應值與最優解的距離直接有關。

③種羣根據適應值進行復制。

④如果終止條件滿足的話，就停止，否則轉步驟② 。

從以上步驟，我們可以看到PSO和遺傳算法有很多共同之處。兩者都隨機初始化種羣，而且都使用適應值來評價系統，而且都根據適應值來進行一定的隨機搜索。兩個系統都不是保證一定找到最優解。但是，PSO沒有遺傳操作如交叉(crossover)和變異(mutation)，而是根據自己的速度來決定搜索。粒子還有一個重要的特點，就是有記憶。

與遺傳算法比較，PSO的信息共享機制是很不同的。在遺傳算法中，染色體(chromosomes)互相共享信息，所以整個種羣的移動是比較均勻的向最優區域移動。在PSO中, 只有gBest (orlBest) 給出信息給其他的粒子， 這是單向的信息流動。整個搜索更新過程是跟隨當前最優解的過程。與遺傳算法比較, 在大多數的情況下，所有的粒子可能更快的收斂於最優解。

演化計算的優勢，在於可以處理一些傳統方法不能處理的。例子例如不可導的節點傳遞函數或者沒有梯度信息存在。

但是缺點在於：

1.在某些問題上性能並不是特別好。

2.網絡權重的編碼而且遺傳算子的選擇有時比較麻煩。

最近已經有一些利用PSO來代替反向傳播算法來訓練神經網絡的論文。研究表明PSO 是一種很有潛力的神經網絡算法。PSO速度比較快而且可以得到比較好的結果。而且還沒有遺傳算法碰到的問題。

人工神經網絡(ANN)是模擬大腦分析過程的簡單數學模型，反向傳播算法是最流行的神經網絡訓練算法。近來也有很多研究開始利用演化計算(evolutionary computation)技術來研究人工神經網絡的各個方面。

演化計算可以用來研究神經網絡的三個方面：網絡連接權重，網絡結構(網絡拓撲結構，傳遞函數)，網絡學習算法。

不過大多數這方面的工作都集中在網絡連接權重，和網絡拓撲結構上。在GA中，網絡權重和/或拓撲結構一般編碼為染色體(Chromosome)，適應函數(fitness function)的選擇一般根據研究目的確定。例如在分類問題中，錯誤分類的比率可以用來作為適應值。

這裏用一個簡單的例子説明PSO訓練神經網絡的過程。這個例子使用分類問題的基準函數 (Benchmark function)IRIS數據集。(Iris 是一種鳶尾屬植物) 在數據記錄中，每組數據包含Iris花的四種屬性：萼片長度，萼片寬度，花瓣長度，和花瓣寬度，三種不同的花各有50組數據. 這樣總共有150組數據或模式。

我們用3層的神經網絡來做分類。有四個輸入和三個輸出。所以神經網絡的輸入層有4個節點，輸出層有3個節點我們也可以動態調節隱含層節點的數目，不過這裏我們假定隱含層有6個節點。我們也可以訓練神經網絡中其他的參數。不過這裏我們只是來確定網絡權重。粒子就表示神經網絡的一組權重，應該是4*6+6*3=42個參數。權重的範圍設定為[-100，100] (這只是一個例子，在實際情況中可能需要試驗調整).在完成編碼以後，我們需要確定適應函數。對於分類問題，我們把所有的數據送入神經網絡，網絡的權重有粒子的參數決定。然後記錄所有的錯誤分類的數目作為那個粒子的適應值。我們就利用PSO來訓練神經網絡來獲得儘可能低的錯誤分類數目。PSO本身並沒有很多的參數需要調整。所以在實驗中只需要調整隱含層的節點數目和權重的範圍以取得較好的分類效果。

從上面的例子我們可以看到應用PSO解決優化問題的過程中有兩個重要的步驟: 問題解的編碼和適應度函數PSO的一個優勢就是採用實數編碼, 不需要像遺傳算法一樣是二進制編碼(或者採用針對實數的遺傳操作.例如對於問題 f(x) = x1^2 + x2^2+x3^2 求解,粒子可以直接編碼為 (x1, x2, x3), 而適應度函數就是f(x). 接着我們就可以利用前面的過程去尋優.這個尋優過程是一個迭代過程, 中止條件一般為設置為達到最大循環數或者最小錯誤

PSO中並沒有許多需要調節的參數,下面列出了這些參數以及經驗設置

粒子數: 一般取 20–40. 其實對於大部分的問題10個粒子已經足夠可以取得好的結果, 不過對於比較難的問題或者特定類別的問題, 粒子數可以取到100 或 200

粒子的長度: 這是由優化問題決定, 就是問題解的長度

粒子的範圍: 由優化問題決定,每一維可是設定不同的範圍

Vmax: 最大速度,決定粒子在一個循環中最大的移動距離,通常設定為粒子的範圍寬度,例如上面的例子裏,粒子 (x1, x2, x3) x1 屬於 [-10, 10], 那麼 Vmax 的大小就是 20

學習因子: c1 和 c2 通常等於 2. 不過在文獻中也有其他的取值. 但是一般 c1 等於 c2 並且範圍在0和4之間

中止條件: 最大循環數以及最小錯誤要求. 例如, 在上面的神經網絡訓練例子中, 最小錯誤可以設定為1個錯誤分類, 最大循環設定為2000, 這個中止條件由具體的問題確定.

全局PSO和局部PSO: 我們介紹了兩種版本的粒子羣優化算法: 全局版和局部版. 前者速度快不過有時會陷入局部最優. 後者收斂速度慢一點不過很難陷入局部最優. 在實際應用中, 可以先用全局PSO找到大致的結果,再用局部PSO進行搜索.

另外的一個參數是慣性權重, 由Shi 和Eberhart提出, 有興趣的可以參考他們1998年的論文(題目: A modified particle swarm optimizer)。