旅行推銷員問題是一個重要的研究主題，該問題描述著一個推銷員試著探訪所有的城鎮，其中每個城鎮只能被探訪一次，且該推銷員所探訪城鎮順序所形成的路徑長度須為最短。本論文根據遺傳演算法、螞蟻演算法、粒子演算法及模擬退火演算法提出兩個處理旅行推銷員問題之新方法。在本論文的第一個方法中，我們根據遺傳演算法及螞蟻演算法提出一個新方法以處理旅行推銷員問題。我們使用螞蟻演算法來產生遺傳演算法的初始解，再利用遺傳演算法找尋更優秀的解。在本論文的第二個方法中，我們將第一個方法作改進，利用螞蟻演算法產生遺傳演算法的初始解，再用遺傳演算法找尋更優秀的解，其中，以模擬退火演算法來處理遺傳演算法的突變運算，並利用粒子演算法來交換螞蟻演算法中的各螞蟻群的費洛蒙，以避免落入局部最佳解。本論文所提之兩個新方法均比目前已存在之方法具有更好的平均解。

The traveling salesman problem is an important research topic. In the traveling salesman problem, a traveling salesman wants to travel all cities and each city only can be visited once. The problem is to minimize the distance of the complete route in which the salesman takes. In this thesis, we present two new methods for solving the traveling salesman problem using the genetic algorithms, ant colony system, particle swarm optimization and the simulated annealing algorithm. In the first method, we present a new method combining the genetic algorithms and the ant colony system to solve the traveling salesman problems. We use the ant colony system to generate the initial solutions for the genetic algorithms and then use the genetic algorithms to search the better solutions. In the second method, we improve the first method by using the simulated annealing algorithm to perform the mutation operation of the genetic algorithms and use the particle swarm optimization techniques to communicate the pheromone information among different ant groups of the ant colony system. We use the ant colony system to generate the initial solutions for the genetic algorithms and then perform the genetic algorithm with simulated annealing mutation operation to prevent the system fall into the local minimum and then use the particle swarm optimization to communicate the pheromone information among different ant groups of the ant colony system to speed up the converge process. The proposed methods get the better average solutions than the existing methods.

[1] N. Adachi and Y. Yoshida, “Accelerating genetic algorithms: protected chromosomes and parallel processing,” in Proceedings of the First International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications, Sheffield, UK, no. 414, pp. 76-81, 1995.
[2] B. Angeniol, G. D. L. C. Vaubois and J. Y. L. Texier, “Self-organizing feature maps and the traveling salesman problem,” Neural Networks, vol. 1, no. 4, pp. 289-293, 1988.
[3] D. L. Applegate, R. E. Bixby, V. Chvtal, and W. J. Cook, The Traveling Salesman Problem: A Computational Study, Princeton Series in Applied Mathematics, New Jersey, 2006.
[4] N. Aras, B. J. Oommen, V. Chvatal, and W. Cook, “The Kohonen network incorporating explicit statistics and its application to the traveling salesman problem,” Neural Networks, vol. 12, no. 9, pp. 1273-1284, 1999.
[5] B. Bullnheimer, R. F. Hartl, and C. Strauss, “A new rank based version of the ant system – A computational study,” Central European Journal for Operations Research and Economics, vol. 7, no. 1, pp. 25-38, 1997.
[6] C. Y. Chien and S. M. Chen, “A new method for handling the traveling salesman problem based on parallelized genetic colony systems,” in Proceedings of the 2009 International Conference on Machine Learning and Cybernetics, Boading, Hebei, China, pp. 2828-2833, 2009.
[7] S. C Chu, J. F. Roddick, and J. S. Pan, “Ant colony system with communication strategies,” Information Sciences, vol. 167, no. 1-4, pp. 63-76, 2004.
[8] A. Colorni, M. Dorigo, and V. Maniezzo, “Distributed optimization by ant colonies,” in Proceedings of the First European Conference on Artificial Life, Paris, France, pp. 134-142, 1991.
[9] E. M. Cochrane and J. E. Beasley, “The co-adaptive neural network approach to the Euclidean traveling salesman problem,” Neural Networks, vol. 16, no. 10, pp. 1499-1525, 2003.
[10] H. M. Deitel and P. J. Deitel, C: How to Program (3rd ed.), Upper Saddle River, NJ: Prentice Hall, 2001.
[11] M. Dorigo, Learning and Nature Algorithm (in Italian), Ph.D. Dissertation, Dipartmento di Electtonica, Polotecnico di Milano, Italy, 1992.
[12] M. Dorigo, V. Maniezzo, and A. Colorni, “Positive feedback as a search strategy,” Dipartimento di Electtonica, Polotecnico di Milano, Italy, Tech. Rep. 99-016, 1992.
[13] M. Dorigo, V. Maniezzo, and A. Colorni, “Ant system: Optimization by a colony of cooperating agents,” IEEE Transactions on System, Man, and Cybernetics Part-B: Cybernetics, vol. 26, no. 1, pp. 29-41, 1996.
[14] M. Dorigo and L. M. Gambardella, “Ant colony system: A cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 53-66, 1997.
[15] M. Dorigo and L. M. Gambardella, “Ant colonies for the traveling salesman problem,” Biosystems, vol. 34, no. 2, pp. 73-81, 1997.
[16] I. Ellabib, P. Calamai, and O. Basir, “Exchange strategies for multiple ant colony system,” Information Sciences, vol. 177, no. 5, pp. 1248-1264, 2007.
[17] L. M. Gambardella and M. Dorigo, “Solving symmetric and asymmetric TSPs by ant colonies,” in Preceedings of 1996 IEEE International Conferemce on Evolutionary Computation, Nagoya, Japan, pp. 622-627, 1996.
[18] M. Gen and R. Cheng, Genetic Algorithms and Engineering Design. NY: John Wiley & Sons, 1997.
[19] D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Boston, MA: Addison-Wesley, 1989.
[20] T. D. Gwiazda, Genetic Algorithms Reference, Vol. Ⅰ: Crossover for Single-Objective Numerical Optimization Problems, Tomasz Gwiazda, Lomianki, Poland, 2006.
[21] T. D. Gwiazda, Genetic Algorithms Reference, Vol. Ⅱ: Mutation Operator for Numerical Optimization Problems, Tomasz Gwiazda, Lomianki, Poland, 2007.
[22] J. H. Holland, Adaptation in Natural and Artificial Systems. Cambridge, MA: MIT Press, 1975.
[23] J. J. Hopfield, and D. W. Tank, “「Neural」 computation of decisions in optimization problems,” Biological Cybernetics, vol. 52, no. 3, pp. 141-152, 1985
[24] J. Kennedy and R. C. Eberhart, “Particle swarm optimization,” in Proceedings of the 1995 IEEE International Conference on Neural Networks, Piscataway, NJ, vol. 4, pp. 1942-1948, 1995.
[25] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, no. 4598, pp. 671-680, 1983.
[26] P. J. M. V. Laarhoven and E. H. L. Aarts, Simulated Annealing: Theory and Applications. Netherland: Kluwer Academic, 1987
[27] E. L. Lawler, J. K. Lenstra, and D. B. Shmoys, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley Series in Discrete Mathematics & Optimization, Chichester, 1985.
[28] B. Li and X. Song, “Improved ant colony algorithm with pheromone mutation and its application in flow-shop problems,” in Proceedings of the 6th World Congress on Intelligent Control and Automation, Dalian, China, vol. 1, pp. 3353-3356, 2006.
[29] L. Li, S. Ju, and Y. Zhang, “Improved ant colony optimization for the traveling salesman problem,” in Proceedings of the 2008 International Conference on Intelligent Computation Technology and Automation, Hunan, China, vol. 1, pp. 76-80, 2008.
[30] F. Liu and G. Zeng, “Study of genetic algorithm with reinforcement learning to solve the TSP,” Expert Systems with Applications, vol. 36, no. 3, pp. 6995-7001, 2009.
[31] O. C. Martin and S. W. Otto, “Combining simulated annealing with local search heuristics,” Annals of Operations Research, vol. 63, no. 1, pp. 57-75, 1996.
[32] T. A. S. Masutti and L. N. D. Castro, “A self-organizing neural network using ideas from the immune system to solve the traveling salesman problem,” Information Sciences, vol. 179, no. 10, pp. 1454-1468, 2009.
[33] H. M. Naimi and N. Taherinejad, “New robust and efficient ant colony algorithms: Using new interpretation of local updating process,” Expert System with Applications, vol. 36, no. 1, pp. 481-488, 2009.
[34] R. Pasti and L. N. D. Castro, “A neuro-immune network for solving the traveling salesman problem,” in Proceedings of 2006 International Joint Conference on Neural Networks, Vancouver, BC, Canada, pp. 3760-3766, 2006.
[35] M. Saadatmand-Tarzjan, M. Khademi, M.-R. Akbarzadeh-T., and H. A. Moghaddan, “A novel constructive-optimizer neural network for the traveling salesman problem,” IEEE Transactions on Systems, Man, Cybernetics-Part B: Cybernetics, vol. 37, no. 4, pp. 754-770, 2007.
[36] J. G. Sauer and L. Coelho, “Discrete differential evolution with local search to solve the traveling salesman problem: Fundamentals and case studies,” in Proceedings of the 7th IEEE International Conference on Cybernetic Intelligence Systems, London, pp. 1-6, 2008.
[37] X. Shi, L. Wang, Y. Zhou, and Y. Liang, “An ant colony optimization method for prize-collecting traveling salesman problem with time windows,” in Proceedings of the Fourth International Conference on Natural Computation, Jinan, China, vol. 7, pp. 480-484, 2008.
[38] S. Somhom, A. Modares, and T. Enkawa, “A self-organizing model for the traveling salesman problem,” Journal of the Operational Research Society, vol. 48, no. 4-6, pp. 919-928, 1997.
[39] T. Sttzle and H. H. Hoos, “Improving the ant system: A detail report on the MAX-MIN ant system,” Tech. Rep. AIDA-96-12, Darmstadt University of Technology, Computer Science Department, Intellectics Group, 1996.
[40] T. Sttzle and H. H. Hoos, “MAX-MIN ant system,” Future Generation Computer Systems, vol. 16, no. 8, pp. 889-914, 2000.
[41] http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/
[42] X. F. Xie and J. Liu, “Multiagent optimization system for solving the traveling salesman problem (TSP),” IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics, vol. 39, no. 2, pp. 489-502, 2008.
[43] J. Yi, W. Bi, G. Yang, and Z. Tang, “A fast elastic net method for traveling salesman problem,” in Proceedings of the 8th International Conference on Intelligent Systems Design and Applications, Kaohsiung, Taiwan, pp. 462-467, 2008.