Ant Colony Optimisation (ACO) is a relatively new nature-inspired meta-heuristic for solving combinatorial optimisation problems. It is a highly parallel multi-agent method that is - as the name suggests - inspired by the behaviour of real ants, in particular by foraging activities.
 
The original ACO algorithm was first applied to the well-known traveling salesman problem, as the structure of this problem is closest to the biological inspiration of foraging and nest building ants. Generalizations to other problems, such as the quadratic assignment problem soon followed, and today ACO (often hybridised with local search or other methods) is among the most promising meta heuristics for many industrially relevant problems.
 
As with all meta-heuristics, tailoring the generic algorithm to a particular problem instance is an indispensable step. To understand how ACO behaves in particular problem domains and what can be achieved with modifications, such as including various forms of local search, it is crucial to be able to prototype and simulate ACO algorithms quickly.

We have developed a complete simulation environment for ACO algorithms that the user allows such rapid prototyping. It provides the basic meta heuristics as a framework which can be customized by high-level scripting. Problem instances can either be entered in an interactive visual editor or textually. and the ACO execution as well as the development of numerical properties during the optimisation can be visualized.

The simulator it not only useful for algorithm development, but can also be used for algorithm visualization in teaching optimisation.
 
Core Reference
“Inspiration for optimization from social insect behaviour”
by E. Bonabeau, M. Dorigo and G. Theraulaz
in Nature 406, 39 - 42 (2000)
 
Student
Amir Mina
 
Supervisor
Bernd Meyer
 
Type
Master of IT
 
Project Start
June 2001
 
Completion
June 2002