Catalogue of Artificial Intelligence Techniques

   

Jump to: Top | Entry | References | Comments

View Maths as: Images | MathML

Ant Colony Optimisation

Keywords: computational intelligence, feedback, metaheuristic, pheromone, swarm, trail

Categories: Search


Author(s): Grigoris Sotiropoulos

A class of metaheuristic algorithms used in solving combinatorial optimisation problems. Ant Colony Optimisation (ACO) algorithms are part of the research field of Swarm Intelligence and are inspired by the behaviour of real ants, which are capable of finding shortest paths from a food source to the ant colony. The first ants initially choose a path at random. All ants, however, also leave a trail of chemicals, called pheromones, along the path they take, and subsequent ants tend to follow the path with the highest pheromone concentration. Pheromones evaporate over time, so the shorter the path, the higher the pheromones concentration along it; a short path is travelled faster, so there is less time for an older pheromone trail to evaporate before the new one is laid. Since more ants will follow a higher-concentration path, this creates a positive feedback loop, eventually making the ants move along a single path.

ACO algorithms simulate this kind of behaviour and have been used successfully to obtain solutions to hard problems, including Travelling Salesman, Vehicle Routing and Quadratic Assignment problems, which reduce to path-finding problems in a graph. Their advantage over other Computational Intelligence approaches, like genetic algorithms, is that they can adapt to any changes in the graph in real time.


References:


Comments:

Add Comment

No comments.