Applied Mathematics Seminar

Ants exhibit collective decision making with an apparent absence of centralised control. One example of this is the laying of pheromone trails, which allow communication between individuals. When ants find a couple of food sources, the colony will ``choose'' the ``best'' source to feed at. One interpretation of the ``best'' food source is the closest.

The Travelling Salesperson Problem (TSP) is to find the shortest path through a collection of destinations, such that each destination is visited exactly once.

The connection between ants ``choosing'' the shortest path and solving the TSP was made about 10 years ago. Since then many algorithms have been written and tested on various TSPs. Some of these are very good at finding the shortest path, however as yet no one knows exactly why they work.

This talk consists of three sections. The first examines a system which models ants foraging, and concludes with a description of some of the phenomena of the trail networks of foraging ants. This model is then reinterpreted to discuss how ants ``choose'' the closest food source. Finally a reinterpretation is examined which attemps to gain an insight into how ants solve the TSP.