粒子群最佳化
粒子群最佳化（Particle Swarm Optimization，PSO）是 Eberhart 與 Kennedy 在 1995 年提出、以族群為基礎的隨機最佳化方法，靈感來自鳥群覓食與魚群游動的社會行為。（說明依原講義改寫）
想像一群鳥在某個區域隨機找食物，區域裡只有一處食物，沒有一隻鳥知道食物在哪裡，但每隻鳥都知道自己離食物有多遠。最有效的策略是什麼？跟著離食物最近的那隻鳥飛過去，同時也記得自己曾經到過最近的地方。
PSO 就把這個情境用在最佳化上：每一個候選解是搜尋空間中的一隻「鳥」，稱為粒子（particle）。每個粒子有一個由適應函數算出的適應值，以及決定飛行方向的速度。一開始隨機產生一群粒子，之後每一代（iteration）每個粒子都依兩個「最佳值」調整速度：
- pBest：這個粒子到目前為止找到的最佳位置（自己的經驗）。
- gBest：整個族群到目前為止找到的最佳位置（群體的經驗）。
速度與位置的更新 Update Rules
記第 \(q\) 代第 \(j\) 個粒子的位置為 \(\mathbf{x}_j^q = [x_{j,1}^q\;\, x_{j,2}^q\;\cdots\; x_{j,n}^q]\)（\(n\) 個變數），速度為 \(\mathbf{v}_j^q\)，則
$$\mathbf{v}_j^{q+1} = w\,\mathbf{v}_j^q + c_1\,r_1\,(\mathbf{gBest}^q - \mathbf{x}_j^q) + c_2\,r_2\,(\mathbf{pBest}_j^q - \mathbf{x}_j^q)$$ $$\mathbf{x}_j^{q+1} = \mathbf{x}_j^q + \mathbf{v}_j^{q+1}\,\Delta t,\qquad \Delta t = 1$$- \(r_1, r_2\)：每次重新產生的 0～1 亂數（原講義寫作 rand()），讓粒子的行為帶點隨機性。
- \(c_1, c_2\)：加速常數，決定被 gBest、pBest 拉過去的強弱，常取 2。
- \(w\)：慣性權重，保留多少上一代的速度。原講義投影片的公式沒有 \(w\)（等於 \(w = 1\)，即 1995 年的原始版本）；附檔 Matlab 範例則用 Shi 與 Eberhart 在 1998 年提出的慣性權重，從 0.9 線性遞減到 0.4——前期大、到處探索，後期小、在好區域內細找。（補充）
- 另外通常限制速度不超過 \(V_{max}\)（範例取搜尋範圍的一半），並把飛出範圍的粒子拉回邊界。
把 \(m\) 個粒子排成矩陣，就能一次更新整個族群：\([X^{q+1}]_{m\times n} = [X^q]_{m\times n} + [V^q]_{m\times n}\,\Delta t\)，第 \(j\) 列是第 \(j\) 個粒子。
編註：原講義 gBest／pBest 定義圖中，\(pBest_j\) 的第二個分量寫成 \(Y_{gBest,j}\)，應為 \(Y_{pBest,j}\)。另外常見教科書多把 \(c_1\) 配 pBest、\(c_2\) 配 gBest，原講義與附檔程式剛好相反；兩者通常取相同的值，結果沒有差別。
演算法流程 Pseudo Code
每個粒子：隨機初始化位置與速度
重複
每個粒子：
計算適應值
若比自己的 pBest 好，更新 pBest
在所有粒子中取適應值最好的當 gBest
每個粒子：
依上式更新速度（並限制在 ±Vmax 內）
更新位置（超出範圍則拉回邊界）
直到 達到最大代數 或 誤差夠小互動示範 Watch the Swarm
（補充）照原講義 Matlab 範例二的設定：求 \(f(x,y) = x\sin(4x) + 1.1\,y\sin(2y)\) 在 \(0 \le x, y \le 10\) 的最小值（程式以適應值 \(=-f\) 轉成最大化）：
- 和 GA 比較：PSO 沒有交配、突變，只靠「記憶＋跟隨」，粒子沿著連續的軌跡飛，直接在實數空間搜尋，不需要二進位編碼。
- \(w\) = 1：沒有慣性衰減，粒子一直在 \(\pm V_{max}\) 之間來回衝，很難穩定下來；遞減的 \(w\) 讓粒子先探索、後收斂。模擬 200 次，40 代內找到最小值的比例：\(w\) 遞減 94%，\(w\) = 1 只有 3%。
編註：附檔程式限制速度時只檢查
if V(j,i) > Vmax(i)，沒有處理負方向，往左、往下飛的粒子速度可以遠超過 \(V_{max}\)（模擬中出現 −22，而 \(V_{max}\) = 5）。應改為 V(j,i) = max(-Vmax(i), min(Vmax(i), V(j,i)))。另外 fit_pbest 的初值是 0、pbest 是 (0, 0)：粒子若一直待在適應值為負的地方，pBest 就停在 (0, 0)，速度公式會把它往那裡拉；應讓 pBest 從粒子的起點開始。
用照原程式逐行改寫的版本（Colab 筆記本第 3 節）各跑 200 次，40 代內找到最小值的比例：原程式 81%、只改雙向限制 76.5%、只改 pBest 初值 83.5%、兩個都改 83%。最大的差距 7 個百分點，還沒超過兩種寫法比較時約 8 個百分點的顯著門檻（2 倍標準誤），差別不顯著。所以修正的理由是讓程式符合演算法的原意，而不是在這個例子上一定比較好。上面的互動示範採兩個都修正的寫法（每個方向各抽一個亂數）。Python 版 Colab Notebook
▶ 在 Colab 開啟原課程的 MATLAB 程式已改寫成 Python 筆記本（四支動畫程式：範例一、二的等高線與 3D 曲面動畫，以及原程式兩個問題的 200 次統計），可以直接在瀏覽器執行、修改參數。⬇ 下載 PSO.ipynb
附檔與延伸閱讀 Files
- Matlab 範例（PSO animations.zip）：範例一求 \(-20\sin r/r\)（\(r = 0.1+\sqrt{(x-4)^2+(y-4)^2}\)）的最小值，答案在 (4, 4)、\(f\) = −19.9667；範例二即上面的函數，答案 (9.039, 8.668)、\(f\) = −18.5547。每個範例都有等高線圖與 3D 曲面兩種動畫版本。
- PSO 中文教學（PDF）、Particle Swarm Optimization（PPT）、PSO 與 GA 混合（PDF）。
- swarmintelligence.org ↗（PSO 教學網站）。原講義另列 Eberhart《Swarm Intelligence》一書的網頁，該網域已不存在。
原圖對照
