Ant Colony Optimization


Algorithms in Real Life

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…

View original post 357 more words

Comments
2 Responses to “Ant Colony Optimization”
  1. I believe that using this approach, the algo might choose the long path and stick to it/stagnate. A possible modification is

    When ant is presented at a choice:
    if no paths previously taken
    choose path with probability 1/n # n-> number of choices
    else if some paths previously taken
    choose one of the paths not taken yet with probability 1/(n-x) # x -> number pf paths previously taken
    else if all paths previously taken
    choose path with highest phermone

    At end of journey,
    traceback path decaying phermone by a factor of journey length

    This gives us a way to have convergent shortest routes.

    • eswarann says:

      Eeshan, you are right. In the algorithm implementation it is common practice to introduce some statistical variation in choice thereby reducing the chances of stagnation.

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

%d bloggers like this: