The ant colony optimization algorithm (ACO), introduced by Marco Dorigo [Dor92,DoSt04], is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. They are inspired by the behaviour of ants in finding paths from the colony to food. In mathematics, computing, linguistics, and related disciplines, an algorithm is a procedure (a finite set of well-defined instructions) for accomplishing some task which, given an initial state, will terminate in a defined end-state. ... Marco Dorigo is a research director for the Belgian Funds for Scientific Research (FNRS), and a co-director of IRIDIA, the artificial intelligence lab of the Université Libre de Bruxelles. ... Probability is the extent to which something is likely to happen or be the case[1]. Probability theory is used extensively in areas such as statistics, mathematics, science, philosophy to draw conclusions about the likelihood of potential events and the underlying mechanics of complex systems. ... Subfamilies Aenictogitoninae Agroecomyrmecinae Amblyoponinae (incl. ...

Overview

In the real world, ants (initially) wander randomly, and upon finding food return to their colony while laying down pheromone trails. If other ants find such a path, they are likely not to keep travelling at random, but to instead follow the trail, returning and reinforcing it if they eventually find food (see Ant communication and behavior). Random redirects here. ... Fanning honeybee exposes Nasonov gland (white-at tip of abdomen) releasing pheromone to entice swarm into an empty hive A pheromone is any chemical or set of chemicals produced by a living organism that transmits a message to other members of the same species. ... Random redirects here. ... Subfamilies Aenictogitoninae Agroecomyrmecinae Amblyoponinae (incl. ...

Over time, however, the pheromone trail starts to evaporate, thus reducing its attractive strength. The more time it takes for an ant to travel down the path and back again, the more time the pheromones have to evaporate. A short path, by comparison, gets marched over faster, and thus the pheromone density remains high as it is laid on the path as fast as it can evaporate. Pheromone evaporation has also the advantage of avoiding the convergence to a locally optimal solution. If there were no evaporation at all, the paths chosen by the first ants would tend to be excessively attractive to the following ones. In that case, the exploration of the solution space would be constrained.

Thus, when one ant finds a good (short, in other words) path from the colony to a food source, other ants are more likely to follow that path, and positive feedback eventually leaves all the ants following a single path. The idea of the ant colony algorithm is to mimic this behavior with "simulated ants" walking around the graph representing the problem to solve. Imbibers of alcoholic drinks the unknown strange organisms were called yeast and they were the starting point of the image. ...

Ant colony optimization algorithms have been used to produce near-optimal solutions to the travelling salesman problem. They have an advantage over simulated annealing and genetic algorithm approaches when the graph may change dynamically; the ant colony algorithm can be run continuously and adapt to changes in real time. This is of interest in network routing and urban transportation systems. If a salesman starts at point A, and if the distances between any two points is known, what is the shortest round-trip the salesman can make which will visit all points once and return to point A? The travelling salesman problem[1] [2](TSP) is a problem in discrete... Simulated annealing (SA) is a generic probabilistic meta-algorithm for the global optimization problem, namely locating a good approximation to the global optimum of a given function in a large search space. ... A genetic algorithm (or short GA) is a search technique used in computing to find true or approximate solutions to optimization and search problems. ... This article describes routing in computer networks, a method of finding paths from origins to destinations, along which information can be passed. ...

There are applications of ACO to machine learning and data mining problems, as well. For instance, one modification of the basic ACO metaheuristic which has been studied is to create a model of cemetery maintenance wherein worker ants "cluster" ant corpses. This has been adapted to the unsupervised machine learning task referred to as clustering wherein one wishes to find groups of objects that are "similar." In fact such modified forms of ACO have been shown to give better performance and accuracy than various classical methods such as the well-known k-means algorithm. Clustering can refer to Computer clustering - (in Computer science) the connection of many low-cost computers using special hardware and software such that they can be used as one larger computer. ...

Related methods

Simulated Annealing (SA) is a related global optimization technique which traverses the search space by generating neighbouring solutions of the current solution. A superior neighbour is always accepted. An inferior neighbour is accepted probabilistically based on the difference in quality and a temperature parameter. The temperature parameter is modified as the algorithm progresses to alter the nature of the search. Simulated annealing (SA) is a generic probabilistic meta-algorithm for the global optimization problem, namely locating a good approximation to the global optimum of a given function in a large search space. ...

Tabu search (TS) is similar to Simulated Annealing, in that both traverse the solution space by testing mutations of an individual solution. While simulated annealing generates only one mutated solution, tabu search generates many mutated solutions and moves to the solution with the lowest fitness of those generated. In order to prevent cycling and encourage greater movement through the solution space, a tabu list is maintained of partial or complete solutions. It is forbidden to move to a solution that contains elements of the tabu list, which is updated as the solution traverses the solution space. Tabu search is a mathematical optimization method, belonging to the class of local search techniques. ...

Genetic Algorithms (GA) maintain a pool of solutions rather than just one. The process of finding superior solutions mimics that of evolution, with solutions being combined or mutated to alter the pool of solutions, with solutions of inferior quality being discarded. A genetic algorithm (GA) is an algorithm used to find approximate solutions to difficult-to-solve problems through application of the principles of evolutionary biology to computer science. ...

See also

• Particle swarm optimization
• Stigmergy
• Swarm Intelligence

Particle swarm optimization (PSO) is a form of swarm intelligence. ... Stigmergy is a method of communication in decentralised systems in which the individual parts of the system communicate with one another by modifying their local environment. ... Swarm intelligence (SI) is an artificial intelligence technique based around the study of collective behavior in decentralized, self-organized systems. ...

Publications (selected)

• [Dor92] M. Dorigo, 1992. Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italy.
• [DMC96] M. Dorigo, V. Maniezzo & A. Colorni, 1996. "Ant System: Optimization by a Colony of Cooperating Agents", IEEE Transactions on Systems, Man, and Cybernetics–Part B, 26 (1): 29–41.
• [DG97] M. Dorigo & L. M. Gambardella, 1997. "Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem". IEEE Transactions on Evolutionary Computation, 1 (1): 53–66.
• [DDG99] M. Dorigo, G. Di Caro & L. M. Gambardella, 1999. "Ant Algorithms for Discrete Optimization". Artificial Life, 5 (2): 137–172.
• [BDT99] E. Bonabeau, M. Dorigo et G. Theraulaz, 1999. Swarm Intelligence: From Natural to Artificial Systems, Oxford University Press. ISBN 0-19-513159-2
• [DS04] M. Dorigo & T. Stützle, 2004. Ant Colony Optimization, MIT Press. ISBN 0-262-04219-3

External links

• Ant Colony Optimization Home Page
• ANSI C implementation of Ant Colony Optimization, Thomas Stützle
• C# implementation of Ant Colony Optimization, Lawrence Botley
• Java implementation of Ant Colony Optimization, Andrew Carson
• A list of dissertations related to the field of Ant Colony Optimization
• VisualBots - Freeware multi-agent simulator in Microsoft Excel. Sample programs include genetic algorithm, ACO, and simulated annealing solutions to TSP.
• AntSim v1.0 A visual simulation of Ant Colony Optimization with artificial ants. (Windows Application)