Ants are amazing animals. Drop something tasty on the floor and they will quickly build an efficient highway from their nest and back to take the morsels home. They can do this despite very poor, in some species non-existent, eye-sight, no voice to talk to each other, and a less than impressive individual IQ.

Ants are very good at forming highways.

So striking is this ability that in the 1990s computer scientists began to wonder whether they could mimic the ants' behaviour in computer programmes designed to solve complex problems.

Today, ant colony optimisation algorithms (ACOs) are widely used to solve problems in which many components need to be combined in some optimal way: whether it's deciding delivery routes of a fleet of trucks or the timetables of doctors in a hospital.

How do ants do it?

Ants communicate using chemical substances called pheromones. "As ants move around they can leave pheromone on the ground," explains Marco Dorigo of the Université Libre de Bruxelles, who came up with the idea of ACOs in his PhD thesis and has co-authored a seminal book on the topic. "And if they sense [a trail of] pheromone already on the ground, they have a higher probability of following that trail rather than going in a different direction." If sufficiently many ants favour a particular trail a feedback loop ensues: the pheromones they have deposited will attract more ants to the trail, who increase the pheromone concentration along it, which will in turn attract more ants.

Intriguingly, biologists have shown that this mechanism alone can enable ants to collectively find a short route between a food source and their nest. In 1990 Jean-Louis Deneubourg and colleagues offered a colony of ants two routes connecting their nest to an area they had not explored yet and where they could find food. In one experiment one of the routes was twice as long as the other and it turned out that, in most of the trials, all the ants eventually chose the shorter path.

This choice could of course be down to some sort of inbuilt ability of ants to measure distance. If this were the case, then you wouldn't expect the ants to prefer one route over the other if both routes are equally long. But in experiments where both paths did have the same length ants also ended up preferring one route over the other.

"Biologists have shown that you can explain this behaviour in terms of pheromones alone," says Dorigo. Initially the ants will make a random choice as to which of the two paths to take, but once one route has more pheromones than the other, they will prefer that one. When one route is twice as long as the other, then the shorter one will rapidly collect more pheromones: ants travelling down the short route will be the first to reach the food source and to start their trip back home, retracing their steps. In this way the shorter route collects pheromone more quickly and the positive feedback loop kicks in.

When both trails have the same length, ants will randomly choose which to take with a 50:50 chance. But just as flipping a fair coin a few times won't give you exactly 50% heads and 50% tails, random fluctuation will cause one of the two paths to pick up more pheromone, so the feedback loop kicks in again.

Marco Dorigo

Deneubourg and his colleagues produced a mathematical model describing the pheromone mechanism. In the model the probability of an ant choosing one of the paths depends on the amount of pheromone already on it. Running the model on a computer, scientists found exactly the behaviour displayed by real ants. (You can see the model in detail in this excerpt of Dorigo's book.)

All of this is an example of something called stigmergy: individuals, in this case ants, make marks on their environment which then guide the actions of other individuals. A feedback loop results which then leads to the emergence of behaviour that appears coordinated and systematic — in this case, choosing a quick route.

Why do humans do it?

"In Deneubourg's experiment the ants are solving an optimisation problem," says Dorigo. "It's a simple optimisation problem for us humans, because when humans look at a [choice between two paths] they immediately know which one is shorter. But there are many [other] problems in the real world that can be modelled as so-called combinatorial optimisation problems."

One example is the routing of vehicles. You have a fleet of trucks and goods kept at a number of depots that need to be delivered to a number of customers at given locations. What set of routes should the trucks take in order to minimise the cost of transportation, while sticking to some additional constraints, for example that all trucks need to be back home in the evening?

"When you have few trucks then maybe you can find the optimal solution, but as the number of trucks increase the problem becomes too difficult even for the most powerful computers. The time it would take any known computer algorithm to find the solution soon exceeds the age of the Universe." explains Dorigo. (In fact, the vehicle routing problem is what complexity theorists call NP hard — you can find out more here.) Many other problems involving time tabling or scheduling are equally difficult.

What these kinds of problems have in common, apart from their difficulty, is that they can all be represented on a network. In the case of the trucks, the network is simply the road network that connects all the places the trucks must go to. For other problems setting up the network representation takes a little more work, but once constructed, provides a clear and succinct description of the problem. (See these slides for an example of a network for a scheduling problem.)

How do computers do it?

Hello cutie! An extreme close-up of an ant by Retro Lenses, CC BY 4.0.

The idea behind ant colony optimisation is to create algorithms that mimic the behaviour of ants to find optimal, or nearly optimal, solutions to such problems. Given a real-world problem, you start by translating it into an optimisation problem on a network. Networks are easily represented in a computer, and so are artificial ants, properly called agents, moving around on them. The place of pheromone is taken by "artificial pheromones", that is, numbers associated to links in the network: the higher the number, the more pheromone there is associate to the link.

The system is started off with the same small amount of artificial pheromone on all links and the agents making random choices as to which link they travel along. When an agent has found a solution, for example a path from the starting node to the end node, it will evaluate the quality of the solution. It'll then add an amount of artificial pheromone to the links that are contained in the solution that's proportionate to the quality of the solution. The amount of artificial pheromone associated to a link biases the choice of an artificial agent sitting on a node attached to that link: the more pheromone, the higher the chance the agent chooses to travel down that link.

"If I am an artificial agent sitting on a node, in the beginning the choices I have are all the same, so I make a random choice," explains Dorigo. "After a while some of the edges will have more pheromone because they have been used more or because they belong to solutions that are better than others. Then I have slightly higher probability to choose those edges. This goes on all the time, with many agents in parallel, and at some point the system finds a good solution."

Using this idea Dorigo, Gianni Di Caro and Luca Gambardella have developed, not just one algorithm to solve a particular problem, but a whole framework that can be tailored to whatever combinatorial optimisation problem you would like to solve.

How well do computers do it?

Pretty well, in practice. Ant colony optimisation is up there with the state-of-the-at algorithms that are being used to solve difficult real-life combinatorial optimisation problems. Ideally, computer scientists like Dorigo would like to prove mathematically that the algorithms perform well, for example by showing that the time it takes for such an algorithm to find a good solution to a problem (for example scheduling trucks) doesn't grow to quickly with the size of the problem (eg the number of trucks).

Ants are more powerful than you might think...though they need to act collectively to achieve that power.

But so far, the theoretical pickings are thin. All that theorists have been able to show in general is that, given an infinite amount of time, the ant colony optimisation algorithms will find an optimal solution to the problems they have been designed to solve.

"This looks like a particularly useless result," admits Dorigo. An infinite amount of time is exactly what people trying to solve real-world optimisation problems don't have. But there is a point to the result: in theory it could be possible for the algorithm to never, ever find an optimal solution. At least that possibility has been ruled out. For some particular algorithms within the class of ant colony optimisation there are theoretical results about how fast they find an optimal solution, but these are exactly the ones that are performing badly in practice. "This doesn't apply just to ant colony optimisation, but to most algorithmic frameworks designed to solve combinatorial optimisation problems." says Dorigo.

There are also still interesting challenges concerning the practical side of ACOs. At the moment, if you want to use the framework, you will have to figure out for yourself which of the family of ACO algorithms is best suited for your problem. "One very promising research direction is to make this process automatic," says Dorigo. This means constructing an algorithm which, given a specific problem, finds the best ACO algorithm for you to use.

Thus, those little creatures, which we don't always view with sympathy, have not only inspired ways of solving complicated problems, but also posed challenging problems to exercise the minds of a new generation of researchers. Think about that next time you're about to brush an ant off your picnic blanket!

About this article

You can also listen to the podcast accompanying this article!

Marco Dorigo is a researcher director of the F.R.S.-FNRS, the Belgian National Funds for Scientific Research and co-director of IRIDIA, the artificial intelligence laboratory of the Université Libre de Bruxelles, Belgium. He is a Fellow of AAAI, EurAI and IEEE. He was awarded the Italian Prize for Artificial Intelligence in 1996, the Marie Curie Excellence Award in 2003, the F.R.S.-FNRS Quinquennal award in applied sciences in 2005, the Cajastur International Prize for Soft Computing in 2007, an ERC Advanced Grant in 2010, and the IEEE Frank Rosenblatt Award in 2015.

Marianne Freiberger is Editor of Plus. She interviewed Dorigo in June 2019.