學習堅持，堅持學習

何謂「粒子群演算法」

「粒子群演算法」是人類觀察鳥類覓食行為所發展出來的演算法

在「粒子群演算法」中一個粒子代表鳥群中的一隻鳥

各個粒子具有「記憶性」並會參考其它粒子的「訊息」來決定移動的方向

 

「粒子群演算法」能做什麼

和「基因演算法」一樣「粒子群演算法」同樣是拿來解決最佳化問題的工具

 

那又什麼叫最佳化問題?

以下給出幾種例子

1. 旅行推銷員問題
2. 工作排程問題

從「旅行推銷員問題」來看
我們可以隨便決定一條路線 (城市的先後順序)，
而這條路線會對應到一段距離 (歷經全部城市所需要的距離)
目標就是找到一條路線，
並且這條路線對應到的距離是最短的

而「工作排程問題」也是差不多的
我們有n個工作及m台機器
每個工作在每台機器上的執行時間可能有所不同
因此我們需要搜尋一個工作分配方式
所需要花費的時間最短

對這類問題通常對會有一個最大的問題

就是要將全部可行的解 (路徑or工作分配方式) 在有限時間內計算完畢是不可能的

而此類問題大部份也都可能是個NP問題

 

而「粒子群演算法」就是為了解決這種問題的工具

但做為折衷方案「粒子群演算法」找到的解不保證是最佳解 (可能只是次佳解)

 

從數學的表示來看

對於「旅行推銷員問題」

x 代表著某一條路徑

f(x) 代表這條路徑的距離

而目標就是找到一個x所對應的 f(x) 最小

很明顯的 x 就是我們要求解的變數

也可以說 x 是我們要最佳化的參數

 

「粒子群演算法」採用哪些鳥類覓食的觀念?

「粒子群演算法」主要採用了下列兩個觀念

1. 依照自身經驗決定飛行方向
2. 參考別人的經驗決定飛行方向

這兩件事就像人類的學習過程

人類在處理事情時，通常都會依照自己的方法

當我們發現有人的方法比自己的方法更好，就會參考並學習該方法

 

對於單個粒子的行為是不可預測的 (也就是我們不確定這個粒子找到的方法會越來越好還是越來越差)

但群體的行為確是可以預測的 (因為各個粒子會參考其它粒子的訊息)

並且粒子是依照「發現別人比自己更好，就會參考並學習」

因此我們可以認為全部的粒子會漸漸的往較好的方向前進

用圖說明如下 (下圖為示意圖，粒子真正在移動並不是只有兩個力來決定，詳細請看「粒子」的移動方式)

 
                粒子位置及方向                                粒子參考群體的資訊                                            

 經過移動後的粒子位置
                          

 

「粒子」的移動方式?

一個粒子的移動方向可以用下圖表示

也就是說：粒子目前的方向 = 粒子上個時間的方向 + 自己認為的最佳方向 + 群體認為的最佳方向
(從這邊我們可以小小的呼應上節所說明「群體的行為是可以預測的」，因為所有粒子都會參考群體認為的最佳方向的所以都會漸漸向這個方向前進)

用數學來表達上面的動作：

各個顏色分別代表對應的方向

從速度的更新式來看

我們可以調整c1、c2來改變粒子依賴「自身最佳位置」和「群體最佳位置」的程度
(c1、c2在原文中是寫contant但我個人比較偏好說是一個權重，畢竟在後面變種的粒子群演算法，c1、c2不一定是一個常數)

而後來的標準版的粒子群演算法中更加入了慣性權重：

因此除了「自身最佳位置」、「群體最佳位置」外還可以調整自己本身的權重

 

「粒子群演算法」的流程

知道了每個粒子的移動方式

接著讓我們看一下「粒子群演算法」的完整流程

1. 使用亂數初始化粒子的位置、速度
    
2. 利用適應函數來評估每個粒子的適應值
    
3. 利用評估後的粒子來更新「粒子自身最佳位置」、「群體最佳位置」
    
4. 用「速度更新式」、「位置更新式」來移動粒子
    
5. 確定是否收斂或達到停止條件?  
   Yes => 輸出結果
   No   => step 2.

 

覓食行為和適應函數的關係?

「粒子」最終要往什麼位置前進?

「粒子群演算法」是觀際鳥類覓食所發展出來的

也就是說鳥類會移動往具有最豐富食物來源的地方

食物越多的位置越好

對應到「旅行推銷員問題」路徑越短 = 食物越多

對應到「工作排程問題」花費時間越少 = 食物越多

在不同的問題上食物越多代表的意思是不同的

所以我們需要設計一個適應函數

利用適應函數來告訴我們某一個位置的食物多寡 (等同於路徑長度、花費時間…)

利用數學表示：

這樣我們才能知道某個粒子目前位置的好壞

 

「粒子最佳位置」代表?與解的關係?

知道了食物和適應函數的關係

那粒子的位置又代表什麼呢?

我們用下圖來了解 (旅行推銷員問題)

所以粒子的位置 != 解的實際形式

鄰近的粒子也不保證解是相似的

粒子的位置經過解碼 = 解的實際形式

事實上粒子的位置不代表任何實質的東西

 

「基因演算法」和「粒子群演算法」?

最後如果有看上一篇「基因演算法」

或許會覺得「基因演算法」和「粒子群演算法」有和差別?

以下給出一些個人的觀點

1. 他們本質上根本沒有差別 (因為他們都是解決最佳化問題的工具)
    
2. 「基因演算法」具有隨機搜尋的能力 (突變步驟)，而「粒子群演算法」沒有 (粒子的移動都是有所根據，自身或是群體經驗)
    
3. 「基因演算法」具有淘汰機制 (選擇、複製步驟)，而「粒子群演算法」並不會淘汱粒子

好像上面有點寫的太簡短了補充一下

 

1. 都是解決最佳化問題的工具
2. 「找尋解的過程基本上都沒有數學根據」，如梯度下降 (所以叫啟發式?)

 

 

 

 

新手發文如有錯誤，煩請指正！