Top > JACIII > Improving Ant Colony Optimization Algorithms for Solving Trave ...

single-jc.php

JACIII Vol.11 No.4 pp. 433-442
doi: 10.20965/jaciii.2007.p0433
(2007)

Paper:

Views over last 60 days: 928

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

Received:
April 17, 2006
Accepted:
September 5, 2006
Published:
April 20, 2007
Creative Commons License
Keywords:
ant colony optimization, traveling salesman problems, entropy
Abstract
Ant colony optimization (ACO) has been successfully applied to solve combinatorial optimization problems, but it still has some drawbacks such as stagnation behavior, long computational time, and premature convergence. These drawbacks will be more evident when the problem size increases. In this paper, we reported the analysis of using a lower pheromone trail bound and a dynamic updating rule for the heuristic parameters based on entropy to improve the efficiency of ACO in solving Traveling Salesman Problems (TSPs). TSPs are NP-hard problem. Even though the problem itself is simple, when the number of city is large, the search space will become extremely large and it becomes very difficult to find the optimal solution in a short time. From our experiments, it can be found that the proposed algorithm indeed has superior search performance over traditional ACO algorithms do.
Cite this article as:
K. Hung, S. Su, and Z. Lee, “Improving Ant Colony Optimization Algorithms for Solving Traveling Salesman Problems,” J. Adv. Comput. Intell. Intell. Inform., Vol.11 No.4, pp. 433-442, 2007.
Data files:
References
  1. [1] E. Bonabeau, M. Dorigo, and G. Theraulaz, “Swarm intelligence from natural to artificial systems,” Oxford University Press, 1999.
  2. [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. [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. [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. [5] T. Stützle and H. H. Hoos, “Max-min ant system,” Future Generation Computer System, Vol.16, pp. 889-914, 2000.
  6. [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. [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. [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. [9] T. Stützle and M. Dorigo, “Ant colony optimization,” MIT Press, 2004.
  10. [10] S. Lin, “Computer solutions of the traveling salesman problem,” Bell Systems Technology Journal, Vol.44, pp. 2245-2269, 1965.
  11. [11] B. H. Korte, “Applications of combinatorial optimization,” Mathematical programming: Recent developments and applications, Kluwer, Dordrecht, pp. 1-55, 1989.
  12. [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. [13] G. Reinelt, “The traveling salesman: Computational solutions for TSP applications,” Lecture Note in Computer Science, Vol.840, Springer-Verlag, Berlin, 1994.
  14. [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. [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. [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. [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. [18] R. Bose, “Information theory, coding, and cryptography,” McGraw Hill, 2002.
  19. [19] M. Dorigo and G. D. Caro, “Ant algorithm for discrete optimization,” Artificial Life, Vol.5, No.3, pp. 137-172, 1999.
  20. [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. [21] E. L. Lawer, J. K. Lenstra, A. H. R. Kan, and D. B. Shmoys, “The traveling salesman problem,” Wiley, New Work, 1985.
  22. [22] G. A. Croes, “A method for solving traveling salesman problems,” Operations Research, Vol.6, No.6, pp. 791-812, 1958.
  23. [23] J. L. Bently, “Fast algorithms for geometric traveling salesman problems,” Journal on Computing, Vol.6, No.4, pp. 387-411, 1992.
  24. [24] G. E. Robinson, “Regulation of division of labor in insect societies,” Annual Review of Entomology, Vol.37, pp. 637-665, 1992.
  25. [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. [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. [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. [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. [29] E. Aarts and J. K. Lenstra, “Local search in combinatorial optimization,” John Wiley & Sons Inc., 1997.
  30. [30] http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/
  31. [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. [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. [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. [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.

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

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Apr. 19, 2024