WCT: [PSO] PSO STORY

全文引用自：http://edisonx.pixnet.net/blog/post/81640299

PSO 演算法，全名稱粒子群移動演算法，Particle Swarm Optimization，屬於尋優式演算法，以「鳥群覓食」為概念所發展出來，但也有人認為可以用社會學的概念去解釋它，這些以鳥群覓食為擬化。

這是一個鳥群吃飯的故事。假設有 20 隻鳥在一地區做覓食的動作，
牠們想在這地區裡面，找到食物最多的區塊。

(1) 一開始牠們只會漫無目的的亂飛，去找食物。
(2) 找了十分鐘之後，會開始猶豫，現在找的這個地方是不是正確的？至於十分鐘後，牠會往哪個方向覓食？取決於以下各因素：
　　(2.1) 在剛剛的十分鐘裡面，牠自己往這方向、速度看到食物的多寡，猶豫要不要繼續下去。
　　(2.2) 在以前的記憶體，牠曾看到食物最多的地方。
　　(2.3) 在這 20 隻鳥裡面，曾有一隻鳥發訊息告訴大家，目前牠找到食物最多的地方是在哪。
(3) 在剛剛猶豫的時間裡，有三個提示出來，於是這隻鳥根據剛剛的三點原則，去調整找食物的方向及速度。
(4) 重覆著 (2)、(3) ，猶豫、改變方向的動作，一直過了一天後，這群鳥集中到了目前大家覺得找到食物最多的地方。

看完這個故事好像沒什麼心得，再 po 一次這故事，這次把粒子移動參數及說明再放進去。

這是一個鳥群吃飯的故事。假設有 20 隻鳥 (粒子個數) 在一地區 (變數個數及各變數範圍) 做覓食的動作(目標式)，牠們想在這地區裡面，找到食物最多的區塊(尋優解)。

(1) 一開始牠們只會漫無目的的亂飛(初始化粒子之位置與速度)，去找食物。
(2) 找了十分鐘之後(經過一次迭代後)，會開始猶豫，現在找的這個地方是不是正確的？至於十分鐘後，牠會往哪個方向覓食？取決於以下各因素：
　　(2.1) 在剛剛的十分鐘裡面，牠自己往這方向、速度看到食物的多寡，猶豫要不要繼續下去(解本身之權重 w)。
　　(2.2) 在以前的記憶體，牠曾看到食物最多的地方。(粒子本身曾找過最佳解之權重 c1)
　　(2.3) 在這 20 隻鳥裡面，曾有一隻鳥發訊息告訴大家，目前牠找到食物最多的地方是在哪。(所有粒子曾找過最佳解之權重 c2)
(3) 在剛剛猶豫的時間裡，有三個提示出來，於是這隻鳥根據剛剛的三點原則，去調整找食物的方向及速度。(更新粒子位置、速度)
(4) 重覆著 (2)、(3) ，猶豫、改變方向的動作，一直過了一天後，這群鳥集中到了目前大家覺得找到食物最多的地方。(重覆 (2), (3) 步驟，直到收斂)

故事往往讓人覺得納悶是在更新速度那裡，假設一開始牠的速度及位置是 v0 與 x0，

更新的速度與位置是 v1 與 x1，那牠要怎麼更新速度和位置 x1, v1？
這要看那隻鳥的個性如何，也就是要看參數 w、c1、c2 要怎麼設？
如果這隻鳥很有個性，不被外界所影響，堅持已見，就像滿清末年那樣的話，
v1 = w * v0，
如果這隻鳥有點智慧，它還會回想起以前自己曾到過哪些地方食物最多的話，
v1 = w*v0 + c1 * (這隻鳥曾最到過最好的位置 - 這隻鳥現在的位置)
如果這隻鳥還懂得團隊合作，它還會去參考別人成功的因素是在哪裡的話，
v1 = w*v0 + c1 * (這隻鳥曾最到過最好的位置 - 這隻鳥現在的位置) + c2 * (目前大家到過最好的位置 - 這隻鳥現在的位置)

上面這些其實都該用符號去表示，
「這隻鳥現在位置」 = 「這個粒子現在位置」 = x0
「這隻鳥曾到過最好的位置」 = 「這個粒子曾得到的最佳解」 = particle best = pbest_x
「目前大家到過的最好位置」 = 「所有粒子曾得到的最佳解」 = global best = gbest_x

再套入一些不確定因素做為亂數干擾(干擾因素小於1)後，原本的更新速度就變成了
v1 = w*v0 + c1 * (這隻鳥曾最到過最好的位置 - 這隻鳥現在的位置) + c2 * (目前大家到過最好的位置 - 這隻鳥現在的位置)
v1 = w * v0 + c1 * rand() * (pbest_x - x0) + c2 * rand() * (gbest_x - x0)
這就是粒子移動的速度更新公式。注意到，通常會再限制速度的最大值 vmax，
也就是說，如果更新的速度 v1 大於 vmax，則直接將 v1 視為 vmax。
那位置呢？回想一下國中物理有教過的，
距離 = 時間 * 速率，s = t * v
由於每次都要迭代，故時間固定為 1，這樣下來，
s = t * v1 = 1* v1 = 1 * v1 = v1
而更新的位置 = 上次的位置 + 移動距離，故可得到
x1 = x0 + s = x0 + v1

至此，上述所有比擬已把 pso 演算法精髓講完一半，下面是整理過後的部份。

1. 適應函式 fitness function ：即要解決的問題。如旅行員到各地怎麼旅行才能是最少的距離；如股票怎麼分配投資才能得到最大收益；如股票怎麼分配投資才能得到最小風險。如線性規劃之目標式等等，這些都屬適應函式。適應函式是依問題存在，盡可能寫出數學表達式出來。 (數學不好、寫不出來的話，也要知道怎麼去計算它的適應值出來，不然就沒得玩了)。
2. 粒子個數 particle count ：此參數由 coder 自設，一般小型問題大概設 20~40 左右，較大型設 100~200，但這已顯少。
3. 權重值 w : 此參數由 coder 自設，早期並沒有這個值的存在，正確的說，早期這個值都視為 0.0，目前看過，大多都設在 [0.0 , 1.5 ] 之間，保守的話可設 1.0 (即與上一迭代值相關)。
4. 常數 c1 : 此參數由 coder 自設，多設 2 ，其它也多設 [0,4] 。
5. 常數 c2 : 此參數由 coder 自設，多設 2 ，其它也多設 [0,4]。
6. 設定各變數上、下界：通常都是先界定各變數之範圍出來，再去範圍內去尋優，意思是可以的話，先經由數學式的推導或判斷，最佳解可能是落在哪區域。如 -100 <=x1 <= +100 ; 10 <= x2 <= -10 等。
7. 速度更新與速度上界：速度更新由上面公式取得，而速度上界此參數由 coder 自設，通常速度上界 = (變數最大值 - 變數最小值) ，換而言之，若 -10 <=x <=10，則速度上界定為 10 - (-10) = 20。這部份可以講的、補充的非常多，改天再發文補上。
8. 位置更新與位置上下界：位置更新由上面公式取得，位置上下界就是上面 6. 裡面提到的，設定各變數之上、下界。

2013/12/09

[PSO] PSO STORY