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.

[1] M. Dorigo and T. Stützle, "From Real to Artificial Ants,"

*Ant Colony Optimization*, Cambridge, MA: Bradford Books, 2004 pp. 1–25.

[3] T. Stützle and H. H. Hoos,

"MAX-MIN Ant System," *Future Generation Computer Systems*,

**16**(8), 2000 pp. 889–914.