Ant Colony Optimisation

ACO

Ant Colony Optimisation is a new class of natural algorithms inspired by the foraging behaviour of natural ant colonies. For more information, please see Marco Dorigo's Ant Colony Optimization Web page, or read the introductory sections in a recent paper of mine, Ant Colony Optimisation for Virtual-Wavelength-Path Routing and Wavelength Allocation.

The Travelling Salesman ACO Applet

This applet demonstrates an ACO algorithm (ant-cycle) for the travelling salesman problem first described in Dorigo M. (1992). Optimization, Learning and Natural Algorithms. Ph.D. Thesis, Politecnico di Milano, Italy (in Italian), and subsequently in three papers:

• Colorni A., M. Dorigo & V. Maniezzo (1992). Distributed Optimization by Ant Colonies. Proceedings of the First European Conference on Artificial Life, Paris, France, F.Varela and P.Bourgine (Eds.), Elsevier Publishing, 134-142. IC.06-ECAL92.ps.gz (52K)
• Colorni A., M. Dorigo & V. Maniezzo (1992). An Investigation of Some Properties of an Ant Algorithm. Proceedings of the Parallel Problem Solving from Nature Conference (PPSN 92), Brussels, Belgium, R.Manner and B.Manderick (Eds.), Elsevier Publishing, 509-520. IC.08-PPSN92.ps.gz (45K)
• Dorigo M., V. Maniezzo & A. Colorni (1996). The Ant System: Optimization by a Colony of Cooperating Agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26(1):29-41. IJ.10-SMC96.ps.gz (105K)

The TSP problem used approximates CCA0 from the second paper. The ant-cycle algorithm uses alpha = 1.0, beta = 2.0, rho = 0.5, an initial tau (pheromone) on each link of 0.1, and a Q of 100. Once the ACO has been started by pressing 'Run', then after each full cycle the links (routes between cities) are displayed coloured by their relative pheromone strength, from the lowest, white (invisible) through dark gray, black, blue, cyan, green, yellow, orange, orange-red to the most attractive, red. The nodes (cities) can be clicked and dragged to new positions within the original problem area, either before or while the ACO runs. (Altho' do this slowly on a slower machine, or the Java Virtual Machine will 'lose' the mouse events!) In addition, the pheromone values on each link can be 'Reset' at any point. To let you see what's going on, the algorithm runs in slow motion - it sleeps for 1 second after every cycle. The source code is available here.