What is ACO (Ant Colony Optimization) Algorithm

November 29, 2017 Author: virendra
Print Friendly, PDF & Email

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 Meta-heuristic takes inspiration from biology and proposes different versions of still more efficient algorithms.

Ant Colony Optimization (ACO): 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 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 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 behaviour 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 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 behaviour to counter problems of great complexity. A specific focus lies with the collective behaviour 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.

This shows the potential paths a colony

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 Pseudocode





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

init pheromone ​\( τ_{ij} \)

Repeat for all ants  construct solution

for all ants  global pheromone update

for all ants  evaporate pheromone;

                              \[ {τ_{i-j}≔(1-ρ) τ_{i-j}} \] 

 \[ Construct solution (i); \]

init ant;

while not yet a solution:

expand the solution by one edge probabilistically according to the pheromone;

\[ {τ_{ρi-j}/∑_{ρi-j}.τ_{ρi-j}} \]

              global pheromone update (i):

for all edges in the solution:

increase the pheromone according to the quality;

\[ {∆τ_{j-j}≔1/(length of the path stored)} \]

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.

One Comment

  • I truly wanted to develop a word so as to appreciate you for all of the amazing guidelines you are posting here. My time intensive internet lookup has at the end been recognized with sensible insight to exchange with my company. I would repeat that most of us readers are undoubtedly blessed to dwell in a perfect network with many special people with beneficial plans. I feel extremely fortunate to have encountered your entire webpages and look forward to tons of more fun times reading here. Thanks again for a lot of things.

Leave a Reply

Your email address will not be published. Required fields are marked *

Insert math as
Block
Inline
Additional settings
Formula color
Text color
#333333
Type math using LaTeX
Preview
\({}\)
Nothing to preview
Insert