//
you're reading...
Algorithms & Heuristics

Ant Colony Optimization

Many interesting meta-heuristics have been bio-inspired. Some of them are:

Ant Colony Optimization

This technique has been adapted from the studies carried out on the behavior of ants. It was observed that foraging ants quickly traversed the shortest path from the anthill to the food source and back. This was initially proposed by Marco Dorigo in 1992 PhD thesis. See here  to know more about his works.

Subsequently further studies on the ant behavior have led to this technique being adapted to address a wider range of problems. See here

The attempt here is to present the basics of the method in a simple manner.

Ant foraging behaviour

  Which road will the ant take? If the ant is facing the option for the first time and no other ant has visited this before then the path chosen will depend on the whim of the ant and both paths are equally possible. Hence the probability of a path being chose in ½ .

However if you imagine that this ant is not the first one and that some ants have already passed this point then the path chosen by this ant could be different. The path chosen will depend upon the number of ants that have passed before and more specifically the path chosen by those earlier ants. The reason is simple. Foraging ants do not want to get lost. Hence whenever they leave the nest and take a path they deposit a chemical called a pheromone and this chemical deposit helps them to return to the nest after they have foraged. This helps the foraging ants to return quickly and also help other ants to reach the food spot more efficiently.

  Which road will the ant now take? The path at the left of the ant is having a pheromone deposit laid by the previous ants. This ant will take that path where the intensity of the pheromone deposit is higher. This indicates more ants have followed this path and indirectly gives credit to the wisdom of those ants. Hence the probability of a path being chosen now changes and depends on the intensity of the pheromone deposit

So the probability that an ant will take a path when there is no pheromone trail is same as that for the other path. If there are two paths then the chances are 50-50. Shorter paths would have higher density of accumulation. Thus when the trail has a higher concentration of pheromone then the chance for taking the path is higher.

Ant Colony Optimization proposed by Dorigo and subsequently enhanced by many, have found uses in variety of the applications viz., travelling salesman, graph colouring, vehicle routing, network optimization, and job shop scheduling amongst many others.

Some challenges however have been faced using this meta-heuristic. Modifications have been suggested by many researchers to overcome these challenges. Different techniques, such having different strategies for different ants and acceleration methods of path search have been used to arrive at better performance.

Advertisements

Discussion

4 thoughts on “Ant Colony Optimization

  1. Simple and very good

    Posted by Mahadevan.p | February 21, 2012, 11:56 am
  2. Thanks. simple and interesting read. A quick question based on the high level understanding. What if the first ant takes the long route, so in this case rest follows it as there would be more pheromone deposit, resulting not necessarily be the shortest route.

    Posted by menon narayana umesh | February 22, 2012, 12:58 pm
    • In the case of the ant, that is possibly true.
      But in the case of systems, i am sure the enhancements to this model will allow the long/problem path to be overriden based on latest choice made.
      Meaning, if i choose a long path, there can be manual override to allow choose a different path – less problematic path – therefore allowing future choices to be influenced by this override.

      Posted by CK | July 13, 2012, 3:32 am

Trackbacks/Pingbacks

  1. Pingback: Cuckoo Search « A Ra News - March 10, 2012

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Enter your email address to follow this blog and receive notifications of new posts by email.

Join 66 other followers

%d bloggers like this: