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.

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., ~10

^{64 }(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.
An ant colony
is an example of a 'complex adaptive system' (CAS). More on that next time.

## No comments:

## Post a Comment