【Python】實現粒子群演算法(Particle Swarm Optimization, PSO) 解Rastrigin Function最小化問題
粒子群演算法(Particle Swarm Optimization)由J. Kennedy 和 R. C. Eberhart等人提出，屬於啟發式演算法目標在於搜尋近似最佳解，基於對於鳥群群體移動的觀察，模擬鳥群覓食行為。
粒子群演算法(Particle Swarm Optimization, PSO)，其模擬鳥群的行為建立在每隻鳥的局部感知上，鳥類會隨著自身的經驗，以及參考群體的最佳的經驗，去尋找出食物的確切位置，其優點為概念簡單，參數設置較少，方便實現，且可解大部分最佳化問題，缺點為容易陷入局部最佳解，由於可全域搜索，其收斂性較差，其解的精度不高。
本文會介紹PSO的概念以及原理，針對PSO本身參數以及PSO的流程加以解說，並用Python實現解Rastrigin Function最小化問題。
Rastrigin function:是一個非凸函數的測試函數(Test functions)，此函數尋找最小值是十分困難的，有許多的局部最佳解，且搜索空間很大。
本文選用二維的Rastrigin function來測試我們的PSO演算法，在此這裡A=10 n=2 且Xi ∈[-5.12,5.12]，x=0 時有全域最小解f(x)=0，其公式以及圖片如下:
粒子群演算法(Particle Swarm Optimization, PSO)
概念:利用鳥類群體覓食的原理，鳥類個體可以通過一些自我評估的規則判斷位置的好壞，並且找到自己最好的位置，然而每一隻鳥類都會透過這種方式，找尋到自己最好的位置，然而群體中找到最好的位置就是我們所找尋的食物的所在地。
步驟:
1. 初始起始位置(pos)、速度(v)以及粒子
2. 計算目標函數，求出目標值(obj_val)
3. 紀錄局部最佳解(pbest)以及全域最佳解(gbest)
4. 計算速度(vel)將其粒子更新位置
5. 更新局部最佳解((pbest))以及全域最佳解(gbest)
6. 最後重複2~3步驟
Python程式碼實作
(一) 參數、函數設定
1. Dim:解的維度，變數的數量
2. pop_size :母體大小，粒子的數量，也就是族群中鳥的數量
3. w_it_max:最大的慣性權重，其影響速度的大小。
4. w_it_min: 最小的慣性權重，其影響速度的大小。
5. c1 / c2: 學習因子，決定粒子本身經驗與群體的經驗對運動軌跡的影響，調整可以減少局部最小值以及解決收斂速度慢的困擾，一般範圍為[1,2.5]。
6. max_iter:最大迭代次數
7. Lb: 解的下界，在Rastrigin function為 Xi∈[-5.12,5.12]
8. Ub: 解的上界，在Rastrigin function為 Xi∈[-5.12,5.12]
9. fun: 目標函式為Rastrigin function(2D)其公式如下:
(二) 初始起始位置(pos)、速度(vel)
1. 利用上下界隨機初始化位置
2. 隨機初始化速度
(三)計算目標函數，求出目標值(obj_val)並且記錄解
1. 求出目標值(obj_val)
2. 紀錄局部最佳解(pbest)以及全域最佳解(gbest)
(四) 計算速度(vel)將其粒子更新位置
1. 利用線性遞減的方式計算慣性權重(w)
2. 利用慣性權重以及隨機變數來更新速度(vel)，公式如下
3. 更新粒子位置(pos)，公式以及示意圖如下
(五)更新局部最佳解((pbest))以及全域最佳解(gbest)
1.紀錄每一個點的最佳位置，並找出局部最佳
2.從記錄中的局部最中找出全域最佳解
程式運行結果:
最後運行結果為如下，[x1,x2]=[ 4.86256190e-10 -1.54326018e-09]時有最小值為0，粒子群演算法在解Rastrigin function的效果還是不錯的，可以發現很快可以找出全域最小值，下圖為運行結果以及每次迭代中最小值。
結語:這次分享的演算法是利用觀察鳥群覓食所發展出來的粒子群演算法(PSO)，其概念簡單且容易實作，實用性廣泛，可以解很多最佳化問題，以上為整理的學習筆記，有疏忽遺漏的歡迎指正。
•全部程式碼
