×

Ant colony optimization theory: a survey. (English) Zbl 1154.90626

Summary: Research on a new metaheuristic for optimization is often initially focused on proof-of-concept applications. It is only after experimental work has shown the practical interest of the method that researchers try to deepen their understanding of the method’s functioning not only through more and more sophisticated experiments but also by means of an effort to build a theory. Tackling questions such as “how and why the method works” is important, because finding an answer may help in improving its applicability. Ant colony optimization, which was introduced in the early 1990s as a novel technique for solving hard combinatorial optimization problems, finds itself currently at this point of its life cycle. With this article we provide a survey on theoretical results on ant colony optimization. First, we review some convergence results. Then we discuss relations between ant colony optimization algorithms and other approximate methods for optimization. Finally, we focus on some research efforts directed at gaining a deeper understanding of the behavior of ant colony optimization algorithms. Throughout the paper we identify some open questions with a certain interest of being solved in the near future.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
68T05 Learning and adaptive systems in artificial intelligence
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C27 Combinatorial optimization
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baum, L. E.; Sell, G. R., Growth transformations for functions on manifolds, Pacific J. Math., 27, 2, 211-227 (1968) · Zbl 0165.22505
[2] M. Birattari, G. Di Caro, M. Dorigo, Toward the formal foundation of ant programming, in: M. Dorigo, G. Di Caro, M. Sampels (Eds.), Ant Algorithms, Proc. ANTS 2002, Third Internat. Workshop, Lecture Notes in Computer Science, Vol. 2463, Springer, Berlin, Germany, 2002, pp. 188-201.; M. Birattari, G. Di Caro, M. Dorigo, Toward the formal foundation of ant programming, in: M. Dorigo, G. Di Caro, M. Sampels (Eds.), Ant Algorithms, Proc. ANTS 2002, Third Internat. Workshop, Lecture Notes in Computer Science, Vol. 2463, Springer, Berlin, Germany, 2002, pp. 188-201.
[3] C. Blum, Theoretical and Practical Aspects of Ant Colony Optimization, Dissertations in Artificial Intelligence, Vol. 282, Akademische Verlagsgesellschaft Aka GmbH, Berlin, Germany, 2004.; C. Blum, Theoretical and Practical Aspects of Ant Colony Optimization, Dissertations in Artificial Intelligence, Vol. 282, Akademische Verlagsgesellschaft Aka GmbH, Berlin, Germany, 2004. · Zbl 1148.90017
[4] Blum, C., Beam-ACO—Hybridizing ant colony optimization with beam search: an application to open shop scheduling, Comput. Oper. Res., 32, 6, 1565-1591 (2005) · Zbl 1122.90427
[5] C. Blum, M. Dorigo, Deception in ant colony optimization, in: M. Dorigo, M. Birattari, C. Blum, L.M. Gambardella, F. Mondada, T. Stützle (Eds.), Proc. ANTS 2004, Fourth Internat. Workshop on Ant Colony Optimization and Swarm Intelligence, Lecture Notes in Computer Science, Vol. 3172, Springer, Berlin, Germany, 2004, pp. 119-130.; C. Blum, M. Dorigo, Deception in ant colony optimization, in: M. Dorigo, M. Birattari, C. Blum, L.M. Gambardella, F. Mondada, T. Stützle (Eds.), Proc. ANTS 2004, Fourth Internat. Workshop on Ant Colony Optimization and Swarm Intelligence, Lecture Notes in Computer Science, Vol. 3172, Springer, Berlin, Germany, 2004, pp. 119-130.
[6] Blum, C.; Dorigo, M., The hyper-cube framework for ant colony optimization, IEEE Trans. Systems, Man, Cybernet.-Part B, 34, 2, 1161-1172 (2004)
[7] Blum, C.; Dorigo, M., Search bias in ant colony optimization: on the role of competition-balanced systems, IEEE Trans. Evol. Comput., 9, 2, 159-174 (2005)
[8] Blum, C.; Roli, A., Metaheuristics in combinatorial optimization: overview and conceptual comparison, ACM Comput. Surveys, 35, 3, 268-308 (2003)
[9] Blum, C.; Sampels, M., Ant Colony Optimization for FOP shop scheduling: a case study on different pheromone representations, (Proc. 2002 Congr. on Evolutionary Computation (CEC’02), Vol. 2 (2002), IEEE Computer Society Press: IEEE Computer Society Press Los Alamitos, CA), 1558-1563
[10] C. Blum, M. Sampels, When model bias is stronger than selection pressure, in: J.J. Merelo Guervós et al. (Eds.), Proc. PPSN-VII, Seventh Internat. Conf. on Parallel Problem Solving from Nature, Lecture Notes in Computer Science, Vol. 2439, Springer, Berlin, Germany, 2002, pp. 893-902.; C. Blum, M. Sampels, When model bias is stronger than selection pressure, in: J.J. Merelo Guervós et al. (Eds.), Proc. PPSN-VII, Seventh Internat. Conf. on Parallel Problem Solving from Nature, Lecture Notes in Computer Science, Vol. 2439, Springer, Berlin, Germany, 2002, pp. 893-902.
[11] Blum, C.; Sampels, M., An ant colony optimization algorithm for shop scheduling problems, J. Math. Model. Algorithms, 3, 3, 285-308 (2004) · Zbl 1146.90405
[12] Blum, C.; Sampels, M.; Zlochin, M., On a particularity in model-based search, (Langdon, W. B.; etal., Proc. Genetic and Evolutionary Computation Conf. (GECCO-2002). Proc. Genetic and Evolutionary Computation Conf. (GECCO-2002), Morgan Kaufmann Publishers, San Francisco, CA (2002)), 35-42
[13] Černý, V., A thermodynamical approach to the travelling salesman problem: an efficient simulation algorithm, J. Optim. Theory Appl., 45, 41-51 (1985) · Zbl 0534.90091
[14] Costa, D.; Hertz, A., Ants can color graphs, J. Oper. Res. Soc., 48, 295-305 (1997) · Zbl 0890.90174
[15] J.S. de Bonet, C.L. Isbell Jr., P. Viola, MIMIC: finding optima by estimating probability densities, in: M.C. Mozer, M.I. Jordan, T. Petsche (Eds.), Adv. Neural Inform. Process. Systems, Vol. 7 (NIPS7), MIT Press, Cambridge, MA, 1997, pp. 424-431.; J.S. de Bonet, C.L. Isbell Jr., P. Viola, MIMIC: finding optima by estimating probability densities, in: M.C. Mozer, M.I. Jordan, T. Petsche (Eds.), Adv. Neural Inform. Process. Systems, Vol. 7 (NIPS7), MIT Press, Cambridge, MA, 1997, pp. 424-431.
[16] Deb, K.; Goldberg, D. E., Analyzing deception in trap functions, (Whitley, L. D., Foundations of Genetic Algorithms, Vol. 2 (1993), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 93-108
[17] M.L. den Besten, T. Stützle, M. Dorigo, Ant colony optimization for the total weighted tardiness problem, in: M. Schoenauer, K. Deb, G. Rudolph, X. Yao, E. Lutton, J.J. Merelo, H.-P. Schwefel (Eds.), Proc. PPSN-VI, Sixth Internat. Conf. on Parallel Problem Solving from Nature, Lecture Notes in Computer Science, Vol. 1917, Springer, Berlin, Germany, 2000, pp. 611-620.; M.L. den Besten, T. Stützle, M. Dorigo, Ant colony optimization for the total weighted tardiness problem, in: M. Schoenauer, K. Deb, G. Rudolph, X. Yao, E. Lutton, J.J. Merelo, H.-P. Schwefel (Eds.), Proc. PPSN-VI, Sixth Internat. Conf. on Parallel Problem Solving from Nature, Lecture Notes in Computer Science, Vol. 1917, Springer, Berlin, Germany, 2000, pp. 611-620.
[18] Deneubourg, J.-L.; Aron, S.; Goss, S.; Pasteels, J.-M., The self-organizing exploratory pattern of the argentine ant, J. Insect Behav., 3, 159-168 (1990)
[19] Di Caro, G.; Dorigo, M., AntNet: distributed stigmergetic control for communications networks, J. Artif. Intel. Res., 9, 317-365 (1998) · Zbl 0910.68182
[20] M. Dorigo, Optimization, learning and natural algorithms (in Italian), Ph.D. Thesis, Dipartimento di Elettronica, Politecnico di Milano, Italy, 1992.; M. Dorigo, Optimization, learning and natural algorithms (in Italian), Ph.D. Thesis, Dipartimento di Elettronica, Politecnico di Milano, Italy, 1992.
[21] Dorigo, M.; Gambardella, L. M., Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE Trans. Evol. Comput., 1, 1, 53-66 (1997)
[22] M. Dorigo, V. Maniezzo, A. Colorni, Positive feedback as a search strategy, Tech. Report 91-016, Dipartimento di Elettronica, Politecnico di Milano, Italy, 1991.; M. Dorigo, V. Maniezzo, A. Colorni, Positive feedback as a search strategy, Tech. Report 91-016, Dipartimento di Elettronica, Politecnico di Milano, Italy, 1991. · Zbl 0825.90549
[23] Dorigo, M.; Maniezzo, V.; Colorni, A., Ant system: optimization by a colony of cooperating agents, IEEE Trans. Systems, Man, Cybernet.-Part B, 26, 1, 29-41 (1996)
[24] Dorigo, M.; Stützle, T., Ant Colony Optimization (2004), MIT Press: MIT Press Cambridge, MA · Zbl 1092.90066
[25] M. Dorigo, M. Zlochin, N. Meuleau, M. Birattari, Updating ACO pheromones using stochastic gradient ascent and cross-entropy methods, in: S. Cagnoni, J. Gottlieb, E. Hart, M. Middendorf, G.R. Raidl (Eds.), Applications of Evolutionary Computing, Proc. EvoWorkshops 2002, Lecture Notes in Computer Science, Vol. 2279, Springer, Berlin, Germany, 2002, pp. 21-30.; M. Dorigo, M. Zlochin, N. Meuleau, M. Birattari, Updating ACO pheromones using stochastic gradient ascent and cross-entropy methods, in: S. Cagnoni, J. Gottlieb, E. Hart, M. Middendorf, G.R. Raidl (Eds.), Applications of Evolutionary Computing, Proc. EvoWorkshops 2002, Lecture Notes in Computer Science, Vol. 2279, Springer, Berlin, Germany, 2002, pp. 21-30. · Zbl 1044.68751
[26] Fogel, L. J.; Owens, A. J.; Walsh, M. J., Artificial Intelligence Through Simulated Evolution (1966), Wiley: Wiley New York · Zbl 0148.40701
[27] Gagné, C.; Price, W. L.; Gravel, M., Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times, J. Oper. Res. Soc., 53, 895-906 (2002) · Zbl 1130.90326
[28] Gambardella, L. M.; Dorigo, M., Ant colony system hybridized with a new local search for the sequential ordering problem, INFORMS J. Comput., 12, 3, 237-255 (2000) · Zbl 1040.90570
[29] Gambardella, L. M.; Taillard, É. D.; Agazzi, G., MACS-VRPTW: a multiple ant colony system for vehicle routing problems with time windows, (Corne, D.; Dorigo, M.; Glover, F., New Ideas in Optimization (1999), McGraw-Hill: McGraw-Hill London, UK), 63-76
[30] Glover, F., Tabu search—Part I, ORSA J. Comput., 1, 3, 190-206 (1989) · Zbl 0753.90054
[31] Glover, F., Tabu search—Part II, ORSA J. Comput., 2, 1, 4-32 (1990) · Zbl 0771.90084
[32] F. Glover, G. Kochenberger (Eds.), Handbook of Metaheuristics, Kluwer Academic Publishers, Norwell, MA, 2002.; F. Glover, G. Kochenberger (Eds.), Handbook of Metaheuristics, Kluwer Academic Publishers, Norwell, MA, 2002.
[33] Glover, F.; Laguna, M., Tabu Search (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0930.90083
[34] Goldberg, D. E., Simple genetic algorithms and the minimal deceptive problem, (Davis, L., Genetic Algorithms and Simulated Annealing (1987), Pitman: Pitman London, UK), 74-88
[35] M. Guntsch, M. Middendorf, Pheromone modification strategies for ant algorithms applied to dynamic TSP, in: E.J.W. Boers, J. Gottlieb, P.L. Lanzi, R.E. Smith, S. Cagnoni, E. Hart, G.R. Raidl, H. Tijink (Eds.), Applications of Evolutionary Computing: Proc. EvoWorkshops 2001, Lecture Notes in Computer Science, Vol. 2037, Springer, Berlin, Germany, 2001, pp. 213-222.; M. Guntsch, M. Middendorf, Pheromone modification strategies for ant algorithms applied to dynamic TSP, in: E.J.W. Boers, J. Gottlieb, P.L. Lanzi, R.E. Smith, S. Cagnoni, E. Hart, G.R. Raidl, H. Tijink (Eds.), Applications of Evolutionary Computing: Proc. EvoWorkshops 2001, Lecture Notes in Computer Science, Vol. 2037, Springer, Berlin, Germany, 2001, pp. 213-222.
[36] W.J. Gutjahr, A generalized convergence result for the graph-based ant system metaheuristic, Tech. Report 99-09, Department of Statistics and Decision Support Systems, University of Vienna, Austria, 1999.; W.J. Gutjahr, A generalized convergence result for the graph-based ant system metaheuristic, Tech. Report 99-09, Department of Statistics and Decision Support Systems, University of Vienna, Austria, 1999.
[37] Gutjahr, W. J., A graph-based ant system and its convergence, Future Gen. Comput. Systems, 16, 9, 873-888 (2000)
[38] Gutjahr, W. J., ACO algorithms with guaranteed convergence to the optimal solution, Inform. Process. Lett., 82, 3, 145-153 (2002) · Zbl 1013.68092
[39] Holland, J. H., Adaption in Natural and Artificial Systems (1975), The University of Michigan Press: The University of Michigan Press Ann Harbor, MI · Zbl 0317.68006
[40] Hoos, H. H.; Stützle, T., Stochastic Local Search: Foundations and Applications (2004), Elsevier, Amsterdam: Elsevier, Amsterdam The Netherlands · Zbl 1126.68032
[41] Jones, T.; Forrest, S., Fitness distance correlation as a measure of problem difficulty for genetic algorithms, (Eshelman, L. J., Proc. 6th Internat. Conf. on Genetic Algorithms. Proc. 6th Internat. Conf. on Genetic Algorithms, Kaufman, LosAltos, CA (1995)), 184-192
[42] M.I. Jordan (Ed.), Learning in Graphical Models, MIT Press, Cambridge, MA, 1998.; M.I. Jordan (Ed.), Learning in Graphical Models, MIT Press, Cambridge, MA, 1998.
[43] L. Kallel, B. Naudts, A. Rogers (Eds.), Theoretical Aspects of Evolutionary Computing, Natural Computing Series, Springer, Berlin, Germany, 2001.; L. Kallel, B. Naudts, A. Rogers (Eds.), Theoretical Aspects of Evolutionary Computing, Natural Computing Series, Springer, Berlin, Germany, 2001.
[44] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 4598, 671-680 (1983) · Zbl 1225.90162
[45] Kullback, S., Information Theory and Statistics (1959), Wiley: Wiley New York · Zbl 0149.37901
[46] Maniezzo, V., Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem, INFORMS J. Comput., 11, 4, 358-369 (1999) · Zbl 1034.90526
[47] Maniezzo, V.; Colorni, A., The ant system applied to the quadratic assignment problem, IEEE Trans. Data Knowledge Eng., 11, 5, 769-778 (1999)
[48] D. Merkle, M. Middendorf, Modelling ACO: composed permutation problems, in: M. Dorigo, G. Di Caro, M. Sampels (Eds.), Ant Algorithms, Proc. ANTS 2002, Third Internat. Workshop, Lecture Notes in Computer Science, Vol. 2463, Springer, Berlin, Germany, 2002, pp. 149-162.; D. Merkle, M. Middendorf, Modelling ACO: composed permutation problems, in: M. Dorigo, G. Di Caro, M. Sampels (Eds.), Ant Algorithms, Proc. ANTS 2002, Third Internat. Workshop, Lecture Notes in Computer Science, Vol. 2463, Springer, Berlin, Germany, 2002, pp. 149-162.
[49] Merkle, D.; Middendorf, M., Modelling the dynamics of ant colony optimization algorithms, Evol. Comput., 10, 3, 235-262 (2002)
[50] D. Merkle, M. Middendorf, Competition controlled pheromone update for ant colony optimization, in: M. Dorigo, M. Birattari, C. Blum, L.M. Gambardella, F. Mondada, T. Stützle (Eds.), Proc. ANTS 2004, Fourth Internat. Workshop on Ant Colony Optimization and Swarm Intelligence, Lecture Notes in Computer Science, Vol. 3172, Springer, Berlin, Germany, 2004, pp. 95-105.; D. Merkle, M. Middendorf, Competition controlled pheromone update for ant colony optimization, in: M. Dorigo, M. Birattari, C. Blum, L.M. Gambardella, F. Mondada, T. Stützle (Eds.), Proc. ANTS 2004, Fourth Internat. Workshop on Ant Colony Optimization and Swarm Intelligence, Lecture Notes in Computer Science, Vol. 3172, Springer, Berlin, Germany, 2004, pp. 95-105. · Zbl 1033.68018
[51] Merkle, D.; Middendorf, M.; Schmeck, H., Ant colony optimization for resource-constrained project scheduling, IEEE Trans. Evol. Comput., 6, 4, 333-346 (2002)
[52] Meuleau, N.; Dorigo, M., Ant colony optimization and stochastic gradient descent, Artif. Life, 8, 2, 103-121 (2002)
[53] Mitchell, T., Machine Learning (1997), McGraw-Hill: McGraw-Hill Boston · Zbl 0913.68167
[54] J. Montgomery, M. Randall, T. Hendtlass, Search bias in constructive metaheuristics and implications for ant colony optimization, in: M. Dorigo, M. Birattari, C. Blum, L.M. Gambardella, F. Mondada, T. Stützle (Eds.), Proc. ANTS 2004, Fourth Internat. Workshop on Ant Colony Optimization and Swarm Intelligence, Lecture Notes in Computer Science, Vol. 3172, Springer, Berlin, Germany, 2004, pp. 391-398.; J. Montgomery, M. Randall, T. Hendtlass, Search bias in constructive metaheuristics and implications for ant colony optimization, in: M. Dorigo, M. Birattari, C. Blum, L.M. Gambardella, F. Mondada, T. Stützle (Eds.), Proc. ANTS 2004, Fourth Internat. Workshop on Ant Colony Optimization and Swarm Intelligence, Lecture Notes in Computer Science, Vol. 3172, Springer, Berlin, Germany, 2004, pp. 391-398.
[55] H. Mühlenbein, G. Paaß. From recombination of genes to the estimation of distributions, in: H.-M. Voigt, W. Ebeling, I. Rechenberg, H.-P. Schwefel (Eds.), Proc. 4th Conf. on Parallel Problem Solving from Nature, PPSN IV, Lecture Notes in Computer Science, Vol. 1411, Springer, Berlin, 1996, pp. 178-187.; H. Mühlenbein, G. Paaß. From recombination of genes to the estimation of distributions, in: H.-M. Voigt, W. Ebeling, I. Rechenberg, H.-P. Schwefel (Eds.), Proc. 4th Conf. on Parallel Problem Solving from Nature, PPSN IV, Lecture Notes in Computer Science, Vol. 1411, Springer, Berlin, 1996, pp. 178-187.
[56] Papadimitriou, C. H.; Steiglitz, K., Combinatorial Optimization—Algorithms and Complexity (1982), Dover Publications Inc.: Dover Publications Inc. New York · Zbl 0503.90060
[57] Prügel-Bennett, A.; Rogers, A., Modelling genetic algorithm dynamics, (Kallel, L.; etal., Theoretical Aspects of Evolutionary Computation, Natural Computing Series (2001), Springer: Springer Berlin, Germany), 59-85 · Zbl 1001.68184
[58] Rechenberg, I., Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (1973), Frommann-Holzboog
[59] Reimann, M.; Doerner, K.; Hartl, R. F., D-ants: savings based ants divide and conquer the vehicle routing problems, Comput. Oper. Res., 31, 4, 563-591 (2004) · Zbl 1061.90024
[60] Robbins, G. E.; Monroe, H., A stochastic approximation method, Ann. Math. Statist., 22, 400-407 (1951) · Zbl 0054.05901
[61] Rubinstein, R. Y., Combinatorial optimization, cross-entropy, ants and rare events, (Stochastic Optimization: Algorithms and Applications (2001), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht, The Netherlands), 303-364 · Zbl 0984.90037
[62] K. Socha, ACO for continuous and mixed-variable optimization, in: M. Dorigo, M. Birattari, C. Blum, L.M. Gambardella, F. Mondada, T. Stützle (Eds.), Proc. ANTS 2004, Fourth Internat. Workshop on Ant Colony Optimization and Swarm Intelligence, Lecture Notes in Computer Science, Vol. 3172, Springer, Berlin, Germany, 2004, pp. 25-36.; K. Socha, ACO for continuous and mixed-variable optimization, in: M. Dorigo, M. Birattari, C. Blum, L.M. Gambardella, F. Mondada, T. Stützle (Eds.), Proc. ANTS 2004, Fourth Internat. Workshop on Ant Colony Optimization and Swarm Intelligence, Lecture Notes in Computer Science, Vol. 3172, Springer, Berlin, Germany, 2004, pp. 25-36.
[63] K. Socha, M. Sampels, M. Manfrin, Ant algorithms for the university course timetabling problem with regard to the state-of-the-art, in: G. Raidl et al. (Ed.), Applications of Evolutionary Computing, Proc. EvoWorkshops 2003, Vol. 2611, 2003, pp. 334-345.; K. Socha, M. Sampels, M. Manfrin, Ant algorithms for the university course timetabling problem with regard to the state-of-the-art, in: G. Raidl et al. (Ed.), Applications of Evolutionary Computing, Proc. EvoWorkshops 2003, Vol. 2611, 2003, pp. 334-345. · Zbl 1033.90508
[64] T. Stützle, An ant approach to the flow shop problem, in: Fifth European Congr. on Intelligent Techniques and Soft Computing, EUFIT’98, 1998, pp. 1560-1564.; T. Stützle, An ant approach to the flow shop problem, in: Fifth European Congr. on Intelligent Techniques and Soft Computing, EUFIT’98, 1998, pp. 1560-1564.
[65] Stützle, T.; Dorigo, M., A short convergence proof for a class of ACO algorithms, IEEE Trans. Evol. Comput., 6, 4, 358-365 (2002)
[66] Stützle, T.; Hoos, H. H., \(MAX-MIN\) ant system, Future Gen. Comput. Systems, 16, 8, 889-914 (2000)
[67] Zlochin, M.; Birattari, M.; Meuleau, N.; Dorigo, M., Model-based search for combinatorial optimization: a critical survey, Ann. Oper. Res., 131, 1-4, 373-395 (2004) · Zbl 1067.90162
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.