Ant colony optimization

Ant colony optimization

The ant colony optimization algorithm (ACO), introduced by Marco Dorigo in 1992 in his PhD thesis, is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. They are inspired by the behavior of ants in finding paths from the colony to food.

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 traveling at random, but to instead follow the trail, returning and reinforcing it if they eventually find food (see Ant communication).

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 (i.e. short) path from the colony to a food source, other ants are more likely to follow that path, and positive feedback eventually leads 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.

Ant colony optimization algorithms have been used to produce near-optimal solutions to the traveling 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.

Pseudo-code & Formulas

procedure ACO_MetaHeuristic while(not_termination) generateSolutions() pheromoneUpdate() daemonActions() end while end procedure

Arc Selection:

An ant will move from node i to node j with probability

p_{i,j} = frac{ ( au_{i,j}^{alpha}) (eta_{i,j}^{eta}) }{ sum ( au_{i,j}^{alpha}) (eta_{i,j}^{eta}) }

where,

au_{i,j} is the amount of pheromone on arc i,j

alpha is a parameter to control the influence of au_{i,j}

eta_{i,j} is the desirability of arc i,j (a priori knowledge, typically 1/d_{i,j})

eta is a parameter to control the influence of eta_{i,j}

Pheromone Update

au_{i,j} = ho au_{i,j} + Delta au_{i,j}

where,

au_{i,j} is the amount of pheromone on a given arc i,j

ho is the rate of pheromone evaporation

and Delta au_{i,j} is the amount of pheromone deposited, typically given by

Delta au^{k}_{i,j} = egin{cases}1/L_k & mbox{if ant }kmbox{ travels on arc }i,j \0 & mbox{otherwise}end{cases}

where L_k is the cost of the kth ant's tour (typically length).

Common Extensions

#Elitist Ant System
#*The global best solution deposits pheromone on every iteration along with all the other ants
#Max-Min Ant System (MMAS)
#*Added Maximum and Minimum pheromone amounts [τmaxmin]
#*Only global best or iteration best tour deposited pheromone
#*All edges are initialized to τmax and reinitialized to τmax when nearing stagnation.
#Rank-Based Ant System (ASrank)
#*All solutions are ranked according to their fitness. The amount of pheromone deposited is then weighted for each solution, such that the more optimal solutions deposit more pheromone than the less optimal solutions

Related methods

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. This form of algorithm is superior.

Simulated Annealing (SA) is a related global optimization technique which traverses the search space by generating neighboring solutions of the current solution. A superior neighbor is always accepted. An inferior neighbor 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.

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.

Harmony search (HS) is an algorithm based on the analogy between music improvisation and optimization. Each musician (variable) together seeks better harmonies (vectors).

Artificial Immune Systems (AIS) algorithms that are modeled on vertebrate immune systems.

ee also

*Particle swarm optimization
*Stigmergy
*Swarm Intelligence

Publications (selected)

* M. Dorigo, 1992. "Optimization, Learning and Natural Algorithms", PhD thesis, Politecnico di Milano, Italy.
* 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.
* 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.
* M. Dorigo, G. Di Caro & L. M. Gambardella, 1999. "Ant Algorithms for Discrete Optimization". Artificial Life, 5 (2): 137–172.
* E. Bonabeau, M. Dorigo et G. Theraulaz, 1999. "Swarm Intelligence: From Natural to Artificial Systems", Oxford University Press. ISBN 0-19-513159-2
* M. Dorigo & T. Stützle, 2004. "Ant Colony Optimization", MIT Press. ISBN 0-262-04219-3
* M. Dorigo, 2007. [http://www.scholarpedia.org/article/Ant_Colony_Optimization "Ant Colony Optimization"] . Scholarpedia.
* C. Blum, 2005 "ant colony optimization:introduction and recent trends" physics of life review(2) 353-373

External links

* [http://www.aco-metaheuristic.org/ Ant Colony Optimization Home Page]
* [http://www.ict.swin.edu.au/personal/dangus/dissertations.htm A list of dissertations related to the field of Ant Colony Optimization]
* [http://www.visualbots.com/index.htm VisualBots] - Freeware multi-agent simulator in Microsoft Excel. Sample programs include genetic algorithm, ACO, and simulated annealing solutions to TSP.
* [http://www.not-equal.eu/myrmedrome Myrmedrome] A visual simulation of Ant Colony Optimization with artificial ants. (Windows and Linux Application)
* [http://www.nightlab.ch/antsim AntSim v1.0] A visual simulation of Ant Colony Optimization with artificial ants. (Windows Application)
* [http://www.geocities.com/chamonate/hormigas/antfarm Ant Farm Simulator] A simulation of ants food-gathering behaviour (Windows Application and source code available)
* [http://djoh.net/blog/?toute-l-histoire-des-fourmis ANT Colony Algorithm] A Java Simulation of the Path Optimisation, on a changing ground. Presentation and source code available.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Ant Colony Optimization — Algorithme de colonies de fourmis Les algorithmes de colonies de fourmis sont des algorithmes inspirés du comportement des fourmis et qui constituent une famille de métaheuristiques d’optimisation. Initialement proposé par Marco Dorigo et al.… …   Wikipédia en Français

  • Ant colony optimization algorithms — Ant behavior was the inspiration for the metaheuristic optimization technique. In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be… …   Wikipedia

  • Ant colony — A plaster cast of an ant nest. Ant hill and ant tracks, Oxley Wild Rivers National Park …   Wikipedia

  • Bee colony optimization — The bee colony optimization algorithm is inspired by the behaviour of a honey bee colony in nectar collection. This biologically inspired approach is currently being employed to solve continuous optimization problems, training neural networks,… …   Wikipedia

  • Ant — For other uses, see Ant (disambiguation). Ants Temporal range: 130–0 Ma …   Wikipedia

  • Optimization (mathematics) — In mathematics, the term optimization, or mathematical programming, refers to the study of problems in which one seeks to minimize or maximize a real function by systematically choosing the values of real or integer variables from within an… …   Wikipedia

  • Extremal optimization — (EO) is an optimization heuristic inspired by the Bak Sneppen model of self organized criticality from the field of statistical physics. This heuristic was designed initially to address combinatorial optimization problems such as the travelling… …   Wikipedia

  • Mathematical optimization — For other uses, see Optimization (disambiguation). The maximum of a paraboloid (red dot) In mathematics, computational science, or management science, mathematical optimization (alternatively, optimization or mathematical programming) refers to… …   Wikipedia

  • Meta-optimization — concept. In numerical optimization, meta optimization is the use of one optimization method to tune another optimization method. Meta optimization is reported to have been used as early as in the late 1970s by Mercer and Sampson [1] for finding… …   Wikipedia

  • Particle swarm optimization — (PSO) is a swarm intelligence based algorithm to find a solution to an optimization problem in a search space, or model and predict social behavior in the presence of objectives.OverviewParticle swarm optimization is a stochastic, population… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”