Ant Colony Optimization


Algorithms in Real Life

A popular nature inspired heuristics is from the ant. The ant foraging behaviour has been studied for long. One of the earliest studies carried out was in 1959 – Pierre-Paul Grassé invented the theory of stigmergy to explain the behavior of nest building in termites. More serious work began in 1983.

Ant foraging behaviour and pheromones

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 his PhD thesis in 1992. 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.

Plain-PathWhich road will the…

View original post 499 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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: