2013/12/09

[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. 裡面提到的,設定各變數之上、下界。