Abstract
Ant colony optimization (ACO) is a meta-heuristic algorithm inspired by foraging behavior of ants and is one of the most well known swarm intelligence algorithms for solving the Traveling Salesman Problem (TSP) because of its simpleness and quality. In this paper we will propose an ACO based algorithm called ASwide that adds simple but powerful factors in the pheromone updating formula. To check the efficiency of our algorithm we did several computer experiments and confirmed that ASwide generates an acceptable solution stably compared with other methods.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Arora, T., Moses, M.E.: Ant Colony Optimization for power efficient routing in manhattan and non-manhattan VLSI architectures. In: IEEE Swarm Intelligence Symposium, SIS 2009, pp. 137–144. IEEE (2009)
Bullnheimer, B., Hartl, R.F., Strauss, C.: A new rank based version of the Ant System. A computational study (1997)
Croes, G.: A method for solving traveling-salesman problems. Operations Research 6(6), 791–812 (1958)
Dorigo, M., Stützle, T.: Ant colony optimization. A Bradford Book (2004), http://books.google.co.jp/books?id=_aefcpY8GiEC
Dorigo, M.: Optimization, learning and natural algorithms. Ph. D. Thesis, Politecnico di Milano, Italy (1992)
Dorigo, M., Caro, G.D., Gambardella, L.M.: Ant algorithms for discrete optimization. Artificial Life 5(2), 137–172 (1999)
Dorigo, M., Gambardella, L.M.: Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation 1(1), 53–66 (1997)
Dorigo, M., Maniezzo, V., Colorni, A.: Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics 26(1), 29–41 (1996)
Gutin, G., Yeo, A., Zverovich, A.: Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP. Discrete Applied Mathematics 117(1), 81–86 (2002)
Haga, M., Kato, S.: ASwide: An Ant System Adapting Penalty by Using the Ratio of Best Solution found. In: JAWS 2012 (2012) (in Japanese)
Haga, M., Kato, S.: ASwide: An Efficient Ant System for Solving the Traveling Salesman Problem. In: RENGO 2012 pp. D3–D6 (2012) (in Japanese)
Haga, M., Kato, S.: Maintaining Diversity in Ant Colony Optimization using λ-branching factor. In: Kansei Robotics Symposium 2013, pp. 89–96 (2013) (in Japanese)
Nakamichi, Y., Arita, T.: The Effects of Diversity Control Based on Random Selection in Ant Colony Optimization. Transactions of Information Processing Society of Japan 43(9), 2939–2946 (2002)
Rong-Long, W., Li-Qing, Z.: Ant colony optimization with memory and its application to traveling salesman problem. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 95(3), 639–645 (2012)
Shah-Hosseini, H.: The intelligent water drops algorithm: a nature-inspired swarm-based optimization algorithm. International Journal of Bio-Inspired Computation 1(1), 71–79 (2009)
Shimomura, S., Sugimoto, M., Haraguchi, T., Matsushita, H., Nishio, Y.: Behavior of Ant Colony Optimization with Intelligent and Dull Ants. Institute of Electronics, Information, and Communication Engineers 110(83), 157–160 (2010) (in Japanese)
Stutzle, T., Hoos, H.H.: MAX-MIN ant system. Future Generations Computer Systems 16(8), 889–914 (2000)
Tsai, C.W., Hu, K.C., Chiang, M.C., Yang, C.S.: Ant colony optimization with dual pheromone tables for clustering. In: 2011 IEEE International Conference on Fuzzy Systems (FUZZ), pp. 2916–2921. IEEE (2011)
TSP, T.: The Traveling salesman problem (2013), http://www.tsp.gatech.edu/index.html
TSPLIB: TSPLIB (2013), http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/
Wong, L.P., Low, M.Y.H., Chong, C.S.: A bee colony optimization algorithm for traveling salesman problem. In: Second Asia International Conference on Modeling & Simulation, AICMS 2008, pp. 818–823. IEEE (2008)
Zhou, X., Zhao, L., Xia, Z., Wang, R.: A Max-Min Ant System with two colonies and its application to Traveling Salesman Problem. In: 2012 IEEE Fifth International Conference on Advanced Computational Intelligence (ICACI), pp. 319–323 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Haga, M., Kato, S. (2013). A New Ant Colony Optimization Method Considering Intensification and Diversification. In: Boella, G., Elkind, E., Savarimuthu, B.T.R., Dignum, F., Purvis, M.K. (eds) PRIMA 2013: Principles and Practice of Multi-Agent Systems. PRIMA 2013. Lecture Notes in Computer Science(), vol 8291. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-44927-7_33
Download citation
DOI: https://doi.org/10.1007/978-3-642-44927-7_33
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-44926-0
Online ISBN: 978-3-642-44927-7
eBook Packages: Computer ScienceComputer Science (R0)