Edison.X. Blog

[回目錄]

 

在 [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 方式。

 

[回目錄]