×

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
[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
[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
[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
[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
[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
[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)
[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
[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
[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
[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
[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)
[49] Merkle, D.; Middendorf, M., Modelling the dynamics of ant colony optimization algorithms, Evol. Comput., 10, 3, 235-262 (2002)
[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
[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
[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.