蟻群最佳化

蟻群最佳化（Ant Colony Optimization，ACO）由 Marco Dorigo 在 1992 年提出，靈感來自螞蟻找食物的行為。螞蟻視力很差，卻能找出巢與食物之間的最短路徑，靠的是費洛蒙（pheromone）：螞蟻走過會留下費洛蒙，後面的螞蟻傾向走費洛蒙濃的路，而費洛蒙會隨時間蒸發。

著名的雙橋實驗：巢與食物之間有一長一短兩條路。一開始螞蟻隨機選，但走短路的螞蟻來回比較快，單位時間內短路上經過的螞蟻多、累積的費洛蒙也多；越多螞蟻因此選短路，又留下更多費洛蒙——這種正回饋加上蒸發「遺忘」舊資訊，最後幾乎所有螞蟻都走短路。

Ant System：解旅行推銷員問題 Ant System for the TSP

旅行推銷員問題（TSP）：給定 \(n\) 個城市，找一條每個城市剛好經過一次、最後回到起點的最短路線。城市一多，可能的路線數 \((n-1)!/2\) 爆炸性成長（10 個城市就有 181 440 條），無法一一比較。Ant System 讓 \(m\) 隻螞蟻反覆建構路線：

1. 每隻螞蟻從隨機城市出發，在城市 \(i\) 時，以下列機率選擇還沒去過的城市 \(j\)： $$p_{ij} = \frac{\tau_{ij}^{\,\alpha}\,\eta_{ij}^{\,\beta}}{\sum_{l \in \text{未去過}} \tau_{il}^{\,\alpha}\,\eta_{il}^{\,\beta}},\qquad \eta_{ij} = \frac{1}{d_{ij}}$$ 其中 \(\tau_{ij}\) 是邊 \(ij\) 上的費洛蒙，\(\eta_{ij}\) 是「能見度」（距離越近越有吸引力），\(\alpha\)、\(\beta\) 決定兩者的相對比重。
2. 所有螞蟻走完一輪後，費洛蒙先蒸發，再由每隻螞蟻在自己走過的邊上留下費洛蒙，路線越短留下越多： $$\tau_{ij} \leftarrow (1-\rho)\,\tau_{ij} + \sum_{k=1}^{m} \Delta\tau_{ij}^{k},\qquad \Delta\tau_{ij}^{k} = \begin{cases} Q/L_k, & \text{螞蟻 } k \text{ 走過邊 } ij \\ 0, & \text{其他} \end{cases}$$ \(\rho\) 是蒸發率，\(L_k\) 是第 \(k\) 隻螞蟻的路線總長。
3. 重複到指定的輪數，記錄找到過的最短路線。

• 預設參數（\(\alpha\) = 1、\(\beta\) = 2、\(\rho\) = 0.5）重複 100 次，每次都在 60 輪內找到最短路線 3.0916（verify_pso.py 以窮舉 181 440 條路線核對）。
• \(\beta\) = 0：螞蟻完全不看距離，只靠費洛蒙，一開始等於亂走；60 輪後的平均最短路線 3.48，比 \(\beta\) = 2 的 3.09 差很多。
• \(\alpha\) = 0：完全不看費洛蒙，等於「每一步都走最近的城市」的貪婪法加上隨機性，沒有群體學習。
• \(\rho\) 太小：舊的費洛蒙忘不掉，早期的壞路線影響很久；太大：好路線也很快被忘記。

和 GA、PSO 一樣，ACO 也是以族群為基礎、帶隨機性的最佳化方法；但它特別適合「路徑、排程、組合」這類離散問題，在控制領域可用於機器人路徑規劃、生產排程，也有人用來搜尋 PID 或模糊控制器的參數。

延伸閱讀：Ant Colony Optimization（M. Dorigo）↗（原講義連結的舊網址已改為這個目錄）。