Ant Colony Optimization (ACO)

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

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).

Contributed by: Rasmus Kamper (March 2012)
Open content licensed under CC BY-NC-SA


Snapshots


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:

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.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send