Ant Colony Optimisation – An Explanation

In this blog, I will be explaining how the technique Ant Colony Optimisation works and where this can and has been applied.

What is Ant Colony Optimisation?

Ant Colony Optimisation (ACO) is a method that attempts to simulate how ants behave when deciding on the optimal path. This method is typically used on networking solutions, using graph theory, to get from point A to point B.

Swarm of Ants
Swarm of Ants [Source: https://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms]

By looking at the example below, you can see how the ant can get from the source to the destination. But you may wonder, how does this work?

ACO Example [Source: https://wirelezz.wordpress.com/2010/10/]

How does this work?

Well, to start off with, we have to know what the ants do when they try to choose their path. When ants move from one node to another, they leave pheromones behind; these pheromones attract the other ants to go the same way. This means that if a path has more pheromones than another path, then the ants will be more likely to go down the path that has more pheromones. By doing this, if the ants start to discover a shorter path, more ants would go down that path and exploit it.

But how does this relate to a computational problem?

First off, we have to explore the search space so the swarm knows the length of the edges in the network. Using this information that is gathered, the swarm can start using it to decide where to go based on the heuristic and knowledge it now has. The only thing that we haven’t mentioned in this implementation is the pheromones. This would also be an aspect for the agents to decide where to go. For the pheromones to be placed in the first place, the agents could place the pheromones along a path if the agent managed to get to the destination. This would further incentivise the agent to follow the paths that can get to the destination. At this stage, the agents move from exploration to exploitation.

If you cannot get your head around this but are familiar with other pathfinding techniques, just think of this as A* pathfinding but with pheromones influencing the agents.

Applications

ACO is used in many network solutions because of how it encompasses exploration and exploitation over a gradual time. Here are a small number of fields that this techniques is used in:

  • Scheduling. E.g. Timetabling
  • Routing. E.g. Travelling Salesman Problem
  • Image Processing

References

Share this post:
RSS
Follow by Email
Facebook
Google+
http://mattrclark.com/2016/12/ant-colony-optimisation-an-explanation/
YouTube31
YouTube
LinkedIn

Leave a Reply

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