調適型螞蟻演算法應用於旅行推銷員問題之研究

Adaptive Ant Colony System for Solving the Traveling Salesman Problem

螞蟻演算法為近年來廣被探討的一種巨集啟發式方法，也被統稱為螞蟻群落最佳化（ACO）方法。ACO已被成功應用於求解許多複雜的組合最佳化問題上，並衍生出多種不同的執行機制，例如：AS、ACS、Ant-Q、Max-Min AS與ASrank，這些執行機制的主要差異在於路徑搜尋機制與費洛蒙更新機制兩個部分。本研究之目的即針對ACO的路徑搜尋機制及其控制參數設定進行深入研究，提出一個調適型螞蟻演算法（AACS）的執行機制，並提出兩種改良式的費洛蒙更新機制，然後選擇24個旅行推銷員問題的國際標竿例題（題目規模500個節點以下），進行解題績效的比較分析。測試結果顯示：與文獻已知最佳解相比，AACS的平均誤差僅為0.46％，兩種改良式ACS的平均誤差分別為0.55％及0.47％，皆優於傳統的ACS，顯示本研究所提出的改良機制確實能有效提升ACO的解題績效。

The Ant Algorithm, also named as Ant Colony Optimization (ACO), is recently a famous meta-heuristic approach that has been successfully applied to solve many complicated Combinatorial Optimization Problems. Furthermore, several variants of the Ant Algorithm, such as Ant System (AS), Ant Colony System (ACS), Ant-Q, Max-Min AS (MMAS) and Rank-based AS (ASrank), have been proposed. These variants mainly differ in the routes searching mechanism and the pheromone update mechanism. Therefore, this paper aims to present an Adaptive ACS (AACS) as well as two modified pheromone update mechanisms for ACS (MACS1 and MACS2). We selected 24 TSP benchmark instances to test and analyze the performance of AACS, MACS1 and MACS2. The average percentages of errors among 24 TSP instances are 0.46% for AACS, 0.55% for MACS1 and 0.47% for MACS2. In summary, computational results imply that our proposed AACS and MACSs are capable of improving the performance of traditional ACS.