ant colony optimization
In plain wordsA method for finding good routes and schedules inspired by how ants find short paths to food: simulated ants leave 'scent' on good paths, which attracts other ants, so the best routes gradually stand out.
A metaheuristicmetaheuristic, n.: A general-purpose strategy for finding good answers to hard problems, such as imitating evolution or cooling metal, that can be adapted to many different problems instead of being designed for just one. for combinatorial optimization, especially routing and sequencing, in which artificial ants construct candidate solutions step by step — for the traveling salesman problem, choosing which city to visit next — with probabilities that depend on pheromone values attached to the options and on a problem-specific heuristicheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer. such as inverse distance. After each iteration pheromone evaporates everywhere and is reinforced on the components of good solutions, so the colony's shared memory concentrates search on promising regions while evaporation prevents premature lock-in. Variants include Ant Colony System and MAX–MIN Ant System, usually combined with local searchlocal search, n.: A family of problem-solving methods that start with some complete answer, however poor, and keep improving it by small changes, instead of building an answer piece by piece from scratch.. Applications include vehicle routing, network routing, scheduling and assembly-line balancing.
Origin
Introduced as the Ant System by Marco Dorigo with Alberto Colorni and Vittorio Maniezzo, first at a 1991 artificial-life conference and then in Dorigo's 1992 doctoral thesis at the Politecnico di Milano, inspired by Jean-Louis Deneubourg and colleagues' experiments showing how Argentine ants choose the shorter of two bridges. The name 'ant colony optimization' was adopted in 1999.
Related
- swarm intelligenceswarm intelligence, n.: The teamwork that appears when crowds of simple creatures or machines, such as ants, bees or small robots, each respond only to what is nearby, with nobody in charge, yet together solve problems.
- particle swarm optimizationparticle swarm optimization, n.: An optimization method inspired by flocking birds: candidate solutions 'fly' through the space of possibilities, each pulled toward the best spot it has found and the best spot its neighbors have found.
- metaheuristicmetaheuristic, n.: A general-purpose strategy for finding good answers to hard problems, such as imitating evolution or cooling metal, that can be adapted to many different problems instead of being designed for just one.
- local searchlocal search, n.: A family of problem-solving methods that start with some complete answer, however poor, and keep improving it by small changes, instead of building an answer piece by piece from scratch.
- evolutionary computationevolutionary computation, n.: Problem-solving by simulated evolution, much as breeders improve crops: keep many candidate answers, let the better ones produce slightly altered offspring, drop the worse, and repeat for many rounds.
Sources
- Dorigo, M., Maniezzo, V. & Colorni, A. (1996). Ant System: Optimization by a Colony of Cooperating Agents. IEEE Transactions on Systems, Man, and Cybernetics B 26(1), 29–41.
- Dorigo, M. & Stützle, T. (2004). Ant Colony Optimization. MIT Press.
Mentioned in
swarm intelligenceswarm intelligence, n.: The teamwork that appears when crowds of simple creatures or machines, such as ants, bees or small robots, each respond only to what is nearby, with nobody in charge, yet together solve problems., traveling salesman problemtraveling salesman problem, n.: The puzzle of planning a round trip through a list of cities that stops at each one once and covers the least distance. It is easy to state, but the number of possible routes explodes as cities are added., metaheuristicmetaheuristic, n.: A general-purpose strategy for finding good answers to hard problems, such as imitating evolution or cooling metal, that can be adapted to many different problems instead of being designed for just one., particle swarm optimizationparticle swarm optimization, n.: An optimization method inspired by flocking birds: candidate solutions 'fly' through the space of possibilities, each pulled toward the best spot it has found and the best spot its neighbors have found.