Monday, January 8, 2007


Ant Colony Algorithm

This article on DrDobbs is well worth the read:  Ant Colony Algorithms.

Ant systems are usually used to solve traveling salesman problems. The ant algorithm mimic the behavior of ants in the real world to find a close to optimal solution fast without spending forever evaluation of all possible solutions. Wikipedia describes the algorithm better than I ever could:

In the real world, ants (initially) wander randomly, and upon finding food return to their colony while laying down pheromone trails. If other ants find such a path, they are likely not to keep travelling at random, but to instead follow the trail, returning and reinforcing it if they eventually find food (see Ant communication and behavior).

Over time, however, the pheromone trail starts to evaporate, thus reducing its attractive strength. The more time it takes for an ant to travel down the path and back again, the more time the pheromones have to evaporate. A short path, by comparison, gets marched over faster, and thus the pheromone density remains high as it is laid on the path as fast as it can evaporate. Pheromone evaporation has also the advantage of avoiding the convergence to a locally optimal solution. If there were no evaporation at all, the paths chosen by the first ants would tend to be excessively attractive to the following ones. In that case, the exploration of the solution space would be constrained.

The ant algorithm gives good results fast and have one big advantage over “similar“ methods like genetic algorithms; they can be run continuously so it will adapt to changes in real time. An obstacle like a traffic jam would quickly lead the ants to take a different road.

Don't you just love algorithms? There is always something new to learn that opens your mind to different ways of doing things.


  1. Nice algo! has anybody the proff of reachin definetly the global optimum? faling in local mins is often a main prob, like in neuralNets...

    Waiting for the proof....

  2. The Ant Colony algorithm avoids convergence on local optimal solutions using "pheromone evaporation" (the signal evaporates over time reducing its strength).

    I do not know of any algorithm that is guaranteed to reach global optimum apart form brute force.