Ant colony optimization is an optimization technique introduced in the early 1990s. The inspirational source of ant colony optimization is the foraging behavior of real ant colonies. This behavior is exploited in artificial ant colonies to find approximate solutions to problems of discrete optimization, problems of continuous optimization and important problems in telecommunications, such as routing and load balancing. First, we deal with the biological inspiration of the ant colony optimization algorithms. We demonstrate how this biological inspiration can be transferred into an algorithm for discrete optimization. Next, we outline the optimization of ant colonies in more general terms in the context of discrete optimization, and we present some of the ant colony optimization variants that best present themselves today. After summarizing some important theoretical results, we demonstrate how ant colony optimization can be applied to continuous optimization problems.
In the natural world, the ants of some species (initially) roam at random, and upon finding the return of food to their colony while establishing the pheromone trails. If other ants find this path, they probably will not continue to travel randomly, but will follow the path, returning and reinforcing it if they finally find food .
Over time, however, the pheromone trail begins to evaporate, thus reducing its attractive strength. The longer it takes an ant to travel down the road and back again, the longer the pheromones have to evaporate. A short path, by comparison, is paraded more frequently, and therefore the density of pheromones becomes higher in trajectories shorter than the longer ones. Pheromone evaporation also has the advantage of avoiding convergence to a locally optimal solution. If there were no evaporation, the paths chosen by the first ants would tend to be excessively attractive to the next ones. In that case, the exploration of solution space would be limited. The influence of pheromone evaporation on real ant systems is unclear, but it is very important in artificial systems.
The overall result is that when an ant finds a good (ie short) path from the colony to a food source, other ants are more likely to follow that path, and positive feedback eventually leads to all ants following a single path. The idea of the ant colony algorithm is to mimic this behavior with "simulated ants" by walking around the graph representing the problem to be solved.