July 6 2000

Follow that ant to find the ultimate short cut


FORGET the road atlas. Travelling salesmen should take a leaf out of the ant's textbook for discovering the shortest route from A to B.

The phenomenon known as "swarm intelligence" could help to cut journey times between cities. Computer programs based on ant behaviour are already being used to route petrol tankers in Switzerland, and are being tested by companies including Unilever, BT, and MCI-Worldcom, scientists say. They work as well, if not better, than existing methods for solving the travelling salesman problem.

It works as follows. A foraging ant that finds food will lay trails of scent along its route as it returns to the colony. The scent, or pheromone, gradually evaporates, causing the trail to be lost unless it is continuously renewed.

However, because the ants that follow shorter routes make more trips than those on longer routes, the scent on the shorter routes remains stronger - indicating the best route for the other ants to follow. In practice, it does not always work perfectly for the ants. They can become "stuck" on an inefficient route if the pheromones do not evaporate quickly enough, and the route is used by enough ants to keep reinforcing the scent.

However, if the ant behaviour is modelled on a computer, this problem can be overcome by increasing pheromone decay. The technique, called Ant Colony Optimisation (ACO), can be used for solving a variety of problems, three scientists report in Nature. "We have no doubt that more practical applications of swarm intelligence will continue to emerge," Eric Bonabeau, of the Santa Fe Institute in New Mexico, and his colleagues Marco Dorigo and Guy Theraulez, say.

In real life, ants never have to solve the travelling salesman problem, but is is possible to imagine how an "artificial ant" might do so. The problem is that of devising the shortest route between a given number of cities, visiting each of them only once.

Imagine an ant visiting the cities, moving between them almost at random. After completing the tour, the ant goes back over the same route and lays an amount of pheromone determined by the length of its tour: the shorter the tour, the more pheromone is laid.

If many ants do this, the pheromone will be thickest along the links that belonged to the largest number of short tours. If the ants follow these, as well as giving priority to nearby cities, they will follow a short route - though not necessarily the shortest.

Next page: What foraging ants can teach travelling salesmen

Arts (Mon - Fri) | Books (Sat) (Thu) | British News | Business | Court page | Features (Mon - Fri) | Go (Sat) | Interface | Law (Tue) | Metro (Sat) | Obituaries | Opinion | Sport | Travel (Sat) (Thu) | Vision (Sat) | Weekend (Sat) | Weekend Money (Sat) | World News


Subscribe to

the paper


What foraging ants can teach travelling salesmen

Next: World Summary

Copyright 2000 Times Newspapers Ltd. This service is provided on Times Newspapers' standard terms and conditions. To inquire about a licence to reproduce material from The Times, visit the Syndication website. Up