Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat
Sign Up
Cited by 2,295

The DOI matches its Crossref record; 4 of the 4 references it cites were found in a registry or an index.

Ant colony optimization theory: A survey

Open access
Dorigo, Marco, Blum, Christian·2005·Theoretical Computer Science
DOI 10.1016/j.tcs.2005.05.020
Open this paper in CoChat — free account

Abstract

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.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1016/j.tcs.2005.05.020

Cites

4 of 4 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Show all 4 references

Research works printed but not linked: 48

  1. Baum, 1968, Growth transformations for functions on manifolds, Pacific J. Math., 27, 211, 10.2140/pjm.1968.27.211 · DOI · Paper page
  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. · DOI
  3. C. Blum, Theoretical and Practical Aspects of Ant Colony Optimization, Dissertations in Artificial Intelligence, Vol. 282, Akademische Verlagsgesellschaft Aka GmbH, Berlin, Germany, 2004. · doi:10.1007/978-3-540-28646-2_11
  4. Blum, 2005, Beam-ACO—Hybridizing ant colony optimization with beam search: an application to open shop scheduling, Comput. Oper. Res., 32, 1565, 10.1016/j.cor.2003.11.018 · DOI · Paper page
  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. · doi:10.1007/978-3-540-28646-2_11
  6. Blum, 2004, The hyper-cube framework for ant colony optimization, IEEE Trans. Systems, Man, Cybernet.-Part B, 34, 1161, 10.1109/TSMCB.2003.821450 · DOI · Paper page
  7. Blum, 2005, Search bias in ant colony optimization: on the role of competition-balanced systems, IEEE Trans. Evol. Comput., 9, 159, 10.1109/TEVC.2004.841688 · doi:10.1109/tevc.2004.841688
  8. Blum, 2003, Metaheuristics in combinatorial optimization: overview and conceptual comparison, ACM Comput. Surveys, 35, 268, 10.1145/937503.937505 · DOI · Paper page
  9. Blum, 2002, Ant Colony Optimization for FOP shop scheduling: a case study on different pheromone representations, Vol. 2, 1558
  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. · doi:10.1007/3-540-45712-7_86
  11. Blum, 2004, An ant colony optimization algorithm for shop scheduling problems, J. Math. Model. Algorithms, 3, 285, 10.1023/B:JMMA.0000038614.39977.6f · doi:10.1023/b:jmma.0000038614.39977.6f
  12. Černý, 1985, A thermodynamical approach to the travelling salesman problem: an efficient simulation algorithm, J. Optim. Theory Appl., 45, 41, 10.1007/BF00940812 · DOI · Paper page
  13. Costa, 1997, Ants can color graphs, J. Oper. Res. Soc., 48, 295, 10.1057/palgrave.jors.2600357 · DOI · Paper page
  14. 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.
  15. Deb, 1993, Analyzing deception in trap functions, Vol. 2, 93
  16. 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. · DOI
  17. Deneubourg, 1990, The self-organizing exploratory pattern of the argentine ant, J. Insect Behav., 3, 159, 10.1007/BF01417909 · DOI · Paper page
  18. M. Dorigo, Optimization, learning and natural algorithms (in Italian), Ph.D. Thesis, Dipartimento di Elettronica, Politecnico di Milano, Italy, 1992.
  19. Dorigo, 1996, Ant system: optimization by a colony of cooperating agents, IEEE Trans. Systems, Man, Cybernet.-Part B, 26, 29, 10.1109/3477.484436 · DOI · Paper page
  20. 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. · DOI
  21. Gagné, 2002, Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times, J. Oper. Res. Soc., 53, 895, 10.1057/palgrave.jors.2601390 · doi:10.1057/palgrave.jors.2601390
  22. Gambardella, 2000, Ant colony system hybridized with a new local search for the sequential ordering problem, INFORMS J. Comput., 12, 237, 10.1287/ijoc.12.3.237.12636 · DOI · Paper page
  23. Glover, 1989, Tabu search—Part I, ORSA J. Comput., 1, 190, 10.1287/ijoc.1.3.190 · DOI · Paper page
  24. Glover, 1990, Tabu search—Part II, ORSA J. Comput., 2, 4, 10.1287/ijoc.2.1.4 · DOI · Paper page
  25. F. Glover, G. Kochenberger (Eds.), Handbook of Metaheuristics, Kluwer Academic Publishers, Norwell, MA, 2002. · DOI · Paper page
  26. 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. · DOI
  27. Gutjahr, 2000, A graph-based ant system and its convergence, Future Gen. Comput. Systems, 16, 873, 10.1016/S0167-739X(00)00044-3 · DOI · Paper page
  28. Gutjahr, 2002, ACO algorithms with guaranteed convergence to the optimal solution, Inform. Process. Lett., 82, 145, 10.1016/S0020-0190(01)00258-7 · doi:10.1016/s0020-0190(01)00258-7
  29. M.I. Jordan (Ed.), Learning in Graphical Models, MIT Press, Cambridge, MA, 1998. · DOI · Paper page
  30. L. Kallel, B. Naudts, A. Rogers (Eds.), Theoretical Aspects of Evolutionary Computing, Natural Computing Series, Springer, Berlin, Germany, 2001. · DOI
  31. Kirkpatrick, 1983, Optimization by simulated annealing, Science, 220, 671, 10.1126/science.220.4598.671 · DOI · Paper page
  32. Maniezzo, 1999, Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem, INFORMS J. Comput., 11, 358, 10.1287/ijoc.11.4.358 · DOI
  33. Maniezzo, 1999, The ant system applied to the quadratic assignment problem, IEEE Trans. Data Knowledge Eng., 11, 769, 10.1109/69.806935 · DOI · Paper page
  34. 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.
  35. Merkle, 2002, Modelling the dynamics of ant colony optimization algorithms, Evol. Comput., 10, 235, 10.1162/106365602760234090 · doi:10.1162/106365602760234090
  36. 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. · doi:10.1007/978-3-540-28646-2_9
  37. Merkle, 2002, Ant colony optimization for resource-constrained project scheduling, IEEE Trans. Evol. Comput., 6, 333, 10.1109/TEVC.2002.802450 · DOI · Paper page
  38. Meuleau, 2002, Ant colony optimization and stochastic gradient descent, Artif. Life, 8, 103, 10.1162/106454602320184202 · DOI
  39. 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. · DOI
  40. 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.
  41. Prügel-Bennett, 2001, Modelling genetic algorithm dynamics, 59, 10.1007/978-3-662-04448-3_4 · doi:10.1007/978-3-662-04448-3_4
  42. Reimann, 2004, D-ants: savings based ants divide and conquer the vehicle routing problems, Comput. Oper. Res., 31, 563, 10.1016/S0305-0548(03)00014-5 · DOI · Paper page
  43. 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. · DOI
  44. 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. · DOI
  45. 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.
  46. Stützle, 2002, A short convergence proof for a class of ACO algorithms, IEEE Trans. Evol. Comput., 6, 358, 10.1109/TEVC.2002.802444 · DOI · Paper page
  47. Stützle, 2000, MAX-MIN ant system, Future Gen. Comput. Systems, 16, 889, 10.1016/S0167-739X(00)00043-1 · DOI
  48. Zlochin, 2004, Model-based search for combinatorial optimization: a critical survey, Ann. Oper. Res., 131, 373, 10.1023/B:ANOR.0000039526.52305.af · DOI · Paper page

Cited by

See all 2,295

Metadata

Authors
Dorigo, M., & Blum, C.
Venue
Theoretical Computer Science
Publisher
Elsevier BV
Published
2005-11
Volume
344
Issue
2-3
Pages
243-278
ISSN
0304-3975 (ISSN-L)
DOI
10.1016/j.tcs.2005.05.020
OpenAlex
W2118573797
Cited by
2,295
References
4
FWCI
51.87
Type
journal article
Language
en
Open access
bronze
Licence

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: Ant colony optimization theory: A survey. https://app.cochat.ai/papers/10.1016/j.tcs.2005.05.020
The paper
Dorigo, M., & Blum, C. (2005). Ant colony optimization theory: A survey. Theoretical Computer Science. https://doi.org/10.1016/j.tcs.2005.05.020

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.