Abstract
Ant Colony Optimization (ACO) is a new population oriented search metaphor that has been successfully applied to NP-hard combinatorial optimization problems. In this paper we discuss parallelization strategies for Ant Colony Optimization algorithms. We empirically test the most simple strategy, that of executing parallel independent runs of an algorithm. The empirical tests are performed applying MAX-MIN Ant System, one of the most efficient ACO algorithms, to the Traveling Salesman Problem and show that using parallel independent runs is very effective.
Preview
Unable to display preview. Download preview PDF.
References
E. Aarts and J. Korst. Simulated Annealing and Boltzman Machines — A Stochastic Apporach to Combinatorial Optimization and Neural Computation. John Wiley & Sons, 1989.
J.J. Bentley. Fast Algorithms for Geometric Traveling Salesman Problems. ORSA Journal on Computing, 4(4):387–411, 1992.
M. Bolondi and M. Bondanza. Parallelizzazione di un Algoritmo per la Risoluzione del Problema del Commesso Viaggiatore. Master's thesis, Politecnico di Milano, 1993.
B. Bullnheimer, R.F. Haiti, and C. Strauss. A New Rank Based Version of the Ant System — A Computational Study. Technical report, University of Viena, 1997.
B. Bullnheimer, G. Kotsis, and C. Strauss. Parallelization Strategies for the Ant System. Technical Report POM 9/97, University of Vienna, 1997.
E. CantÚ-Paz. A Survey of Parallel Genetic Algorithms. Technical Report IlliGAL 97003, University of Illinois at Urbana-Champaign, 1997.
T.G. Crainic, M. Toulouse, and M. Gendreau. Toward a Taxonomy of Parallel Tabu Search Heuristics. INFORMS Journal on Computing, 9(1):61–72, 1997.
N. Dodd. Slow Annealing Versus Multiple Fast Annealing Runs — An Empirical Investigation. Parallel Computing, 16:269–272, 1990.
M. Dorigo. Optimization, Learning, and Natural Algorithms. PhD thesis, Politecnico di Milano, 1992.
M. Dorigo and L.M. Gambardella. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1(1):53–66, 1997.
M. Dorigo, V. Maniezzo, and A. Colorni. The Ant System: Optimization by a Colony of Cooperating Agents. IEEE Transactions on Systems, Man, and Cybernetics — Part B, 26(1):29–41, 1996.
M. Gorges-Schleuter. Comparison of Local Mating Strategies in Massively Parallel Genetic Algorithms. In PPSN-II, pages 553–562, 1992.
D.S. Johnson and L.A. McGeoch. The Traveling Salesman Problem: A Case Study in Local Optimization. In E.H.L. Aarts and J.K. Lenstra, editors, Local Search in Combinatorial Optimization. John-Wiley and Sons, Ltd., 1997.
E.D. Taillard L. Gambardella and M. Dorigo. Ant Colonies for the QAP. Technical Report IDSIA-4-97, IDSIA, 1997.
S. Lin. Computer Solutions of the Traveling Salesman Problem. Bell Systems Technology Journal, 44:2245–2269, 1965.
V. Maniezzo, M. Dorigo, and A. Colorni. The Ant System Applied to the Quadratic Assignment Problem. Technical Report IRIDIA/94-28, Université Libre de Bruxelles, Belgium, 1994.
Olivier C. Martin and Steve W. Otto. Combining Simulated Annealing with Local Search Heuristics. Annals of Operations Research, 63:57–75, 1996.
P. Merz and B. Freisleben. Genetic Local Search for the TSP: New Results. In Proc. of the IEEE Conf. on Evol. Comp. (1CEC'97), pages 159–164, 1997.
Y. Nagata and S. Kobayashi. Edge Assembly Crossover: A High-power Genetic Algorithm for the Traveling Salesman Problem. In Proc. of ICGA'97, pages 450–457, 1997.
G. Reinelt. TSPLIB — A Traveling Salesman Problem Library. ORSA Journal On Computing, 3:376–384, 1991.
R. Shonkwiler. Parallel Genetic Algorithms. In Proceedings of ICGA'93, 1993.
T. Stützle. MAX-MIN Ant System for the Quadratic Assignment Problem. Technical Report AIDA-97-4TH Darmstadt, July 1997.
T. Stützle and H. Hoos. The MAX-MIN Ant System and Local Search for the Traveling Salesman Problem. In IEEE Conf. on Evol. Comp. (ICEC'97), pages 309–314, 1997.
T. Stützle and H. Hoos. Improvements on the Ant System: Introducing MAX-MIN Ant System. In Proceedings of ICANNGA'97. Springer Verlag, Wien, 1997.
é.D. Taillard. Robust Taboo Search for the Quadratic Assignment Problem. Parallel Computing, 17:443–455, 1991.
é.D. Taillard. Comparison of Iterative Searches for the Quadratic Assignment Problem. Location Science, pages 87–105, 1995.
H.M.M. ten Eikelder, B.J.M. Aarts, M.G.A. Verhoeven, and E.H.L. Aarts. Sequential and Parallel Local Search Algorithms for Job Shop Scheduling. Paper presented at the Metaheuristics conference 1997, 1997.
N.L.J. Ulder, E.H.L. Aarts, H.-J. Bandelt, P.J.M. van Laarhoven, and E.Pesch. Genetic Local Search Algorithms for the Traveling Salesman Problem. In Proceedings PPSN-I, number 496 in LNCS, pages 109–116. Springer Verlag, 1991.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Stützle, T. (1998). Parallelization strategies for Ant Colony Optimization. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, HP. (eds) Parallel Problem Solving from Nature — PPSN V. PPSN 1998. Lecture Notes in Computer Science, vol 1498. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0056914
Download citation
DOI: https://doi.org/10.1007/BFb0056914
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65078-2
Online ISBN: 978-3-540-49672-4
eBook Packages: Springer Book Archive