In the discipline of Operations Research, the Ant Colony Optimization algorithm (ACO) is a technique to solve complex combinatorial problems inspired by the behaviour shown by ants in nature, swarm intelligence. This algorithm was first proposed by Marco Dorigo in 1992.
A colony of ants is able to find the shortest route from their anthill to a food source thanks to the pheromones they give off. When an ant finds food, it returns to its anthill while secreting pheromones which are very attractive to the other ants. These pheromones work as a trail of signals that the rest of the swarm will tend to follow.
Because of the large size of their colonies, it is common for several ants to find different routes of different distances between the anthill and the food. Here the volatility of pheromones comes into play, whose intensity decreases over time, so that longer routes, which require more time to be travelled, have a less intense trail than short ones, are less attractive and are less frequently travelled. Therefore, the pheromone trail of the shortest routes is reinforced.
This technique is applied to find alternative solutions to classic problems such as Travelling Salesman and has the advantage of dynamically adapting to changes in the conditions of the problem. ACO is used in real routing problems by for example delivery and courier companies.
This heuristic efficiently combines two elements of information: on the one hand, the distance between points along the different paths (the closer the next point, the more likely it is to go to it); on the other, the pheromone, that is, the information of previously explored solutions. Thus, at a point A, the closest ones are more attractive, but in previous solutions, going from A to each point has resulted in better or worse solutions. This algorithm combines the two sources of information in a balanced way.
Game
We have created a small demo game to show the ACO algorithm in operation.
– Draw 10 dots on the canvas. To make the game more interesting, we will draw another 10 dots randomly.
If you click on the dice icon, we will take care of drawing the missing dots until we reach 20.
– Draw the shortest path across all the dots, only once for each one and that ends at the starting point. You only need to single-click on each dot. To keep it simple, it is not possible to undo strokes, so be careful not to make mistakes.
– When you are finished, the ACO algorithm will solve the problem for a maximum of 20 seconds and show you its best solution.
– The solution with the shortest distance wins.
Good luck!
Note: for the sake of simplicity, this game is designed for large screens: enjoy it on your PC or Mac.
To know more about real-world applications of operations research, visit our solutions and contact us.
