Using Ants to do Math

Have you ever seen ants? Of course you have. Of course you are not from Antarctica. But if you are from Antarctica then for your information Ants are a type of small insect which you can find almost anywhere in every continent (except Antarctica). 

Ants belong to an order of insects called Hymenoptera and the insect family Formicidae means ‘ant family’.

Now where do these little guys live? The answer is everywhere. In the first place, ants are not like bees and wasps, which build their nests out of wax or carton and form polygonal cells whose structure is instinctively fixed for each species by heredity. Ant-nests, on the contrary, are nearly all irregular, variable and adaptable to circumstances. This is probably one of the reasons ants are one of the most adaptive species.

The field of ‘‘ant algorithms’’ models derived from observing these little guys and using these models as a source of inspiration for the design of novel algorithms for the solution of optimization and distributed control problems. One of the most successful examples of ant algorithms is known as ‘‘ant colony optimization,’’ or ACO. ACO is inspired by the foraging behaviour of ant colonies, and targets discrete optimization problems.

Now the idea is to use highly coordinated behaviour of real ants to solve computational problems. Several different aspects of the behaviour of ant colonies have inspired different kinds of ant algorithms. Examples are foraging, division of labour, brood sorting, and cooperative transport. 

Deneubourg and colleagues (Deneubourg et al., 1990; Goss et al., 1989) proposed a simple model that describes the dynamics of the ant colony as observed in the double bridge experiment. The double bridge experiments show clearly that ant colonies have a built-in optimization capability: by the use of probabilistic rules based on local information they can find the shortest path between two points in their environment. Interestingly, by taking inspiration from the double bridge experiments, it is possible to design artificial ants that, by moving on a graph modelling the double bridge, find the shortest path between the two nodes corresponding to the nest and to the food source. 

But the following problem arises: the artificial ants, while building a solution, may generate loops. As a consequence of the forward pheromone trail updating mechanism, loops tend to become more and more attractive and ants can get trapped in them. But even if an ant can escape such loops, the overall pheromone trail distribution becomes such that short paths are no longer favoured and the mechanism that in the simpler double bridge situation made the ant choose the shortest path with higher probability does not work anymore. 

We therefore need to extend the capabilities of the artificial ants in a way that, while retaining the most important characteristics of real ants, allows them to solve minimum cost path problems on generic models. In particular, artificial ants are given a limited form of memory in which they can store the partial paths they have followed so far, as well as the cost of the links they have traversed. Via the use of memory, the ants can implement a number of useful behaviours that allow them to efficiently build solutions to the minimum cost path problem. These behaviours are -

1. probabilistic solution construction biased by pheromone trails, without forward pheromone updating. 

2. deterministic backward path with loop elimination and with pheromone updating.

3. evaluation of the quality of the solutions generated and use of the solution quality in determining the quantity of pheromone to deposit.

We can also use this specific algorithm  to solve Routing problem, Subset problem etc. It can be used in Quantum Physics, Photonics, Fluid Mechanics and even to build the folding structure of protein.

Source: Ant Colony Optimization - Marco Dorigo and Thomas Stützle, 

The Social World of Ants ( Vol. 1) - Auguste Forel

RAKTIM KARAN(STUDENT)
SEM: II
DATE: 20/07/26