Distributed Optimization by Ant Colonies

Ants colonies exhibit very interesting behaviours: even if a single ant only has simple capabilities, the behaviour of a whole ant colony is highly structured. This is the result of coordinated interactions. But, as communication possibilities among ants are very limited, interactions must be based on very simple flows of information. In this paper we explore the implications that the study of ants behaviour can have on problem solving and optimization. We introduce a distributed problem solving environment and propose its use to search for a solution to the travelling salesman problem. The problem of interest is how almost blind animals manage to establish shortest route paths from their colony to feeding sources and back. In the case of ants, the media used to communicate among individuals information regarding paths and used to decide where to go consists of pheromone trails. A moving ant lays some pheromone (in varying quantities) on the ground, thus marking the path it followed by a trail of this substance. While an isolated ant moves essentially at random, an ant encountering a previously laid trail can detect it and decide with high probability to follow it, thus reinforcing the trail with its own pheromone. The collective behaviour that emerges is a form of autocatalytic behaviour — or allelomimesis — where the more are the ants following a trail, the more that trail becomes attractive for being followed. The process is thus characterized by a positive feedback loop, where the probability with which an ant chooses a path increases with the number of ants that chose the same path in the preceding steps. In Fig.1 we present an example of how allelomimesis can lead to the identification of the shortest path around an obstacle.