
Ant trails
Insects with no map that teach computers to find their way
✦ Confirmed
No ant knows a map. Yet the whole colony finds the shortest route to food. A young Italian turned this trick into a computer program.
Who: Jean-Louis Deneubourg, Marco Dorigo · When: 1989–1992 · Where: Brussels, Belgium and Milan, Italy
Nature and invention
Ants mark the way with scent, a pheromone. On the shorter path ants come back sooner, so the scent thickens and attracts more. The longer route slowly fades.
Ant algorithms, that is, programs in which virtual ants look for good routes for lorries, production plans and traffic in computer networks.
The tale
In the late 1980s, Jean-Louis Deneubourg's Belgian team set Argentine ants a task: two bridges, one short and one long, led from the nest to the food. At first the ants took both routes equally.
After a few minutes almost the whole colony had chosen the shorter bridge. Nobody was in charge. It was enough that the ants on the shorter route came back faster and marked it more often.
Marco Dorigo, a doctoral student at the Politecnico di Milano, decided this was a ready-made recipe for hard mathematical problems. In 1992, in his doctoral thesis, he described the first ant algorithm: virtual ants walk across a map of cities, leave a digital scent, and the scent evaporates.
Today ant algorithms are one family of optimisation methods. They are used for planning delivery routes, allocating tasks and research into routing in computer networks.
How it works
- Smell: Every ant returning with food marks the way. The next ants prefer the paths that smell stronger.
- Reinforcement: The short route is covered faster, so it gets more scent in the same time. A good route reinforces itself.
- Evaporation: In the program the scent slowly disappears. This keeps the virtual ants from getting stuck on the first, random route, so they keep looking for a better one.
Check for yourself
- Two routes to the sugar: In summer, put a drop of honey at two distances from an ant trail, with two sticks as bridges: a short one and a long one. After a quarter of an hour, count the ants on each bridge.
- Wipe out the trail: Rub a finger across an ant trail on a paving slab. Watch how the ants get lost at that spot and search for the scent.
- Ants on paper: Draw five cities on a sheet of paper and look for the shortest route through all of them. Count how many possible routes there are. With twenty cities there are more of them than grains of sand on a beach.
What is known for certain
The bridge experiments were described by Goss, Aron, Deneubourg and Pasteels in 1989. The ant algorithm was proposed by Marco Dorigo in 1992 and has since been a widely used method for approximately solving routing problems. It does not always give the best result, but usually a good one, and quickly.