Ant colony optimization theory: A survey

By Marco Dorigo, Christian Blum. Theoretical Computer Science, 2005

2,422 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/ffbe49ae5b99b99c9b62f0d7187dfa0b2dbfd185

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Industrial and Manufacturing Engineering

Citations in the corpus

Particle swarm and ant colony algorithms hybridized for improved continuous optimization (2007, background): “ACO is a multiagent approach that simulates the foraging behavior of ants for solving difficult combinatorial optimization problems, such as, the traveling salesman problem and the quadratic assignment problem [5].”
A survey on metaheuristics for stochastic combinatorial optimization (2009, background): “The theoretical convergence properties of the ACO meteheuristic have been recently reviewed in a paper by Dorigo and Blum (2005).”
Evolutionary optimization as applied to inverse scattering problems (2009, background): “For further indications on this issue, the interested reader is referred to the exhaustive survey on the ACO theory available in [55].”
A comprehensive survey: artificial bee colony (ABC) algorithm and applications (2012, methodology): “Duan et al. (2009) introduced a hybrid quantum evolutionary algorithm with ABC optimization. Pulikanti and Singh (2009) proposed a new hybrid approach combining ABC algorithm with a greedy heuristic and a local search for the quadratic knapsack problem.”
Search Based Software Engineering: A Comprehensive Analysis and Review of Trends Techniques and Applications (2009, methodology): “Ayari et al. [46] propose Ant Colony Optimisation (ACO) to generate test input data in the automatic mutation testing.”
The Current State and Future of Search Based Software Engineering (2007, methodology): “Particle Swarm Optimization [91] and Ant Colony Optimization [30] techniques have not been used in the SBSE literature.”
A survey of search methodologies and automated system development for examination timetabling (2009, background): “Ant Algorithms [71, 112] belong to the family of population based techniques.”
Ant colony optimization: Introduction and recent trends (2005, background): “For a recent survey on theoretical work on ACO see [31].”
Fundamentals of natural computing: an overview (2007, background): “Dorigo and Blum [82] list a number of theoretical open problems concerning the ACO algorithm, such as their relation with other probabilistic algorithms, their convergence speed, and the development of new algorithmic components based on solid theoretical foundations.”
Darwin or Lamarck? Future Challenges in Evolutionary Algorithms for Knowledge Discovery and Data Mining (2014, background): “Other examples of such metaheuristics are tabu search, simulated annealing, and evolutionary computation [62].”
Harmony Search as a Metaheuristic Algorithm (2010, background): “dicting each other, but their balanced combination is crucially important to the success of any metaheuristic algorithms [4,6,13].”
A social learning particle swarm optimization algorithm for scalable optimization (2015, background): “Behavior learning is an essential and common process for updating particle behaviors, which is also similar to other learning mechanisms in various swarm intelligence algorithms [18,40,43,59].”
Bio inspired computing - A review of algorithms and scope of applications (2016, methodology): “In this algorithm, the solution is often attempted in a sequence of iterative steps (Dorigo & Blum, 2005; Hong, et al, 2012; Bououden, et al, 2015; Mandloi and Bhatia, 2015; Ghasab et al, 2015).”
Evolutionary techniques in optimizing machining parameters: Review and recent applications (2007-2011) (2012, background): “The quantity of pheromone deposited, which may depend on the quantity and quality of the food, will guide other ants to the food source (Dorigo & Blum, 2005).”