Particle Swarm Optimization(PSO) Department of Industrial Engineering and Management Particle Swarm Optimization(PSO) 粒子群演算法 Speaker:Jar-Her Kao November 23,2004 IEM Monograph November 23,2004 IEM Monograph Department of Industrial Engineering and Management
報告大綱 簡介 特點 演算法介紹 演算法流程 速度更新函數 參數設定 結論
簡介 起源 原理 生物社會學家對鳥群尋找食物行為的研究 我們可以設想這樣的一個場景，一群鳥再隨機搜尋食物。這個區域裡只有一塊食物。所有的鳥都不知道食物再哪裡，但他們知道目前距離食物還有多遠，那麼找到食物的最佳策略是什麼？最簡單的方法就是找尋距離食物最近的鳥之周圍區域及根據自己本身飛行的經驗判斷食物的所在。
鳥群的覓食行為 Food Global Best Solution Past Best Solution
特點 分散式搜尋 具記憶性 元件較少，容易實現 適合在連續性的範圍內搜尋
演算法介紹 每個尋優的問題解都被想像成一隻鳥，我們也稱為“Particle”粒子。 所有的Particle 都有一個fitness function 以判斷目前的位置之好壞。 每一個Particle必須賦予記憶性，能記得所搜尋到最佳位置。 每一個Particle 還有一個速度以決定飛行的距離與方向。
演算法流程 Initial： Evaluation： Fine the Pbest： Fine the Gbest： 將群族做初始化，以隨機的方式求出每一Particle 之初始位置與速度。 Evaluation： 依據fitness function 計算出其fitness value 以作為判斷每一Particle之好壞。 Fine the Pbest： 找出每一Particle 到目前為止的搜尋過程中最佳解，這個最佳解我們將之稱為Pbest。 Fine the Gbest： 找出所有Particle 到目前為止所搜尋到的整體最佳解，此最佳解我們稱之為Gbest。 Update the Velocity： 依據式(1) 與式(2) 更新每一Particle之速度與位置。 回到步驟2. 繼續執行，直到獲得一個令人滿意的結果或符合終止條件為止。
1. Initial 將群族做初始化，以隨機的方式求出每一Particle 之初始位置與速度，這些隨機的Particle限定在規定的範圍內。
2. 速度更新函數 Vid ：每一Particle在第d維之速度 i：Particle之編號 d：維度 w ：Inertia Weight c1、c2：學習常數 Rand()：一介於0至1的亂數 Pid ：每一Particle到目前為止，所出現的最佳位置 Pgd ：所有Particle到目前為止，所出現的最佳位置 xid ：每一Particle目前之所在
3.更新位置 粒子群內的每一個粒子點更新如下公式 更新之後的點也必須限定在規定範圍內
4.記憶更新 在符合限制下，更新Pid Pgd Pid ← pi IF f(p i) > Pid Pgd ← pi IF f(p i) > Pgd f (x) 是一個目標函數受限於最大化
5.終止條件 重複步驟２到４直到達到中止條件 最後會得到Pgd 而f(Pgd) 就是解的結果
參數設定 c1、c2：學習常數一般設定為 不過在文獻中也有其他的取值，一般設定c1 = c2 值介於0~4之間 粒子數：一般取 20 ~ 40個，大部分的問題用10 ~ 20個粒子就能取的不錯的結果。 Vmax ：最大速度，決定粒子再一個循環中最大的移動距離 例如: 問題fitness function : f(x)= x12+x22+x32 其中限制式為 -10<= x1, x2, x3 <= 10 則Vmax 的大小就是10-(-10) = 20
結論 簡單的概念 容易實做 運算效能佳 未來可發展: 模糊粒子群 平行粒子群 排程方面的應用 糢糊類神經的訓練
國內目前已有的文獻 演化式模糊系統及其硬體的實現 混合階層式遺傳演算法與粒子群優演算法之資料分群技術 應用粒子最佳演算法於發電機組維修排程之研究 利用PSO演算法探討高速銑削最佳化 Nelder-Mead 搜尋法處理無限制式及隨機最佳化問題之研究 質群演算法(PSO)於多組解方程最佳化問題之研究 以粒子群最佳化為基礎之電腦遊戲角色設計之研究 供應商產能有限及價格折扣下多產品多供應商最佳化採購決策 一個智慧型指紋辨識系統的設計方法論 資料來源：全國碩博士網