top of page
Search
Apr 19, 20213 min read

Ants and the Travelling Salesperson Problem

By Abi Wilkinson - Computer Science Student @ Queens' College, Cambridge

 

"Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?"


This problem - the travelling salesperson problem - is NP-Hard. This effectively means that an algorithm that could solve this problem exactly in polynomial time doesn't exist, i.e. any algorithm that could solve this problem exactly would take way too long for it to be useful.

To illustrate the problem, if we take this map of Europe and highlight all of the EU capitals (before the UK left the EU):

We can then find the shortest time to drive between each pair of cities using something like Google Maps. The aim then is to find the shortest route through all of the cities, visiting each city exactly once.


There are many ways to solve this using either exact algorithms or heuristic methods. An exact algorithm approach would be inefficient, but would guarantee that no shorter route exists, whereas a heuristic method is fast, but cannot guarantee to have found the optimum solution, i.e. shorter routes could exist.


Using an Ant Colony Optimisation (ACO) to achieve a decent solution for the TSP is a heuristic approach: we can't guarantee that the solution is optimal, but it will calculate a close solution far quicker than an exact algorithm.


An ACO models the behaviour observed in ant colonies to find the shortest paths between a series of food sources and their nest. Let's take a brief look into how an ant colony works:

Worker ants need to find the shortest routes between food sources to feed their nest. As they search for food, they leave pheromones behind them. Pheromones evaporate quickly, therefore shorter routes will have a higher concentration of pheromones. These worker ants are more likely to follow routes with a higher concentration, so the shortest route will eventually end up with the highest concentration of pheromones.


In order to model an ant colony, we could model our ants as objects that interact with an area surrounding a colony’s nest. The area around the nest, in this case, would be our map of Europe, with cities being food sources and the shortest routes between pairs of cities being the paths between them. The program would manage the ‘evaporation’ of pheromones on the paths and the distribution of ants. The ants would individually take a route through the map, starting with the first ant taking a random route. The following ants would gradually decrease the randomness in their path choices so that they take pheromone concentration and visibility down a path into account. At each timestep the amount of pheromones on the paths would decrease, leaving the shortest paths with the highest concentration of pheromones, and encouraging the ants to travel down them.


After many ants taking a journey through the map, the high concentration of pheromones on the shorter routes should leave us with a good solution for the TSP of our map. For our map of the EU, an ant colony optimisation found a route taking 11 days, 18 hours, and 22 minutes of continuous driving:

ACOs are not the only example of computer scientists taking concepts from other sciences to solve tricky problems. Computer scientists are currently collaborating with physicists and engineers to make quantum computers, with economists to make trading algorithms, and even neurologists and psychologists to create Brain-Computer Interfaces!


Further reading:

Comments

bottom of page