Narges Habibi’s Blog

Swarm intelligence (SI) is an artificial intelligence technique based around the study of collective behavior in decentralized, self-organized systems.

SI systems are typically made up of a population of simple agents interacting locally with one another and with their environment. Although there is normally no centralized control structure dictating how individual agents should behave, local interactions between such agents often lead to the emergence of global behavior. Examples of systems like this can be found in nature, including ant colonies, bird flocking, bacterial growth, and fish schooling.

(source: Wikipedia)

Several SI-based algorithms are proposed, like Ant Colony Optimization (ACO), Particle Swarm Intelligence (PSO), Stochastic Diffusion Search (SDS), etc. These algorithms are applied to an impressive number of optimization problems.

ACO is based on the behavior of real ants for finding food. This behavior can be described as follow (a little long, but intresting ):

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 traveling at random, but to instead follow the trail, returning and reinforcing it if they eventually find food.

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.

Thus, when one ant finds a good (short, in other words) path from the colony to a food source, other ants are more likely to follow that path, and positive feedback eventually leaves all the ants following a single path. The idea of the ant colony algorithm is to mimic this behavior with “simulated ants” walking around the graph representing the problem to solve.

(see a good example here.)

You can find my report about Swarm Intelligence here. It introduces SI in general, and Ant Colony Optimization in detail. Also, an ACO-based for Traveling Salesperson problem and a ACO-based routing algorithm, are described.

More information:
- M. Dorigo & G. D. Caro’s paper, the original paper on ACO
- M. Dorigo home page