[回目錄]

 

[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 發表在 痞客邦 留言(11) 人氣()