Despite the fact that an ant has only a tiny brain, ant colonies manage to solve quite complex problems. Can we learn anything from them?
by Nigel Cummings
Insects that live in colonies, such as ants, bees and termites, have fascinated man for centuries. What is it that governs them? How can such primitive creatures achieve the relatively complex task of building self supporting communities? I am not writing this to expatiate upon the wonders of the insect world. I am writing this to comment upon OR practices which may be derived from insect behavioural patterns.
The means by which these social insects go about their day-to-day business has, after observation, led to analytical methods which can be applied to the classic travelling salesman problem. Swarm intelligence observed in ants is largely based on co-operation at the colony level where co-ordination takes place among individuals. Such interactions appear simple, little more than one insect following the trail left by another, though collectively they can solve difficult problems finding the shortest route to a food supply being a prime example. This co-operative tendency, observed particularly in ants, may some day lead to more effective algorithms for use in robotics. The way in which social insects sort out and segregate their dead, and their larvae, can also be applied to analyse certain types of banking data.
Going back to the travelling salesman problem for a moment, the problem of finding the shortest route which visits each of a given set of cities each exactly once, is known to be difficult to solve. With only 15 cities this problem poses billions of route possibilities. The problem is a good one to use for test purposes because of the relative ease of its formulation, but extreme difficulty of its solution. It is also a completely non-deterministic polynomial, as the solution requires a number of computational steps that grow faster than the number of cities raised to any finite power. This problem is usually solved with an emphasis on finding an answer that is nearly right, but not necessarily representing the very shortest routes possible.
Recently Marco Dorigo and his team at the Free University of Brussels, experimenting with ant-like agents, have produced a good solution to the problem. To achieve this they used simulated ants in search of pheromone trails equivalent to the individual route to each city. Dorigo has shown that he can produce near optimal results by using simulated ants which have the capability of producing varying pheromone concentrations dependent on the distances travelled.
Imagine for a moment, the use of a hypothetical ant colony in which an ant, after completing a tour of all 15 of the cities in the problem, returns to the links it used and deposits a pheromone. The amount of the pheromone deposited in relation to the distance travelled, is inversely proportional to the overall length of the 15 city tour- the shorter the tour, the more pheromone each of the links receives. Consider also that in such a colony, millions of other ants could be independently and randomly hopping about from city to city producing similar pheromone trails.
Consider also, that after the ants have all completed their tours, examination of the links that belonged to the highest number of short tours, will reveal highest concentrations of the pheromone. The pheromone in question is volatile and tends to evaporate. The effect of this evaporation becomes most noticeable in long routes where pheromone distribution is most tenuous, as opposed to short routes where pheromone distribution is most concentrated.
If the hypothetical colony of ants is set loose again on the same city trek, the following will be observed the ants will be guided by the traces remaining of the earlier pheromone trails, but will predominantly follow those remaining trails which contain the highest concentration of pheromone. They will also be seen to favour (weighted equally) those trails which can be described as intercity locations.
Marco Dorigos methodology assumes that favoured links will lead to shorter routes. As the experiment is repeated, the simulated ants can be shown to continually obtain shorter tours between cities. Such experiments do generate certain inequalities though; an example has been noted whereby many routes might happen to use a link which is not part of a short tour. Such a popular link might place a bias on the search for several iterations until a better connection eventually replaces it.
According to Dorigos observations, this form of optimisation can be seen as a consequence of interplay between reinforcement and evaporation which ensures that only the better links survive. Another problem has been observed. If a short route contains a very long link that initially appears unattractive, that link will only be ranked above other competing links after the short route has been selected.
Dorigos system is flexible, but it should be noted whilst it can find the shorter routes, it can not necessarily find the shortest, but due to the fact that simulated ants are continually exploring different paths, the pheromone trails provide back ups thus if a link breaks down a number of alternative short routes can be selected.
Social insect behaviour has inspired a large amount of scientific research into routing problems, the calculation of credit risk in banking, and the sitting of tiny satellites in swarm formation to form a collective with greater power than conventional satellite communication systems. Indeed swarm intelligence is daily being shown to offer alternative ways of designing systems. Such intelligence utilises self sufficiency and autonomy which rely on direct or indirect actions amid simple individual agents.
Further information on Dorigos work can be found in: Swarm intelligence: from natural to artificial systems - Eric Bonabeau, Marco Dorigo, Guy Theraulaz. Oxford University Press.
First published to members of the Operational Research Society in Inside OR April 2000
