Abstract
In multi colony ant algorithms several colonies of ants cooperate in finding good solutions for an optimization problem. At certain time steps the colonies exchange information about good solutions. If the amount of exchanged information is not too large multi colony ant algorithms can be easily parallelized in a natural way by placing the colonies on different processors. In this paper we study the behaviour of multi colony ant algorithms with different kinds of information exchange between the colonies. Moreover we compare the behaviour of different numbers of colonies with a multi start single colony ant algorithm. As test problems we use the Traveling Salesperson problem and the Quadratic Assignment problem.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Boese, K.D., A.B. Kahng, and S. Muddu. (1994). “New Adaptive Multistart Techniques for Combinatorial Global Optimizations.” Operations Research Letters 16, 101–113.
Bolondi, M. and M. Bondaza. (1993). “Parallelizzazione di un algoritmo per la risoluzione del problema del comesso viaggiatore.” Master's Thesis, Politecnico di Milano.
Bullnheimer, B., R.F. Hartl, and C. Strauss. (1999). “A New Rank Based Version of the Ant System—A Computational Study.” CEJOR 7, 25–38.
Bullnheimer, B., G. Kotsis, and C. Strauss. (1998). “Parallelization Strategies for the Ant System.” In R. De Leone et al. (eds.), High Performance Algorithms and Software in Nonlinear Optimization, Applied Optimization, Vol. 24. Dordrecht: Kluwer, pp. 87–100.
Calégari, P.R. (1999). “Parallelization of Population-Based Evolutionary Algorithms for Combinatorial Optimization Problems.” Ph.D. Thesis, Départment D'Informatique, École Polytechnique Fédérale De Lausanne.
Colorni, A., M. Dorigo, V. Maniezzo, and M. Trubian. (1994). “Ant System for Job Shop Scheduling.” Belgian Journal Operations Research 34, 39–53.
Dorigo, M. (1992). “Optimization, Learning and Natural Algorithms.” Ph.D. Thesis, Dipartimento di Elettronica, Politecnico di Milano. (in Italian).
Dorigo, M. (1993). “Parallel Ant System: An Experimental Study.” Unpub. manuscript.
Dorigo, M. and G. Di Caro. (1999). “The Ant Colony Optimization Meta-Heuristic.” In D. Corne, M. Dorigo, and F. Glover (eds.), New Ideas in Optimization. New York: McGraw-Hill, pp. 11–32.
Dorigo, M., V. Maniezzo, and A. Colorni. (1996). “The Ant System: Optimization by a Colony of Cooperating Agents.” IEEE Trans. Sys., Man, Cybernetics—B 26, 29–41.
Gambardella, L.M. and M. Dorigo. (1995). “Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem.” In Proceedings of ML-95, Twelfth Intern. Conf. on Machine Learning. San Mateo, CA: Morgan Kaufmann, pp. 252–260.
Gambardella, L.M., E.D. Taillard, and G. Agazzi. (1999b). “MACS-VRPT: A Multiple Ant Colony System with for Vehicle Routing Problems with Time Windows.” In D. Corne, M. Dorigo, and F. Glover (eds.), New Ideas in Optimization. McGraw-Hill, 63–76.
Gambardella, L.M., E.D. Taillard, and M. Dorigo. (1999a). “Ant Colonies for the Quadratic Assignment Problem.” Journal of the Operational Research Society 50, 167–176.
Kohlmorgen, U., H. Schmeck, and K. Haase. (1999). “Experiences with Fine-Grained Parallel Genetic Algorithms.” Ann. Oper. Res. 90, 203–219.
Krüger, F., M. Middendorf, and D. Merkle. (1998). “Studies on a Parallel Ant System for the BSP Model.” Unpub. manuscript.
Maniezzo, V. and A. Colorni. (1999). “The Ant System Applied to the Quadratic Assignment Problem.” IEEE Trans. Knowledge and Data Engineering 11, 769–778.
Merkle, D., M. Middendorf, and H. Schmeck. (2000). “Ant Colony Optimization for Resource-Constrained Project Scheduling.” In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2000). San Mateo, CA: Morgan Kaufmann, pp. 893–900.
Michels, R. and M. Middendorf. (1999). “An Ant System for the Shortest Common Supersequence Problem.” In D. Corne, M. Dorigo, and F. Glover (eds.), New Ideas in Optimization. New York: McGraw-Hill, pp. 51–61.
Middendorf, M., F. Reischle, and H. Schmeck. (2000). “Information Exchange in Multi Colony Ant Algorithms.” In J. Rolim (ed.), Parallel and Distributed Computing, Proceedings of the 15 IPDPS 2000 Workshops, Third Workshop on Biologically Inspired Solutions to Parallel Processing Problems (BioSP3), Mai 1–5, 2000, Cancun, Mexico, LNCS, Vol. 1800. Berlin: Springer-Verlag, pp. 645–652.
Stützle, T. (1998). “Parallelization Strategies for Ant Colony Optimization.” In A.E. Eiben, T. Bäck, M. Schoenauer, and H.-P. Schwefel (eds.), Parallel Problem Solving from Nature—PPSN V, LNCS, Vol. 1498. Berlin: Springer-Verlag, pp. 722–731.
Stützle, T. and M. Dorigo. (1999). “ACO Algorithms for the Quadratic Assignment Problem.” In D. Corne, M. Dorigo, and F. Glover (eds.), New Ideas in Optimization. New York: McGraw-Hill, pp. 33–50.
Stützle, T. and H.H. Hoos. (1997). “Improvements on the Ant System: Introducing MAX(MIN) Ant System.” In G. D. Smith et al. (eds.), Proc. of the International Conf. on Artificial Neutral Networks and Genetic Algorithms. Berlin: Springer-Verlag, pp. 245–249.
Stützle, T. and H.H. Hoos. (2000). “MAX(MIN) Ant System.” Future Generation Computer Systems 19, 889–914.
Talbi, E.-G., O. Roux, C. Fonlupt, and D. Robillard. (1999). “Parallel Ant Colonies for Combinatorial Optimization Problems.” In J. Rolim et al. (eds.), Parallel and Distributed Processing, 11 IPPS/SPDP'99 Workshops, LNCS, Vol. 1586. Berlin: Springer, pp. 239–247.
Whitley, D., S. Rana, and R.B. Heckendorn. (1999). “The Island Model Genetic Algorithm: On Separability, Population Size and Convergence.” Journal of Computing and Information Technology—CIT 7 1, 33–47. http://www.iwr.uni-heidelberg.de/iwr/comopt/soft/TSPLIB/TSPLIB.html http://www.imm.dtu.dk/sk/qaplib/
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Middendorf, M., Reischle, F. & Schmeck, H. Multi Colony Ant Algorithms. Journal of Heuristics 8, 305–320 (2002). https://doi.org/10.1023/A:1015057701750
Issue Date:
DOI: https://doi.org/10.1023/A:1015057701750