[回目錄]

 

[pso] 初步 - 粒子移動演算法精髓 時,

我用了很不正式的敘述說明了 pso 演算法一些參數,

此篇做為稍加詳細之介紹,整體上介紹圍繞在速度更新之公式上。

以下符號,若出現 rnd(),代表取 [0,1] 之間之浮點數亂;

若出現 random(a, b),代表取 [a,b] 之間之浮點亂數。

 

速度更新公式

 

於前幾篇中,我所撰之公式基本形式與符號說明如下

 

vid = w * vid + c1 * rnd() * (pbest_xid - xid)  + c2 * rnd() * (gbest_xd-xid)


vid : 第 i 個粒子,d 維度之速度

rnd() : 產生 [0,1] 之間之浮點亂數

w  : 權重值

c1 : (區域解相關係數) 常數值

c2 : (全域解相關係數) 常數值

xid : 第 i 個粒子,目前在第 d 維度裡之數值

pbest_xid : 第 i 個粒子曾找到的最佳值中,第 d 維度之數值。

gbest_xd : 全域中最佳解中,第 d 維度之數值。

 

事實上這並不是原版的公式,此公式是後期由其他學者改善而來,原版公式為

vid = vid + c1 * rnd() * (pbest_xid - xid)  + c2 * rnd() * (gbest_xd-xid)

沒有相關的 w 權重值。

 

權重值 w

 

關於權重值 w,這篇 pdf 有做介紹。

w < 0.8 時,各粒子將較容易往 gbest 該點移動,收斂會較快,

但卻也容易陷入區域最佳解,若設太小時,其動作較像是 local search,

而非 global search。

w > 1.2 時,各粒子動作是較像在做 global search ,

但卻很容易跳脫原本的搜尋區域,意指,若最佳解是落在該搜尋區域,

也容易被粒子跳脫忽略。

0.8 < w < 1.2 時,這是一般較常設的範圍,

設在這範圍裡,通常是較被認為,gloabl search 與 local search 達到平衡之狀況。

 

係數 c1、c2

 

c1 係數為將各粒子推向 pbest (區域解) 之加速常數,若設太大時,

容易只在該區域解圍繞,最後大多只能找到 local solution。

c2 係數為將各粒子推向 gbest (目前全域解) 之加速常數,若設太大時,

所有粒子容易一直往 gbest 方向移動,要得到新解之機會更小。

 

解空間(粒子位置) xid 限制

 

在有 d 維解空間之情況下,所有問題在做 pso 時,會先把解空間定義出來,

如考慮 d=3 之情況下,各維度之解空間如下所述。

 

x1_min = -10 , x1_max = +10

x2_min = +5 , x2_max = +7

x3_min = -3 , x3_max = +4

 

而在做位置更新的時候

 

xid = xid + vid

 

是有機會發生逾界之情形,即可能

x11 = -12  --> 第1個粒子,第1個維度解小於下界,或

x23 = +8  --> 第2個粒子,第3個維度解大於上界。

當這些情況發生時,必須對該粒子之解空間進行調整,

常見的調整方式為


if (xid > xd_max) xid = xd_max;
if (xid < xd_min)  xid = xd_min;

 

但實作後發現,這種方式容易讓所有粒子最後集在中同一解上,

沒辦法得到很好的效果,於是較建議,若發生逾界情形時,

直接再給該粒子一隨機位置

 

if (xid > xd_max || xid < xd_min) xid = random(xd_min, xd_max)

 

粒子各維度速度限制

 

一開始在進入演算法前的 初始化 中,必須對粒子各維度之速度加以限制,

通常速度之極值限制如下

vd_max = xd_max - xd_min

以上述之範例為說明

 

x1_min = -10 , x1_max = +10 ---> v1_max = 10 - (-10) = 20

x2_min = +5 , x2_max = +7 ----> v2_max = 7 - 5 = 2

x3_min = -3 , x3_max = +4 -----> v3_max = 4 - (-3) = 7

 

這是一些國內文獻上提出的建議,但實際測試與分析下來,並不合理,

原因是這種設法速度嫌太大,容易會產生每個粒子會跑到解邊界 (xd_min, xd_max ) 現象,

但也不建議直接設常數進去。以上述 x1_min=-10,x1_max=10 為例,

合理可以設在 [0, 20] 之間,不建議直接設成 20,也不建議直接設成 10 等等之類的常數值,

較佳的作法應是以倍率方式下去做,即

 

vd_max = Rate * (xd_max - xd_min)

 

至於 Rate 要不要設 d 個 (即  double Rate[d]) ,個人是認為沒必要,統一一個數值即可。

在筆者進行的一些測試後,認為 Rate 可設成 [0.0001 , 0.05」會較佳,

但應視情況而定,Rate 該怎麼設。當 Rate 設高時,如上所述,容易達到邊界值;

但當 Rate 設低時,收斂速度變慢 ( 是不會說容易陷入 local solution),

在這情況下要找到最佳解需要較長的演化代數 (迭代次數)。

但必須注意,Rate 之設定上,必須注意會不會使得 vd_max 得到 0 ,

或使得 vd_max 趨近於 0 ,若使 vd_max 趨近於 0 ,整份 pso 演算法幾乎是沒用的。

 

速度更新使用之亂數

 

以原版之速度更新公式

vid = w * vid + c1 * rnd() * (pbest_xid - xid)  + c2 * rnd() * (gbest_xd-xid)

裡面提到的 rnd() 指的是產生 [0,1] 間之浮點亂數,這是原版 pso 所提用到的亂數,

因 pbest_xid - xid 與 gbest_xd - xid 都可能為正,也可能為負。

但分析下來,此時速度會是一定向,意即只會更負,或只會更正,

轉向之機會並不高,故較建議在設計上時,rnd() 將其設計成產生 [-1, 1] 間之浮點亂數,

日後以 rnd1() 表示。

 

速度更新限制

 

上述在說明,設定各維度速度上限時,有提到一個公式

 

vd_max = Rate * (xd_max - xd_min)

 

而粒子在更新速度時,vid 也可能會超過 vd_max ,

也由於 vid 可能是負的情況下,vid 也可能會小於 -vd_max。

與解空間逾界時的處理似,常見的手法是

 

if (vid > vd_max ) vid = vd_max;

if(vid < - vd_max) vid = -vd_max;

 

若是仿上述,在解空間逾界時的處理,可這麼進行

 

if( vid > vd_max || vid < -vid_max) vid = random( -vd_max, vd_max); /* A */

 

筆者在習慣上,在重新產生一新之速度時,不會讓速度生成為負值,進行方式如下

 

if( vid > vd_max || vid < -vid_max) vid = random( 0.0, vd_max); /* B */

 

A 與 B 這兩種方式實測過,差異並不大,唯筆者較慣用為 B 方式。

 

[回目錄]

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


留言列表 (11)

發表留言
  • 劍子仙跡
  • 先生您好~~
    我是中央大學博士...
    目前正在研讀其他前輩的論文期刊..
    其中有利用到pso搜尋法...
    論文有一個買賣雙方的聯合成本函數(非線性)
    其中包含4個變數...
    他的方法正是想利用pso搜尋法尋找最佳解,使得成本最小
    我想自己用電腦跑跑看....
    我該如何開頭..
    步驟需要注意什麼?
    謝謝您的解答...

    Jay Liang
  • Hi, Jay

    由於從您的留言上,我無法判定您是否有程式經驗,在此假設您沒有任何程式經驗回答。

    任何研究有用到演化式演算法(如基因、粒子、螞蟻等),都必需要會寫程式,至於要用什麼程式語言並不限定,因程式語言只是去解決問題的工具,甚至直接拉 excel 也可以 (但 excel 不寫 vba 較少為學術所接受)。

    若您閱到該論文期刊,欲「用自己電腦跑跑看」其方法,若該論文期刊有附上某種程式語言(如C、C#、VB、Java等)之程式碼或執行檔,則直接抓下來進行編譯、執行,當然還必須有一系列之輸入資料;若該論文期刊未附程式碼,應先確定其方法(演算法)之流程與步驟,愈詳細愈好,自行以任何程式語言實作之,並觀查結果。

    簡而言之,您需要的是
    (1) 確定其輸入資料來源 (或自行模擬輸入資料),但資源來源必須先進行初步有效性篩選,也包含了各屬性(構面)之相關性測試。
    (2) 對演算法流程必須熟悉,熟悉定義為:必須會自己用筆算。如聯合成本函數如何列式?裡面用了哪些變數?該從哪些資料取得?
    (3) 撰寫程式,故必須學習一種程式語言。

    程式語言非常多種,此處不一一舉出。目前大多用來寫演化式演算法的為 C/C++/C#,哪種程式語言並不影響演算法之結果(結果只由演算法之流程設計所影響),但程式語言之選擇會影響執行速度之快慢。

    以上建議,希望對您有所幫助。

    edisonx / edison.shih.

    edisonx 於 2011/12/19 16:41 回覆

  • 劍子仙跡
  • 謝謝您的回答~~

    我有寫程式的經驗~~,此篇論文是以C++ bulider6 撰寫,未附程式碼,
    他所有的資料都有提供,
    我的問題是 第一步驟是先進行未知參數值的搜尋?(此處是否就要利用pso)?
    還是其它我未注意的地方?

    Thanks
  • Hi, Jay :

    我想您應是對演化式演算法並不熟悉才有此惑。在所有演算式演算法裡,關於該演算法之所有參數「大多」都是 coder (or user) 自設,只有少數部份是必須視問題定義,其參數必須依問題定義計算出來,但 pso 在這部份真的少之又少。換而言之,pso 可變異之參數約 5 個左右,大多的作法是,這 5 個參數都設幾個代表值,如 Low, Mid, Up,如此一來便有 3^5 = 243 個參數可以跑,當然大多之情況是不會試這麼多參數值的。這部份之演算式演算法,算是被部份 cs 領域之學者所垢病之處,原因在於認為這種算法根本就是瞎貓碰到死耗子。(但巧妙的是,針對某些問題之某些演算法,能得到趨近於最佳解,這件事 "似乎" 有人證明過)。

    由於我已顯少翻閱文獻,但大多步驟不外乎是確定 fitness function (單目標 or 多目標 or 多目標化單目標 or 帕拉圖解集合)、確定限制式、套入問題,設計演化式演算法、多跑幾組演化式演算法之參數值。當然上述這些步驟,可由該專業背後之 know how 得到較佳之結果 (像是初值不用隨機選取,先以 Greedy theom. 取得部份初解也大有人在)。

    希望這次有回答到您的問題。

    edisonx 於 2011/12/19 23:15 回覆

  • 悄悄話
  • 劍子仙跡
  • 先生您好~~
    可以麻煩您看一下我的問題?
    http://tieba.baidu.com/p/1331347037

    我用手算的方式可以完全算出他的變數最佳值,並使成本最小
    但我現在的問題是,如何用電腦尋找變數的最佳值,使成本最小,
    他4個變數裡有相關的限制條件,K這個變數裏的條件又隱藏著Nm這個變數,
    好傷腦筋,我試了很久,一直產生錯誤
    麻煩您指點一下~~
    thanks
  • (接洽中...)

    edisonx 於 2011/12/23 23:06 回覆

  • novus
  • to 劍子仙跡

    如果你對C++還算熟練的話,建議你搜尋一下 ParadisEO,這個程式庫包含了大多數 EO、GA、PSO 的基礎建設,讓使用者可以迅速組裝出想要的演算法,對於需要進行大量實驗的研究頗有幫助。

    缺點是他的 tutorial 寫得很糟糕,你必須花點時間去 trace 範例和程式庫的原始碼才有辦法上手。
  • ParadisEO 還真是第一次聽過, novus 知道的 library 真多,每次聽到都為之驚艷。
    由於劍子仙跡情況較為特殊 (熟 Fortran,但研究必須以 C language 撰之),目前小弟已與劍子仙跡接洽聯繫 (#3 之悄悄話),希望能給予一點幫助。結案情況如何小弟後續自行回覆此篇 blog 回報。

    edisonx 於 2011/12/23 23:10 回覆

  • novus
  • 只不過有人問起,碰巧我略知一二而已,我不在乎別人的工作也不在乎幫不幫得上忙。現在除非是心情特別好或者是看不下去,不然我很懶得主動寫東西.....

    還有也建議你,寫個部落格而已,不需對任何人負責,不要給自己什麼壓力
  • 謝謝建議 :)

    edisonx 於 2011/12/24 21:11 回覆

  • edisonx

  • [劍子仙跡 後記]

    第一次接洽時,沒在有限時間內(約 12 小時) 將該問題解決出來,其實感到有些灰心 (雖有要求希望能再延長專案時間,但當下其實沒有把握,即使延長也能迎刃而解),畢竟是第一份沒解出來的案,讓人有點無法釋懷 ( 但其他的事還是正常運作便是 )。後續第二次接洽時,需求簡化,費時約十小時予以滿意之成果 (不知這算不算是雪恥)。

    此次接洽的心得是 (1) 我該強調,blog 能展現的只能是作者實作過的心得,對某方面、某事項的了解或紀錄,要從零開始,大致有三個選擇:找個人從頭到尾學習、外發包案、找本書從頭念到尾 (較沒急迫性時可選此項目)。(2) 大多之專案難度評估多為瓶頸技術所花費時間,但在非專業之 domain 時,徹底了解該問題前,並不適合對該專案進行太多評估。甚至保守之評估,應將難度提昇2至3倍才算合理。原因在於:進入該專案 domain 、徹底了解問題後,往往此時的瓶頸技術才會慢慢浮現,且該瓶頸技術往往嚇人。

    如果 劍子仙跡 沒在身旁解說變數與方程式,我想需要一星期左右才可順利結案。總之,結了第一次沒寫出來的案 (雖然它變得簡單了點),讓人放下了一些心。

    學一次經驗學一次乖 - novus 說得是對的。
  • chen
  • 請問一下,參考文獻在哪嗎?
  • 沒留。

    edisonx 於 2013/05/24 15:06 回覆

  • cai
  • 請問,以下這兩個選擇式,都是有發表出來,且證明可行的嗎?
    若有,可否告知,文章出處,或是相關的搜尋關鍵字,方便查詢!!
    if (xid > xd_max || xid < xd_min) xid = random(xd_min, xd_max)
    if( vid > vd_max || vid < -vid_max) vid = random( -vd_max, vd_max);
    以上
    萬分感謝
  • 這兩個式子並沒經過任何證明,純粹神來一筆覺得可以這麼搞。有沒有文獻講這個我就不清楚了。

    更清楚的說,其實一般文章(文獻)並不會特別強調,PSO 的解範圍超過預計時該怎麼處理(最扯的是看過不處理的 Code),故這部份我認為是視問題狀況,或 Coder 喜好。

    edisonx 於 2014/03/07 15:29 回覆

  • 訪客
  • 方便請問一下嘛,為什麼我的pso作出來,解都幾乎一樣??,感謝!!
  • 這情況還蠻正常的,到最後的解會收斂,只是比較難確保那個解是 Local Solution 還是 Global Solution...

    edisonx 於 2015/02/25 18:20 回覆

  • 想請問大大一下
  • 我對PSO算法大致了解,但對與寫程式方面不知如何下手,想問一下如何在短時間去學習某程式語言(較快學會的語言)寫出此PSO算法呢?還是有範例資料供參考,請指教謝謝!!
  • 我的 blog 上已有範例,或是你可到書局挑本書回來學。

    edisonx 於 2015/12/14 19:34 回覆

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

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

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

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

請輸入左方認證碼:

看不懂,換張圖

請輸入驗證碼