Ant algorithm

from Wikipedia, the free encyclopedia
Certain behavior patterns of the ants form the basis for optimization algorithms (here Dorylus ).

Ant algorithms belong to the metaheuristics for methods of combinatorial optimization that are based on the model behavior of real ants when searching for food. Most ant algorithms also fulfill the ACO (Ant Colony Optimization) metaheuristic presented by Marco Dorigo .

Natural role model

1: The first ant finds a source of food (F), uses the path (a), then it reaches the nest (N), and leaves a trail of pheromones. 2: Other ants follow the first one of 4 possible paths. 3: The ants follow the shortest path.
Certain behavior of ants was used to formulate optimization algorithms. The shortest path in a graph between two points A and B is searched for with an ant colony algorithm (ACS).

When searching for food, individual ants excrete a scent ( pheromone ) along their path . Other ants are more likely to choose a route with a higher concentration of pheromones. If you connect a food source with two paths of different lengths to the nest in an experiment, the ants search for food on both paths with about the same frequency. However, the ants on the shorter path return from the feeding place more quickly, so that over time a higher pheromone concentration prevails on the shortest path than on the other. As a result, the following ants prefer this route: They seem to be walking along a road, an ant road has emerged.

This type of ant optimization was already observed in the 1940s by Richard P. Feynman , who later won the Nobel Prize in Physics , and was vividly described in his popular book Surely you are joking, Mr. Feynman .

Transfer to algorithms

This approach can be described as swarm intelligence : a higher level of performance (here as an example the solution to an optimization problem, namely the search for the shortest route) is achieved through the interaction of many simple actors who can only contribute a part to the overall solution. That's why ant algorithms can also be assigned to agent-based models .

The first ant algorithm, called Ant System (AS), was presented by the Italian scientist Marco Dorigo (1991, 1996). He applied AS to the well-known IT problem of the traveling salesman, since a transfer from the search for the shortest possible paths to this problem is obvious.

In the following years, Luca Maria Gamberdella with the Ant Colony System (ACS, 1997) and Thomas Stützle with the Max-Min Ant System (MMAS, 1999) provided important extensions and modifications , with which the best results for the traveling salesman problem have so far been achieved.

Ant algorithms can be used to solve combinatorial optimization problems in particular, for example project planning problems or the quadratic allocation problem , IP routing or logistics problems . Since these are heuristic optimization methods, it cannot be guaranteed that the optimal solution will always be found. Therefore, it only makes sense to use it if an optimal solution does not necessarily have to be found or cannot be found in an acceptable computing time.

history

  • 2000: Special edition of a scientific journal on ant algorithms
  • 2000: Gutjahr provides the first evidence of convergence for an ant algorithm
  • 2001: First use of the ant algorithms by companies (Eurobios and AntOptima)
  • 2001: Iredi u. a. publish the first multi-target algorithm

Applications

see also backpack problem
  • Bus routes, garbage collection, postal and delivery routes.
  • Machine occupancy problem: Minimizing the transport time for production sites that are far apart: Realized by Unilever in England and Vincent Darley from the Bios Group in Santa Fe (New Mexico).
  • Route optimization for the replenishment of production lines with minimal use of means of transport (route formation, guidance, timing in connection with the container selection); realized in the layout-based logistics planning system MALAGA with algorithms from INPRO.
  • Loading of paint shops: Batch formation to minimize color changes: Realized at DaimlerChrysler.
  • Production control: lot formation to minimize set-up times and compliance with deadlines at ebm-papst, St. Georgen; realized through a program by Carpe Retem.
  • Protein folding : 20 amino acids are combined into proteins with 100 amino acids → 20 100 , this results in about 10 130 different proteins.
  • Telephone network and Internet: With ACO, free routes can be found quickly during operation (e.g. Antnet ).
  • Personnel deployment planning for airlines: flight attendants and pilots are planned monthly, taking into account periods of rest, etc.
  • Forklift control systems : Optimal control and utilization of vehicles and routes.

TSP with ACO

Screendumps of a Traveling Salesman run with ACO

The traveling salesman (TSP) problem can be handled very efficiently with ACO. In the example, TSP is calculated with 30 “cities” or destinations (approx. 4.4 · 10 30 possible routes). The strength of ACO to process changes in the ongoing search process self-adaptively is clear in the example. When moving a destination point in the route found after 20 seconds, the algorithm makes another good route suggestion 10 seconds later (without reinitialization) (see combinatorics ).

literature

  • M. Dorigo, M. Birattari, T. Stützle: Ant Colony Optimization: Artificial Ants as a Computational Intelligence Technique . In: IEEE Computational Intelligence Magazine . Volume 1, No. 4 , 2006, p. 28-39 .
  • Johann Dréo, Alain Petrowski, Éric Taillard, Patrick Siarry: Métaheuristiques pour l'optimisation difficile . Ed. Eyrolles, Paris 2003, ISBN 2-212-11368-4 (French, 356 pp., Extrait concernant les algorithmes de colonies de fourmis [PDF; 933 kB ]).
  • Éric Bonabeau, Marco Dorigo, Guy Theraulaz: Swarm Intelligence: From Natural to Artificial Systems . Oxford University Press, 1999, ISBN 0-19-513159-2 .
  • M. Dorigo, T. Stützle: Ant Colony Optimization . MIT Press / Bradford Books, Cambridge MA 2004, ISBN 0-262-04219-3 .

Web links

Individual evidence

  1. ↑ http://www.mathpages.com/home/kmath320/kmath320.htm
  2. ↑ M. Dorigo, G. Di Caro et T. Stützle, special issue on "Ant Algorithms" , Future Generation Computer Systems, volume 16, numéro 8, 2000.
  3. ^ WJ Gutjahr, A graph-based Ant System and its convergence , Future Generation Computer Systems, volume 16, pages 873-888, 2000.
  4. ↑ Eurobios and AntOptima .
  5. ↑ S. IREDI, D. Merkle et M. Middendorf, Bi-Criterion Optimization with Multi Colony Ant Algorithms , Evolutionary Multi-Criterion Optimization, First International Conference (EMO'01), Zurich, Springer Verlag, pages 359-372., 2001