今天是連假的第二天
又是一個美好的週五
接下來兩天會跟大家介紹跟基因演算法(遺傳演算法)相關的演算法

今天跟各位介紹的是蟻群演算法

蟻群演算法

蟻群演算法（Ant Colony Optimization, ACO），又叫『螞蟻演算法』

• 一種用來在圖中尋找優化路徑的機率型演算法。
• 由Marco Dorigo於1992年在他的博士論文中提出，靈感來自於螞蟻在尋找食物過程中發現路徑的行為。
• 屬於啟發式演算法的一種

蟻群演算法是一種類比進化演算法，初步的研究表明該演算法具有許多優良的性質。針對PID控制器參數最佳化設計問題，將蟻群演算法設計的結果與遺傳演算法設計的結果進行了比較，數值仿真結果表明，蟻群演算法具有一種新的類比進化最佳化方法的有效性和應用價值。

螞蟻在路徑上前進時會根據前邊走過的螞蟻所留下的分泌物選擇其要走的路徑。其選擇一條路徑的概率與該路徑上分泌物的強度成正比。因此，由大量螞蟻組成的群體的集體行為實際上構成一種學習資訊的正反饋現象：某一條路徑走過的螞蟻越多，後面的螞蟻選擇該路徑的可能性就越大。螞蟻的個體間通過這種資訊的交流尋求通向食物的最短路徑。

蟻群演算法就是根據這一特點，通過模仿螞蟻的行為，從而實現尋優。當程式最開始找到目標的時候，路徑幾乎不可能是最優的，甚至可能是包含了無數錯誤的選擇而極度冗長的。但是，程式可以通過螞蟻尋找食物的時候的資訊素原理，不斷地去修正原來的路線，使整個路線越來越短，最終找到最佳路線。

虛擬碼(Pseudo code)

Algorithm ACO_MetaHeuristic
   while(not_termination)
      generateSolutions()
      daemonActions()
      pheromoneUpdate()
   end while
end Algorithm

變化型態

1. 精英螞蟻系統

2. 最大最小螞蟻系統（MMAS）

3. 蟻群系統

4. 基於排序的螞蟻系統（ASrank）

5. 連續正交蟻群（COAC）

相關資料：
維基百科-蟻群演算法
蟻群演算法、遺傳演算法、模擬退火演算法介紹 | 程式前沿
蟻群優化演算法 (Ant Colony Optimization) - 陳鍾誠的網站