[回目錄]

 

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

 

[回目錄]

edisonx 發表在 痞客邦 PIXNET 留言(2) 人氣()


留言列表 (2)

發表留言
  • hui
  • 感謝提供!!
    講解的很清楚。@@
    請問可以借我轉載嗎?
  • 歡迎,請註明出處。

    edisonx 於 2012/08/01 17:04 回覆

您尚未登入,將以訪客身份留言。亦可以上方服務帳號登入留言

請輸入暱稱 ( 最多顯示 6 個中文字元 )

請輸入標題 ( 最多顯示 9 個中文字元 )

請輸入內容 ( 最多 140 個中文字元 )

請輸入左方認證碼:

看不懂,換張圖

請輸入驗證碼