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 accessAbstract
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.
Integrity signals
Registry
Cites
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.
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
Holland, J. H. (1992) · The MIT Press eBooks · doi:10.7551/mitpress/1090.001.0001 · Cited by 47,002
Optimization by Simulated Annealing
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983) · Science · doi:10.1126/science.220.4598.671 · Cited by 45,134
Ant system: optimization by a colony of cooperating agents
Dorigo, M., Maniezzo, V., & Colorni, A. (1996) · IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) · doi:10.1109/3477.484436 · Cited by 12,067
Self-citationA Stochastic Approximation Method
Robbins, H., & Monro, S. (1951) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177729586 · Cited by 9,643
Ant colony system: a cooperative learning approach to the traveling salesman problem
Dorigo, M., & Gambardella, L. M. (1997) · IEEE Transactions on Evolutionary Computation · doi:10.1109/4235.585892 · Cited by 8,081
Self-citationInformation theory and statistics
(1959) · Journal of the Franklin Institute · doi:10.1016/0016-0032(59)90368-0 · Cited by 7,094
(2007) · Handbook of Approximation Algorithms and Metaheuristics · doi:10.1201/9781420010749-33 · Cited by 6,607
Combinatorial Optimization: Algorithms and Complexity.
Johnson, D. S., Papadimitriou, C. H., & Steiglitz, K. (1984) · The American Mathematical Monthly · doi:10.2307/2322374 · Cited by 5,942
Glover, F., & Laguna, M. (1997) · Cited by 5,679
Glover, F. (1990) · ORSA Journal on Computing · doi:10.1287/ijoc.2.1.4 · Cited by 5,647
Glover, F. (1989) · ORSA Journal on Computing · doi:10.1287/ijoc.1.3.190 · Cited by 5,106
Combinatorial optimization:Algorithms and complexity
Rabiner, L. (1984) · IEEE Transactions on Acoustics, Speech, and Signal Processing · doi:10.1109/tassp.1984.1164450 · Cited by 3,576
Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm
Černý, V. (1985) · Journal of Optimization Theory and Applications · doi:10.1007/bf00940812 · Cited by 3,436
(2003) · International Series in Operations Research & Management Science · doi:10.1007/b101874 · Cited by 3,430
Dorigo, M., & Stützle, T. (2004) · The MIT Press eBooks · doi:10.7551/mitpress/1290.001.0001 · Cited by 3,330
Self-citationOptimization, Learning and Natural Algorithms
Dorigo, M. (1992) · Medical Entomology and Zoology · Cited by 3,307
Self-citationMetaheuristics in combinatorial optimization: Overview and conceptual comparison
Blum, C., & Roli, A. (2003) · ACM Computing Surveys · doi:10.1145/937503.937505 · Cited by 3,236
Self-citationGlover, F., & Laguna, M. (1997) · doi:10.1007/978-1-4615-6089-0 · Cited by 3,001
Artificial Intelligence through Simulated Evolution
Fogel, L. J., Owens, A. J., & Walsh, M. J. (1966) · International Linear Collider · Cited by 2,796
Hoos (2000) · doi:10.1016/s0167-739x(00)00043-1 · Cited by 2,737
(2003) · Selected Papers of Alan J Hoffman · doi:10.1142/9789812796936_others05 · Cited by 2,465
Evolutionsstrategie : Optimierung technischer Systeme nach Prinzipien der biologischen Evolution
Rechenberg, I. (1973) · Frommann-Holzboog eBooks · Cited by 2,440
(1998) · Springer eBooks · doi:10.1007/978-94-011-5014-9 · Cited by 2,418
Metaheuristics in Combinatorial Optimization
Gendreau, M., & Potvin, J.-Y. (2005) · Annals of Operations Research · doi:10.1007/s10479-005-3971-7 · Cited by 2,338
Corne, D., Dorigo, M., Glover, F., Dasgupta, D., Moscato, P., Poli, R., & Price, K. V. (1999) · Cited by 2,136
Self-citationGenetic Algorithms and Simulated Annealing
Davis, L. D. (1987) · Cited by 1,759
AntNet: Distributed Stigmergetic Control for Communications Networks
Di Caro, G., & Dorigo, M. (1998) · Journal of Artificial Intelligence Research · doi:10.1613/jair.530 · Cited by 1,579
Self-citationVent, W. (1975) · Feddes Repertorium · doi:10.1002/fedr.19750860506 · Cited by 1,331
Stochastic Local Search: Foundations & Applications
Hoos, H. H., & St�tzle, T. (2004) · Medical Entomology and Zoology · Cited by 1,227
From recombination of genes to the estimation of distributions I. Binary parameters
Mühlenbein, H., & Paaß, G. (1996) · Lecture Notes in Computer Science · doi:10.1007/3-540-61723-x_982 · Cited by 1,207
Information Theory and Statistics.
Lindley, D. V., & Kullback, S. (1959) · Journal of the American Statistical Association · doi:10.2307/2282528 · Cited by 960
(2004) · Lecture Notes in Computer Science · doi:10.1007/b98643 · Cited by 957
The self-organizing exploratory pattern of the argentine ant
Deneubourg, J. L., Aron, S., Goss, S., & Pasteels, J. M. (1990) · Journal of Insect Behavior · doi:10.1007/bf01417909 · Cited by 921
Ant colony optimization for resource-constrained project scheduling
Merkle, D., Middendorf, M., & Schmeck, H. (2002) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2002.802450 · Cited by 759
The ant system applied to the quadratic assignment problem
Maniezzo, V., & Colorni, A. (1999) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/69.806935 · Cited by 744
MACS-VRPTW: a multiple ant colony system for vehicle routing problems with time windows
Gambardella, L. M., Taillard, É. D., & Agazzi, G. (1999) · Cited by 725
Costa, D., & Hertz, A. (1997) · Journal of the Operational Research Society · doi:10.1057/palgrave.jors.2600357 · Cited by 497
Fitness Distance Correlation as a Measure of Problem Difficulty for Genetic Algorithms
Jones, T., & Forrest, S. (1995) · Cited by 469
MIMIC: Finding Optima by Estimating Probability Densities
Bonet, J. S. D., Isbell, C. L., & Viola, P. A. (1996) · Cited by 457
The Hyper-Cube Framework for Ant Colony Optimization
Blum, C., & Dorigo, M. (2004) · IEEE Transactions on Systems, Man and Cybernetics, Part B (Cybernetics) · doi:10.1109/tsmcb.2003.821450 · Cited by 432
Self-citationA short convergence proof for a class of ant colony optimization algorithms
Stutzle, T., & Dorigo, M. (2002) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2002.802444 · Cited by 427
Self-citationBlum, C. (2005) · Computers & Operations Research · doi:10.1016/j.cor.2003.11.018 · Cited by 421
Self-citationD-Ants: Savings Based Ants divide and conquer the vehicle routing problem
Reimann, M., Doerner, K., & Hartl, R. F. (2004) · Computers & Operations Research · doi:10.1016/s0305-0548(03)00014-5 · Cited by 387
An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem
Gambardella, L. M., & Dorigo, M. (2000) · INFORMS Journal on Computing · doi:10.1287/ijoc.12.3.237.12636 · Cited by 373
Self-citationA Graph-based Ant System and its convergence
Gutjahr, W. J. (2000) · Future Generation Computer Systems · doi:10.1016/s0167-739x(00)00044-3 · Cited by 368
Growth transformations for functions on manifolds
Baum, L. E., & Sell, G. (1968) · Pacific Journal of Mathematics · doi:10.2140/pjm.1968.27.211 · Cited by 363
Exact and Approximate Nondeterministic Tree-Search Procedures for the Quadratic Assignment Problem
Maniezzo, V. (1999) · INFORMS journal on computing · doi:10.1287/ijoc.11.4.358 · Cited by 338
Analyzing Deception in Trap Functions
Deb, K., & Goldberg, D. E. (1993) · Foundations of Genetic Algorithms · doi:10.1016/b978-0-08-094832-4.50012-x · Cited by 334
Simple Genetic Algorithms and the Minimal, Deceptive Problem
Goldberg, D. E. (1987) · Medical Entomology and Zoology · Cited by 297
Intelligence Through Simulated Evolution: Forty Years of Evolutionary Programming
Fogel, L. J. (1999) · Medical Entomology and Zoology · Cited by 262
Model-Based Search for Combinatorial Optimization: A Critical Survey
Zlochin, M., Birattari, M., Meuleau, N., & Dorigo, M. (2004) · Annals of Operations Research · doi:10.1023/b:anor.0000039526.52305.af · Cited by 247
Self-citationAnt Colony Optimization for the Total Weighted Tardiness Problem
den Besten, M., Stützle, T., & Dorigo, M. (2000) · Lecture Notes in Computer Science · doi:10.1007/3-540-45356-3_60 · Cited by 219
Self-citationACO for Continuous and Mixed-Variable Optimization
Socha, K. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-28646-2_3 · Cited by 199
Stochastic Optimization: Algorithms and Applications
(2001) · Applied Optimization · doi:10.1007/978-1-4757-6594-6 · Cited by 198
An Ant Approach to the Flow Shop Problem
Stützle, T. (1998) · Cited by 183
Pheromone Modification Strategies for Ant Algorithms Applied to Dynamic TSP
Guntsch, M., & Middendorf, M. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-45365-2_22 · Cited by 177
Theoretical Aspects of Evolutionary Computing
(2001) · Natural computing series · doi:10.1007/978-3-662-04448-3 · Cited by 169
Ant Algorithms for the University Course Timetabling Problem with Regard to the State-of-the-Art
Socha, K., Sampels, M., & Manfrin, M. (2003) · Lecture Notes in Computer Science · doi:10.1007/3-540-36605-9_31 · Cited by 167
Combinatorial Optimization, Cross-Entropy, Ants and Rare Events
Rubinstein, R. Y. (2001) · Applied optimization · doi:10.1007/978-1-4757-6594-6_14 · Cited by 112
Ant Colony Optimization and Stochastic Gradient Descent
Meuleau, N., & Dorigo, M. (2002) · Artificial Life · doi:10.1162/106454602320184202 · Cited by 98
Self-citationToward the Formal Foundation of Ant Programming
Birattari, M., Di, G. A., & Dorigo, M. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45724-0_16 · Cited by 63
Self-citationUpdating ACO Pheromones Using Stochastic Gradient Ascent and Cross-Entropy Methods
Dorigo, M., Zlochin, M., Meuleau, N., & Birattari, M. (2002) · Lecture notes in computer science · doi:10.1007/3-540-46004-7_3 · Cited by 25
Self-citationSearch Bias in Constructive Metaheuristics and Implications for Ant Colony Optimisation
Montgomery, J., Randall, M., & Hendtlass, T. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-28646-2_39 · Cited by 16
Research works printed but not linked: 10
- 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
- Blum, 2002, Ant Colony Optimization for FOP shop scheduling: a case study on different pheromone representations, Vol. 2, 1558
- 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
- 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
- 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
- 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
- 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.
- Merkle, 2002, Modelling the dynamics of ant colony optimization algorithms, Evol. Comput., 10, 235, 10.1162/106365602760234090 · doi:10.1162/106365602760234090
- 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
- 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
Slime mould algorithm: A new method for stochastic optimization
Li, S., Chen, H., Wang, M., Heidari, A. A., & Mirjalili, S. (2020) · Future Generation Computer Systems · doi:10.1016/j.future.2020.03.055 · Cited by 3,036
Atashpaz-Gargari, E., & Lucas, C. (2007) · 2007 IEEE Congress on Evolutionary Computation · doi:10.1109/cec.2007.4425083 · Cited by 2,628
A comprehensive survey: artificial bee colony (ABC) algorithm and applications
Karaboga, D., Gorkemli, B., Ozturk, C., & Karaboga, N. (2014) · Artificial Intelligence Review · doi:10.1007/s10462-012-9328-0 · Cited by 1,975
A survey on optimization metaheuristics
Boussaïd, I., Lepagnot, J., & Siarry, P. (2013) · Information Sciences · doi:10.1016/j.ins.2013.02.041 · Cited by 1,655
Black hole: A new heuristic optimization approach for data clustering
Hatamlou, A. (2013) · Information Sciences · doi:10.1016/j.ins.2012.08.023 · Cited by 1,370
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
- www.elsevier.com/tdm/userlicense/1.0/ (tdm)
- www.elsevier.com/open-access/userlicense/1.0/ (vor, 2851 d)
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.