Tag: optimization algorithms

There are even increasing efforts in searching and developing algorithms that can find solutions to combinatorial optimization problems. In this way, the Ant Colony Optimization Metaheuristic takes inspiration from biology and proposes different versions of still more efficient algorithms.

Overview

Ant Colony Optimization (ACO) is a paradigm for designing metaheuristic algorithms for combinatorial optimization problems. The essential trait of ACO algorithms is the combination of a priori information about the structure of a promising solution with a posteriori information about the structure of previously obtained good solutions.

ACO is a class of algorithms, whose first member, called the Ant System, was initially proposed by Colorni, Dorigo, and Maniezzo The main underlying idea, loosely inspired by the behavior of real ants, is that of a parallel search over several constructive computational threads based on local problem data and on a dynamic memory structure containing information on the quality of the previously obtained result. The collective behavior emerging from the interaction of the different search threads has proved effective in solving combinatorial optimization (CO) problems.

More specifically, we can say that “Ant Colony Optimization (ACO) is a population-based, general search technique for the solution of difficult combinatorial problems which is inspired by the pheromone trail laying behavior of real ant colonies.”

ACO Principle

Ant Colony Optimization principles are based on the natural behavior of ants. In their daily life, one of the tasks ants have to perform is to search for food, in the vicinity of their nest. While walking in such a quest, the ants deposit a chemical substance called pheromone in the ground.

At first, the ants wander randomly. When an ant finds a source of food, it walks back to the colony leaving "markers" (pheromones) that show the path has food. When other ants come across the markers, they are likely to follow the path with a certain probability. If they do, they then populate the path with their own markers as they bring the food back. As more ants find the path, it gets stronger until there are a couple of streams of ants traveling to various food sources near the colony. Because the ants drop pheromones every time they bring food, shorter paths are more likely to be stronger, hence optimizing the "solution."

Ant Colony Optimization (ACO) is an example of how inspiration can be drawn from seemingly random, low-level behavior to counter problems of great complexity. A specific focus lies on the collective behavior of ants after being confronted with a choice of path when searching for a food source (see Figure 1). Ants deposit pheromones on the ground having selected a path, with the result that fellow ants tend to follow the path with a higher pheromone concentration. This form of communication allows ants to transport food back to their nest in a highly effective manner. Following random fluctuations, one of the bridges presents a higher pheromone concentration. Eventually, the entire colony converges toward the use of the same bridge.

Figure 1: This shows the potential paths a colony can take from nest (N) to food (F), with the route eventually converging as a result of random fluctuations in pheromone deposits.

ACO Algorithm

The ant colony algorithm is an algorithm for finding optimal paths that are based on the behavior of ants searching for food. Here we are presenting an ACO algorithm

Table 1: ACO Algorithm

References

[1] Paul Sharkey, “Ant Colony Optimization: Algorithms and Applications”, March 6, 2014, available online at: http://www.lancaster.ac.uk/pg/sharkeyp/Topic1.pdf

[2] Maniezzo, Vittorio, and Antonella Carbonaro, "Ant colony optimization: an overview", In Essays and surveys in metaheuristics, pp. 469-492, Springer, Boston, MA, 2002.

[3] Parsons, Simon, "Ant Colony Optimization by Marco Dorigo and Thomas Stützle, MIT Press, 305, The Knowledge Engineering Review 20, no. 1 (2005): 92.