Paper:

# Improving Ant Colony Optimization Algorithms for Solving Traveling Salesman Problems

## Kuo-Sheng Hung^{*}, Shun-Feng Su^{*,**}, and Zne-Jung Lee^{***}

^{*}Dept. of Electrical Eng., National Taiwan University of Science and Technology, No. 43, Sec. 4, Keelung Rd. Taipei, 106, Taiwan

^{**}Dept. of Electrical Eng., National Taipei University of Technology, No. 1, Sec. 3, Chung-Hsiao E. Rd., Taipei, 106, Taiwan

^{***}Dept. of Information Management, Huafan University, Taipei, Taiwan

*J. Adv. Comput. Intell. Intell. Inform.*, Vol.11 No.4, pp. 433-442, 2007.

- [1] E. Bonabeau, M. Dorigo, and G. Theraulaz, “Swarm intelligence from natural to artificial systems,” Oxford University Press, 1999.
- [2] M. Dorigo and L. M. Gambardella, “The colony system: A cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, Vol.1, No.1, April, 1997.
- [3] A. Colorni, M. Dorigo, and V. Maniezzo, “Distributed optimization by ant colonies,” Proc. of ECAL91-European Conference on Artificial Life, pp. 134-142, 1991.
- [4] M. Dorigo, V. Maniezzo, and A. Colorni, “The ant system: Optimization by a colony of cooperating agents,” IEEE Transactions on System, Man, and Cybernetics, Part B, Vol.26, pp. 29-41, 1996.
- [5] T. Stützle and H. H. Hoos, “Max-min ant system,” Future Generation Computer System, Vol.16, pp. 889-914, 2000.
- [6] L. M. Gambardella and M. Dorigo, “Ant-Q: A reinforcement learning approach to the traveling salesman problem,” Proceeding of ML-95, Twelfth Intern. Conf. on Machine Learning, Morgan Kaufmann, pp. 252-260, 1995
- [7] M. Dorigo and L. M. Gambardella, “A study of some properties of ant-Q,” Proceedings of PPSN-IV, Fourth International Conference on Parallel Problem Solving from Nature, Vol.1141, pp. 656-665, Springer-Verlag, 1996.
- [8] B. Bullnheimer, R. F. Hartl, and C. Strauss, “A new rank-based version of ant system: A computational study,” Central European Journal for Operations Research and Economics, Vol.7, No.1, pp. 25-38, 1999.
- [9] T. Stützle and M. Dorigo, “Ant colony optimization,” MIT Press, 2004.
- [10] S. Lin, “Computer solutions of the traveling salesman problem,” Bell Systems Technology Journal, Vol.44, pp. 2245-2269, 1965.
- [11] B. H. Korte, “Applications of combinatorial optimization,” Mathematical programming: Recent developments and applications, Kluwer, Dordrecht, pp. 1-55, 1989.
- [12] R. G. Bland and D. F. Shallcross, “Large traveling salesman problems arising from experiments in X-ray crystallography: A preliminary report on computation,” Operations Research Letters, Vol.8, pp. 125-128, 1989.
- [13] G. Reinelt, “The traveling salesman: Computational solutions for TSP applications,” Lecture Note in Computer Science, Vol.840, Springer-Verlag, Berlin, 1994.
- [14] M. Dorigo and G. D. Caro, “Ant colony optimization: A new metaheuristic,” Proceedings of the 1999 Congress on Evolutionary Computation, Vol.2, pp. 1470-1477, 1999.
- [15] R. Beckers, J. L. Deneubourg, and S. Goss, “Trails and U-turn in the selection of the shortest path by the ant Lasius Niger,” Journal of Theoretical Biology, Vol.159, pp. 397-415, 1992.
- [16] D. J. Rosenkranz, R. E. Stearns, and P. M. Lewis, “An analysis of several heuristics for the traveling salesman problem,” SIAM Journal on Computing, Vol.6, pp. 563-581, 1997.
- [17] N. R. Pal and S. K. Pal, “Entropy: A new definition and its applications,” IEEE Transactions on System, Man, and Cybernetics, Vol.5, No.21, pp. 1260-1270, 1991.
- [18] R. Bose, “Information theory, coding, and cryptography,” McGraw Hill, 2002.
- [19] M. Dorigo and G. D. Caro, “Ant algorithm for discrete optimization,” Artificial Life, Vol.5, No.3, pp. 137-172, 1999.
- [20] E. T. Jaynes, “On the rationale of the maximum entropy methods,” Proceedings of the IEEE, Vol.70, No.9, pp. 939-952, 1982.
- [21] E. L. Lawer, J. K. Lenstra, A. H. R. Kan, and D. B. Shmoys, “The traveling salesman problem,” Wiley, New Work, 1985.
- [22] G. A. Croes, “A method for solving traveling salesman problems,” Operations Research, Vol.6, No.6, pp. 791-812, 1958.
- [23] J. L. Bently, “Fast algorithms for geometric traveling salesman problems,” Journal on Computing, Vol.6, No.4, pp. 387-411, 1992.
- [24] G. E. Robinson, “Regulation of division of labor in insect societies,” Annual Review of Entomology, Vol.37, pp. 637-665, 1992.
- [25] L. Nemes and T. Roska, “A CNN model of oscillation and chaos in ant colonies: A case study,” IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, Vol.42, No.10, pp. 741-745, 1995.
- [26] V. Maniezzo and A. Coorni, “The ant system applied to the quadratic assignment problem,” IEEE Transactions on Knowledge and Data Engineering, Vol.11, pp. 769-778, 1999.
- [27] S. Goss, S. Aron, J. L. Deneubourg, and J. M. Pasteels, “Selforganized shortcuts in the argentine ant,” Naturwissenchaftn, Vol.76, pp. 579-581, 1989.
- [28] S. Lin and B. W. Kernighan, “An effective heuristic algorithm for the traveling salesman problem,” Operations Research, Vol.21, No.2, pp. 498-516, 1973.
- [29] E. Aarts and J. K. Lenstra, “Local search in combinatorial optimization,” John Wiley & Sons Inc., 1997.
- [30] http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/
- [31] Z.-J. Lee, S.-F. Su, and C.-Y. Lee, “An immunity based ant colony optimization algorithm for solving weapon-target assignment problems,” Applied Soft Computing, Vol.2, pp. 39-47, 2002.
- [32] Z.-J. Lee, S.-F. Su, and C.-Y. Lee, “A heuristic based ant colony system applied to weapon-target assignment problems,” Journal of Applied Systems Studies, Vol.4, No.2, 2003.
- [33] C.-C. Chuang, S.-F. Su, and C.-C. Hsiao, “The annealing robust backpropagation (ARBP) learning algorithm,” IEEE Trans. On Neural Networks, Vol.11, No.5, pp. 1067-1077, 2000.
- [34] K.-S. Hung, “An Entropy-based Algorithm in Ant Colony Optimization for Traveling Salesman Problems,” Master Thesis, Dept. Electrical Engineer, National Taiwan University of Science and Technology, Spring 2006.

This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.