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

The DOI matches its Crossref record; 63 of the 63 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

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.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

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

63 of 63 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.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

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

Research works printed but not linked: 10

  1. 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
  2. Blum, 2002, Ant Colony Optimization for FOP shop scheduling: a case study on different pheromone representations, Vol. 2, 1558
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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.
  8. Merkle, 2002, Modelling the dynamics of ant colony optimization algorithms, Evol. Comput., 10, 235, 10.1162/106365602760234090 · doi:10.1162/106365602760234090
  9. 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
  10. 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

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)
OpenAlex
W2118573797
Cited by
2,295
References
63
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

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.