Ant Colony Algorithms are typically use to solve minimum cost problems.

We may usually have N nodes and A undirected arcs

There are two working modes for the ants: either forwards or backwards.

Pheromones are only deposited in backward mode.

The Algorithm

The ants memory allows them to retrace the path it has followed while searching for the destination node

Before moving backward on their memorized path, they eliminate any loops from it. While moving backwards, the ants leave pheromones on the arcs they traversed.

The Algorithm

The ants evaluate the cost of the paths they have traversed.

The shorter paths will receive a greater deposit of pheromones. An evaporation rule will be tied with the pheromones, which will reduce the chance for poor quality solutions.

The Algorithm

At the beginning of the search process, a constant amount of pheromone is assigned to all arcs. When located at a node i an ant k uses the pheromone trail to compute the probability of choosing j as the next node:

where is the neighborhood of ant k when in node i.

The Algorithm

When the arc (i,j) is traversed , the pheromone value changes as follows:

By using this rule, the probability increases that forthcoming ants will use this arc.

The Algorithm

After each ant k has moved to the next node, the pheromones evaporate by the following equation to all the arcs:

where is a parameter. An iteration is a completer cycle involving ants’ movement, pheromone evaporation, and pheromone deposit.

Steps for Solving a Problem by ACO

Represent the problem in the form of sets of components and transitions, or by a set of weighted graphs, on which ants can build solutions

Define the meaning of the pheromone trails

Define the heuristic preference for the ant while constructing a solution

If possible implement a efficient local search algorithm for the problem to be solved.

Choose a specific ACO algorithm and apply to problem being solved

Pheromone “trail” additions/deletions, global updates and local updates

Large number of different ACO algorithms to exploit different problem characteristics

Sources

Dorigo, Marco and Stützle, Thomas. (2004) Ant Colony Optimization, Cambridge, MA: The MIT Press.

Dorigo, Marco, Gambardella, Luca M., Middendorf, Martin. (2002) “Guest Editorial,” IEEE Transactions on Evolutionary Computation, 6(4): 317-320.

Thompson, Jonathan, “Ant Colony Optimization.” http://www.orsoc.org.uk/region/regional/swords/swords.ppt, accessed April 24, 2005.

Camp, Charles V., Bichon, Barron, J. and Stovall, Scott P. (2005) “Design of Steel Frames Using Ant Colony Optimization,” Journal of Structural Engineeering, 131 (3):369-379.

Fjalldal, Johann Bragi, “An Introduction to Ant Colony Algorithms.” http://www.informatics.sussex.ac.uk/research/nlp/gazdar/teach/atc/1999/web/johannf/ants.html, accessed April 24, 2005.