10182

Ant Colony Optimization (ACO)

Have you ever wondered how ants always seem to find the shortest path between their nest and sources of food? Research has shown that ants deposit certain chemicals called pheromones along their trail that attract other ants to follow the same trail. Initially, the ants wander around randomly, but some ants will accidentally stumble upon a food source and return to the nest. Shorter trails will naturally be traveled more often and therefore have a higher concentration of pheromone, which in turn makes it more likely that other ants follow the trail. Over time the majority of the ants will then converge toward the shortest trail. This idea has been used successfully to find near-optimal solutions to relatively large traveling salesman problems (TSP).

DETAILS

Select the size of your TSP (cities). The cities are random points in a 2D Euclidean square and the distance between each pair of cities (the edge weight) is the Euclidean distance. The outline of the algorithm is:
initialize
while there is no convergence
—construct tours
—simulate evaporation
—deposit pheromone
end while
compare the ant solution to the optimal solution, found by FindShortestTour.
Click "run" to get the ants going. During a construction step all ants complete a Hamiltonian cycle, each starting from a randomly selected city.
Initially all edges are assigned an equal amount of pheromone, controlled by the "initial level" slider. After each construction step, the pheromone on each edge is multiplied by a certain evaporation fraction to simulate evaporation. The slider "min/max ratio" sets the minimum pheromone level allowed on an edge to prevent early convergence toward a sub-optimal trail.
Then the pheromone is updated (i.e., deposited) using the ants' trails. Edges belonging to shorter trails are favored and the pheromone deposited is inversely proportional to the length of a trail. An edge with higher level of pheromone or shorter length is assigned higher probability to be chosen by an ant when building a new trail. When calculating the probabilities, the parameters and control the relative importance of pheromone level and length of edge, respectively. As this process in repeated, the edges on the graph with little traffic will fade and the ants' preferred trail will slowly emerge. For larger graphs changes will appear slowly in the beginning.
The algorithm implements an "elitist" approach, allowing only the most efficient ants to deposit pheromone. The dropdown menu "elite ants" controls the corresponding percentage.
The use of a "candidate list" allows the search for the next city to be restricted to the nearest cities. For larger graphs, this increases the speed considerably.
This process is repeated until all ants converge toward a particular trail. By default, at the end of each construction step the algorithm applies a simple tour improvement algorithm (TIA) on each tour. This can be switched off with the "TIA" checkbox.
The checkbox "MMAS" enables the MAX-MIN Ant System algorithm. This algorithm allows only the best-performing ant to deposit pheromone after each iteration. In addition it calculates upper and lower limits for the pheromone dynamically and sets the number of ants to the number of cities. These controls are therefore disabled (dimmed) when "MMAS" is enabled.
After the ants converge to a trail, the result (red) is compared to the usually optimal trail (dashed) found using Mathematica's FindShortestTour.
Click "save" to save the outcome of a particular run. You can change parameters and click "run" again to see how the algorithm performs on the same graph with the new settings. To compare the latest run with the saved run, click "toggle". Click "stop" to abort a run. Changing the "random seed" or clicking "run" will create a new graph. Changing "random seed" back to a previously used value, will let you use that particular graph again.
This implementation of ACO is just one of many. For more information, see the references.
Thanks to my colleague Cağan Korkmaz, the Koç School, Istanbul, for inspiration, suggestions and time spent on testing.
References
[1] M. Dorigo and T. Stützle, "From Real to Artificial Ants," Ant Colony Optimization, Cambridge, MA: Bradford Books, 2004 pp. 1–25.
[2] M. Dorigo. "Ant Colony Optimization." Scholarpedia. (Oct 21, 2011) www.scholarpedia.org/article/Ant_colony_optimization.
[3] T. Stützle and H. H. Hoos, "MAX-MIN Ant System," Future Generation Computer Systems, 16(8), 2000 pp. 889–914.

PERMANENT CITATION

 Share: Embed Interactive Demonstration New! Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details » Download Demonstration as CDF » Download Author Code »(preview ») Files require Wolfram CDF Player or Mathematica.

 RELATED RESOURCES
 The #1 tool for creating Demonstrations and anything technical. Explore anything with the first computational knowledge engine. The web's most extensive mathematics resource. An app for every course—right in the palm of your hand. Read our views on math,science, and technology. The format that makes Demonstrations (and any information) easy to share and interact with. Programs & resources for educators, schools & students. Join the initiative for modernizing math education. Walk through homework problems one step at a time, with hints to help along the way. Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet. Knowledge-based programming for everyone.