Improved ACO Algorithm with Pheromone Correction Strategy for the Traveling Salesman Problem
Keywords:
ant colony optimization (ACO), traveling salesman problem (TSP), nature inspired algorithms, metaheuristics, swarm intelligenceAbstract
A new, improved ant colony optimization (ACO) algorithm with novel pheromone correction strategy is introduced. It is implemented and tested on the traveling salesman problem (TSP). Algorithm modification is based on undesirability of some elements of the current best found solution. The pheromone values for highly undesirable links are significantly lowered by this a posteriori heuristic. This new hybridized algorithm with the strategy for avoiding stagnation by leaving local optima was tested on standard benchmark problems from the TSPLIB library and superiority of our method to the basic ACO and also to the particle swarm optimization (PSO) is shown. The best found solutions are improved, as well as the mean values for multiple runs. The computation cost increase for our modification is negligible.
References
Brajevic, I. and Tuba, M. (2012) An upgraded artificial bee colony algorithm (ABC) for constrained optimization problems. Journal of Intelligent Manufacturing, published Online First, DOI:10.1007/s10845-011-0621-6.
Bacanin, N. and Tuba, M. (2012) Artificial bee colony (ABC) algorithm for constrained optimization improved with genetic operators. Studies in Informatics and Control, 21(2), 137-146.
Secui, D. C., Felea, I., Dzitac, S., and Popper, L. (2010) A swarm intelligence approach to the power dispatch problem. International Journal of Computers, Communications & Control, 5(3), 375-384.
Zamfirescu, C.-B. and Filip, F. G. (2010) Swarming models for facilitating collaborative decisions. International Journal of Computers, Communications & Control, 5(1), 125-137.
Wang, Z., Geng, X., and Shao, Z. (2009) An effective simulated annealing algorithm for solving the traveling salesman problem. Journal of Computational and Theoretical Nanoscience, 6(7), 1680-1686. http://dx.doi.org/10.1166/jctn.2009.1230
Meer, K. (2007) Simulated annealing versus metropolis for a TSP instance. Information Processing Letters, 104(6), 216-219. http://dx.doi.org/10.1016/j.ipl.2007.06.016
Gendreau, M., Laporte, G., and Semet, F. (1998) A tabu search heuristic for the undirected selective travelling salesman problem. European Journal of Operational Research, 106(2-3), 539-545. http://dx.doi.org/10.1016/S0377-2217(97)00289-0
Liu, F. and Zeng, G. (2009) Study of genetic algorithm with reinforcement learning to solve the TSP. Expert Systems with Applications, 36(3), 6995-7001. http://dx.doi.org/10.1016/j.eswa.2008.08.026
Shi, X. H., Liang, Y. C., Lee, H. P., Lu, C., and Wang, Q. X. (2007) Particle swarm optimization-based algorithms for TSP and generalized TSP. Information Processing Letters, 103(5), 169-176. http://dx.doi.org/10.1016/j.ipl.2007.03.010
Applegate, D., Bixby, R., Chvatal, V., and Cook, W. (1998) On the solution of the travelling salesman problems. Documenta Mathematica, Extra Volume ICM(III), 645-656.
Rego, C., Gamboa, D., Glover, F., and Osterman, C. (2011) Traveling salesman problem heuristics: Leading methods, implementations and latest advances. European Journal of Operational Research, 211(3), 427-441. http://dx.doi.org/10.1016/j.ejor.2010.09.010
Dorigo, M. and Gambardella, L. M. (1997) Ant colonies for the travelling salesman problem. Biosystems, 43(2), 73-81. http://dx.doi.org/10.1016/S0303-2647(97)01708-5
Chengming, Q. (2008) An ant colony algorithm with stochastic local search for the VRP. 3rd International Conference on Innovative Computing Information and Control, Los Alamitos, CA, USA, pp. 464-468, IEEE Computer Society.
Lee, Z.-J., Su, S.-F., Chuang, C.-C., and Liu, K.-H. (2008) Genetic algorithm with ant colony optimization (GA-ACO) for multiple sequence alignment. Applied Soft Computing, 8(1), 55-78. http://dx.doi.org/10.1016/j.asoc.2006.10.012
Jun-Qing Li, Q.-K. P. and Xie, S.-X. (2010) A hybrid variable neighborhood search algorithm for solving multi-objective flexible job shop problems. Computer Science and Information Systems, 7(4), 907-930. http://dx.doi.org/10.2298/CSIS090608017L
Negulescu, S., Dzitac, I., and Lascu, A. (2010) Synthetic genes for artificial ants. diversity in ant colony optimization algorithms. International Journal of Computers, Communications & Control, 5(2), 216-223.
Zhang, X., Duan, H., and Jin, J. (2008) DEACO: Hybrid ant colony optimization with differential evolution. IEEE Congress on Evolutionary Computation, pp. 921-927, IEEE Computer Society.
Neumann, F., Sudholt, D., and Witt, C. (2008) Rigorous analyses for the combination of ant colony optimization and local search. Ant Colony Optimization and Swarm Intelligence, LNCS Vol. 5217, Berlin, Heidelberg, pp. 132-143, Springer-Verlag. http://dx.doi.org/10.1007/978-3-540-87527-7_12
Gan, R., Guo, Q., Chang, H., and Yi, Y. (2010) Improved ant colony optimization algorithm for the traveling salesman problems. Journal of Systems Engineering and Electronics, 21(2), 329-333. http://dx.doi.org/10.3969/j.issn.1004-4132.2010.02.025
Jovanovic, R., Tuba, M., and Simian, D. (2010) Comparison of different topologies for island-based multi-colony ant algorithms for the minimum weight vertex cover problem. WSEAS Transactions on Computers, 9(1), 83-92.
St¨utzle, T. and Dorigo, M. (1999) ACO algorithms for the traveling salesman problem. Evolutionary Algorithms in Engineering and Computer Science: Recent Advances in Genetic Algorithms, Evolution Strategies, Evolutionary Programming, Genetic Programming and Industrial Applications, K Miettinen, P Niettaanmaki, M M Makela and J Periaux, editors, p. 500, Willey.
St¨utzle, T. and Hoos, H. H. (2000) MAX-MIN ant system. Future Generation Computer Systems, 16(9), 889-914. http://dx.doi.org/10.1016/S0167-739X(00)00043-1
Wong, K. Y. and See, P. C. (2009) A new minimum pheromone threshold strategy (MPTS) for max-min ant system. Applied Soft Computing, 9(3), 882-888. http://dx.doi.org/10.1016/j.asoc.2008.11.011
Pintea, C.-M., Chira, C., Dumitrescu, D., and Pop, P. C. (2011) Sensitive ants in solving the generalized vehicle routing problem. International Journal of Computers, Communications & Control, 6(4), 228-231.
Jovanovic, R. and Tuba, M. (2011) An ant colony optimization algorithm with improved pheromone correction strategy for the minimum weight vertex cover problem. Applied Soft Computing Journal, 11(8), 5360-5366. http://dx.doi.org/10.1016/j.asoc.2011.05.023
Gan, R., Guo, Q., Chang, H., and Yi, Y. (2010) Improved ant colony optimization algorithm for the traveling salesman problems. Journal of Systems Engineering and Electronics, 21(2), 329-333. http://dx.doi.org/10.3969/j.issn.1004-4132.2010.02.025
Cri¸san, G. C. and Nechita, E. (2008) Solving fuzzy TSP with ant algorithms. International Journal of Computers, Communications & Control, III(S.), 228-231.
Huang, H., Yang, X., Hao, Z., and Cai, R. (2006) A novel ACO algorithm with adaptive parameter. Computational Intelligence and Bioinformatics, LNCS 4115, pp. 12-21, Springer-Verlag Berlin Heidelberg. http://dx.doi.org/10.1007/11816102_2
White, C. and Yen, G. (2004) A hybrid evolutionary algorithm for traveling salesman problem. IEEE Congress on Evolutionary Computation, Vol.2, pp. 1473-1478, IEEE Computer Society.
Duan, H. and Yu, X. (2007) Hybrid ant colony optimization using memetic algorithm for traveling salesman problem. Approximate Dynamic Programming and Reinforcement Learning, pp. 92-95, IEEE Computer Society.
Reinelt, G. (1991) TSPLIB - a traveling salesman problem library. ORSA Journal on Computing, 3(4), 376-384. http://dx.doi.org/10.1287/ijoc.3.4.376
Jovanovic, R. and Tuba, M. (2012) Ant colony optimization algorithm with pheromone correction strategy for the minimum connected dominating set problem. Computer Science and Information Systems (ComSIS), Accepted for publishing.
http://www.iwr.uni heidelberg.de/groups/comopt/software/TSPLIB95/tsp/ .
Jovanovic, R., Tuba, M., and Simian, D. (2008) An object-oriented framework with corresponding graphical user interface for developing ant colony optimization based algorithms. WSEAS Transactions on Computers, 7(12), 1948-1957.
Published
Issue
Section
License
Copyright (c) 2017 Milan Tuba, Raka Jovanovic
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
