Saturday, July 21, 2012

37. Ant Logic

Ants are the history of social organization and the future of computers (Kevin Kelly 1994).
Ants are social insects. And they occur in huge numbers. There are more than a million ants for every human. An ant is a small dumb creature, not able to see far. Considering its size, the landscape in which it moves around must appear very rugged to it. Then how is it that ants in an ant colony are able to find food rather rapidly and generally by the shortest route, in spite of the fact that there is no one in command of operations?

It is a case of swarm intelligence. In such a swarm, each individual has little or no intelligence, and it only follows some simple 'local rules', and yet the swarm as a whole ends up possessing intelligence.

It is instructive to understand the basic processes involved in an ant colony, the more so because ANT LOGIC has already found several applications in the field of 'artificial evolution' and in computational science. Dorigo and coworkers did some pioneering work in this area.

Ants in a colony have a distinctive communication mechanism, involving pheromones. Pheromones are chemicals that play the role of signals among members of the same species.

An ant colony is a remarkable parallel-processing superorganism. The ants function independently and simultaneously, and communicate with one another unknowingly via pheromones.

A number of scout ants set out in search of food, going in different directions independently and randomly. They emit the pheromone all the time, both while going away from the nest and while returning to it. It follows that a trail used by many ants will have a strong pheromone odour. The pheromone evaporates slowly, i.e. its strength on a trail is a decaying function of time.

Suppose one of the many scout ants has accidentally discovered the shortest usable path to food. Let us call it trail A (Part 3 in the figure below).

Then it will be able to travel to the food, and come back by the same path (guided by the pheromone trail), in the shortest time, compared to other ants which did not happen to take this route. The to and fro journey along trail A will result in twice as much pheromone along it, compared to a trail which is twice as long. Different ants traverse different trails, and the trails may intersect. At trail-crossings the ants divert to the trail with the strongest odour, thus further strengthening its odour (LAW OF INCREASING RETURNS, OR POSITIVE FEEDBACK). Ultimately, all ants follow the shortest route to food, in spite of the fact that no design work, or planning, or supervision, has gone into this. Swarm intelligence indeed.

Investigation of one type of complex system can provide insights into what may be happening in other complex systems. An obvious case in point is: How to understand human intelligence as a kind of swarm intelligence. Human intelligence emerges from the interactions among neurons, in spite of the fact that any particular neuron is as dumb as can be.

Ant logic has been applied, among other things, to the so-called travelling salesman problem (TSP). Suppose a salesman wants to visit every city in his route exactly once and then return home. The TSP is to determine the route for which the distance travelled (or the cost) is the least, and involves enumerating the possible distinct itineraries. Suppose the salesman has to visit, say, five cities and then return home. There are five ways of choosing the first destination city. For each of these, there are four different ways of choosing the second city. Having chosen any of these, there are only three ways of picking up the next city (because the salesman cannot touch any city twice). And so on. Thus the total number of possible itineraries is 5 x 4 x 3 x 2 = 120, or 'factorial 5' (denoted by '5!'). For each of these 120 options, one computes the total distance to be covered. The option with the least distance is the best.

This is a brute-force way of solving the TSP. But suppose the number of cities to be visited is 50, rather than 5, not an unrealistic number in modern days of air travel. The search space now comprises of '50!' possibilities; i.e., ~1064 (10 followed by 64 zeroes). This is a very large number indeed, and the girl doing the booking at an airline would have a very tough time trying to offer a good itinerary.

Algorithms for reducing the size of this search space must be found. At present it is not known whether a so-called 'good algorithm' actually exists which always gives a minimal solution. In fact, it is a so-called NP-complete problem.

When ant logic was applied for solving the TSP, surprisingly good results were obtained. Virtual ants ('vants') were created on a computer. Vants were dumb processors in a giant community of processors, operating in parallel. They had a meagre memory, and could communicate only locally, pheromone-like. Each vant would set out rambling from 'city' to 'city', leaving a trail of a time-decaying mathematical function, rather like the pheromone. The shorter the path between cities, the less the mathematical pheromone decayed with time. And the stronger the pheromone signal, the more the other vants followed that route (self-reinforcement of paths). Around 5000 runs enabled the vant group-mind to evolve a fairly optimal global itinerary.

Click HERE for some interesting information on human societies vs. ant colonies.

An ant colony is an example of a 'complex adaptive system' (CAS). More on that next time.