旅行銷售員問題是很經典的NP問題，隨著問題中城市數的增加，所需的計算時間會大幅增加，終至難以計算。近年來模擬自然的優化算法陸續被提出，如模擬退火法與蟻群演算法，此兩方法都可以用來求解旅行銷售員問題。
　　以單一的演算法求解旅行銷售員問題的效率可能有限，本論文詳細探討如何設定模擬退火法及蟻群演算法的參數，比較兩者呈現在不同規模的TSP範例的結果，最後討論將模擬退火法與蟻群演算法結合的可能性，期望對求解旅行銷售員問題有所突破。

The traveling salesman problem is a classic NP problem. As the number of cities in the problem increases, the required computing time will increase significantly, and it will eventually become difficult to proceed the computation. In recent years, several famous nature-inspired optimization algorithms have been proposed, such as simulated annealing and ant colony optimization. Both of them can be used to solve the traveling salesman problem.
The efficiency of solving the traveling salesman problem with a single algorithm may be limited. In this thesis, we study in detail how to set the parameters of simulated annealing and ant colony optimization, and compare the results of the two algorithms for TSP instances of different scales. Finally, we discuss the possibility of combining stimulated annealing with ant colony optimization, which, if successful, is expected to make a breakthrough in solving the traveling salesman problem.

Chapter 1　導論 1
Chapter 2　計算方法 5
2.1　旅行銷售員問題 5
2.2　旅行銷售員問題求解方法 6
2.3　蒙地卡羅模擬 7
2.4　Metropolis演算法 8
2.5　模擬退火法 10
2.5.1　模擬退火原理 10
2.5.2　降溫策略 11
2.6　蟻群演算法 12
2.6.1　螞蟻的特性，社會型態與群體行為 12
2.6.2　蟻群演算法源起 13
2.6.3　模擬螞蟻與真實螞蟻之異同 13
2.6.4　躍遷機率 14
2.6.5　費洛蒙更新 16
2.6.6　蟻群算法的改進: 最大最小螞蟻系統 17
Chapter 3　實驗結果 19
3.1　SA與ACO的實驗結果 19
3.1.1　SA實驗結果 20
3.1.2　ACO實驗結果 21
3.2　SA參數設定 23
3.2.1　初始溫度 24
3.2.2　降溫係數k 28
3.2.3　模擬次數 29
3.3　 ACO參數設定 31
3.3.1　螞蟻數量 32
3.3.2　影響距離的參數β 34
3.3.3　費洛蒙揮發濃度ρ 35
3.4　實驗結果之比較 37
Chapter 4　結論與討論 41
附錄A　ACO Mathematica 程式碼 45
附錄B　SA Mathematica 程式碼 49
參考文獻 51

[1] J. H. Holland, Adaptation in natural and artificial system. (The University of Michigan Press, 1975).
[2] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Optimization by simulated annealing, Science 220, 671 (1983).
[3] E. H. L. Aarts and P. J. M. van Laarhoven, Simulated annealing: Theory and applications (Reidel, 1987).
[4] M. Dorigo, A. Colorni, and V. Maniezzo, Distributed optimization by ant colonies, in Proc. ECAL91,134 (1991).
[5] M. Dorigo, Optimization, learning and natural algorithms (Ph.D thesis, Politecnico di Milano, 1992).
[6] M. Dorigo, V. Maniezzo, and A. Colorni, Ant system: Optimization by a colony of cooperating agents, IEEE Trans. Sys., Man, and Cyber. B 26, 29 (1996).
[7] M. Dorigo and T. Stutzle, Ant colony optimization (MIT Press, 2004).
[8] M. Dorigo and L. M. Gambardella, Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Trans. Evolu. Comp. 1, 53 (1997).
[9] M. Dorigo and L. M. Gambardella, Ant colonies for the traveling salesman problem, BioSystems 43, 73 (1997).
[10] C. Blum, Ant colony optimization: Introduction and recent trends, Phys. Life Rev. 2, 353 (2005).
[11] 段海濱, 蟻群算法原理及其應用 (科學出版社, 北京, 2005).
[12] 馬振, 青島理工大學碩士論文 (2016).
[13] 鮑文杰, 浙江師範大學碩士論文 (2016).
[14] D. Applegate, R. E. Bixby, V. Chvátal, and W. Cook, The traveling salesman problem: A computational study (Princeton University Press, 2006).
[15] M. R. Gray and D. S. Johnson, Computer and intractability: A guide to the theory of NP-completenes (Freeman, 1979).
[16] G. Reinelt, TSPLIB—A Traveling Salesman Problem Library. ORSA J. Comp. 3, 376 (1991).
[17] D. P. Landau and K. Binder, A guide to Monte Carlo simulations in statistical physics (Cambridge University Press, 2014).
[18] K. Binder and D. W. Heermann, Monte Carlo simulation in statistical physics: An introduction (Springer, 2019).
[19]N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller, Equation of state calculation by fast computing machines, J. Chem. Phys. 21, 1087 (1953).
[20] A. Basu and L. N. Frazer, Rapid determination of the critical temperature in simulated annealing inversion, Science 249, 1409 (1990).
[21] W. Cai and L. Ma, Applications of critical temperature in minimizing functions of continuous variables with simulated annealing algorithm, Comp. Phys. Comm. 181, 11 (2010).
[22] D. M. Chitty, Applying ACO to Large Scale TSP Instances, in Advances in Computational Intelligence Systems, F. Chao et al. eds (Springer, 2018).
[23] T. Stutzle and M. Dorigo, ACO algorithms for the traveling salesman problem, in Recent Advances in Genetic Algorithms, Evolution Strategies, Evolutionary Programming, Genetic Programming and Industrial Applications, K. Miettinen et al. eds (John Wiley & Sons, 1999).