Ant colony optimization algorithms

Ant algorithms are one of the metaheuristics process for combinatorial optimization, based on the model-like behavior of real ants when foraging. Most ant algorithms also meet the presented by Marco Dorigo ACO ( Ant Colony Optimization) metaheuristics.

Natural model

When foraging individual ants differ along its path from a fragrance ( pheromone ). Other ants likely choose a path with a higher concentration of pheromone. If you connect in an experiment of a food source with two different lengths due to the nest, the ants enter in their search for food both ways about equally. However, the ants quickly return to the shorter path back from the feed point, so that prevails at the time on the shortest path has a higher concentration than the other pheromone. As a result, the descendant ants select preferred this route: They seem to run along a road, a trail has been created.

This type of ant optimization has already been observed in the 1940s by the later Nobel Prize winner Richard P. Feynman and 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 power ( on the example of solving an optimization problem, namely the search for the shortest route ) is provided by the interaction of many simple actors who only able to provide part of the overall solution, respectively. So we can ant algorithms also assign the agent-based models.

The first ant algorithm, called Ant System (AS), was presented by the Italian scientists Marco Dorigo (1991, 1996). He turned on the AS -known informatic problem traveling salesman, as a transfer from finding shortest paths is obvious to this problem.

Important enhancements and modifications delivered in subsequent years Luca Maria Gamberdella with Ant Colony System (ACS, 1997) and Thomas Stützle with Max -Min Ant System ( MMAS, 1999), with the so far the best results for the traveling salesman problem ends were achieved.

With ant algorithms can be solved especially combinatorial optimization problems, such as project scheduling problems or the quadratic assignment problem, or IP routing problems of logistics. Since it is heuristic optimization methods can not be guaranteed that the optimum solution is found. Therefore, an application is also only useful when an optimal solution does not necessarily have found or can not be found in a reasonable computing time.

History

  • 2000: special issue of a scientific journal on ant algorithms.
  • 2000: Gutjahr leads first proof of convergence for an ant algorithm.
  • 2001: the first use of ant algorithms of companies ( Eurobios and AntOptima ) ( Eurobios et AntOptima ).
  • 2001: IREDI et al publish the first multi- objective algorithm.

Applications

  • Bus routes, garbage disposal, postal and delivery routes.
  • Machine scheduling problem: Minimization of transport time in spatially far apart production: Finished at Unilever in England and Vincent Darley of the Bios Group in Santa Fe ( New Mexico).
  • Route optimization for replenishment of production lines with minimal transportation use (Route education, man-agement, overclocking in conjunction with the container selection); implemented in the layout-based logistics planning system MALAGA with algorithms of INPRO.
  • Loading of painting: lot sizing to minimize color change: Finished at DaimlerChrysler.
  • Production control: lot sizing for minimizing set-up times and compliance from end dates at ebm -papst St. Georgen; realized through a program of Carpe retem.
  • Protein folding: 20 amino acids are combined to form proteins with 100 amino acids → 20100, this yields about 10130 different proteins.
  • Telephone network and the Internet: By ACO fast free series can be found and that during operation (eg Antnet ).
  • Staff scheduling in airlines: flight attendants and pilots are planned taking into account periods of rest, etc. monthly.
  • Stacker control: Optimal control and utilization of vehicles and roadways.

TSP with ACO

The problem of a Salesman ( TSP) can be very efficiently handled with ACO. In the example, the TSP with 30 " cities" or targets calculated (about 4.4 x 1030 possible ways ). The strength of ACO, to handle changes in the current search process self-adaptive, can be seen in the example. When moving a target point in the route found after 20 seconds a good way proposal is already 10 seconds later ( without reinitialization ) by the algorithm again made ​​(see combinatorics ).

55915
de