Learning from the humble ant

The next time you're outdoors and you see a trail of marching ants, try a little experiment. Place an obstruction asymmetrically in their path, which is steep enough that they can't climb over it, and see what happens. At first, they would spread out equally in both directions to rejoin the trail. Over a period of time, you'll see the longer trail thin out and disappear as all the ants start taking the shorter trail.

What's really remarkable about this is that ants cannot see and cannot talk. That is to say, they lack the sensory organs for sight and sound. So how do they do this job of finding a short route around obstacles to their target food source?

The secret, as with many other things observed in nature, is elegant in its simplicity and inventiveness. Ants have a very good sense of smell, and lay out a class of chemicals called Pheromones to mark their trail. Each ant lays out roughly the same amount of pheromone for a particular food source, and the pheromone evaporates at a constant rate. When an ant moves towards a marked food source, it tends to move in a direction in which it senses a relatively higher concentration of pheromone.

That's all. If you're puzzled as to why I cut the explanation short, take a minute to think about how this would work and then read on. Now, when the obstacle is placed in the path, the ants can no longer sense the correct direction to travel, and they choose at random among the available directions. Ultimately, they would rejoin the trail, but each ant has now laid pheromone along the path it has taken. Initially, there is little to choose from between the two options, but over a period of time, the shorter path, simply by virtue of being shorter, would have a greater number of ants traversing the path back and forth. This means that the evaporating pheromone on the shorter route gets regenerated more often than on the longer route, causing more ants to choose that direction over the other. This further increases the disparity in pheromone level between the two choices, until there is insufficient pheromone on the longer trail to tempt even a single ant to go in that direction.

This kind of a process is called Auto-Catalytic, meaning it speeds itself up. Some time around 1990, an Italian scientist called Marco Dorigo got a brainwave on how to use this ant behaviour to solve combinatorial optimization problems, which are notoriously difficult to solve with conventional mathematical techniques.

What he did was to represent an optimization problem as a set of obstacles in the path of an ant trail. The decision of which direction to take at an obstacle represented the decision of what value to assign to a variable. In other words, if a variable can take four different values, it is like placing an obstacle giving an ant four different paths around it. Each variable in the problem is equivalent to an obstacle on the trail. "Pheromone concentrations" are maintained virtually for each decision at each obstacle.

The generation of a solution is done randomly, with the probability of taking a particular decision being proportional to the virtual pheromone concentration. Then, the "goodness" of the solution is quantified by the objective function, and this is analogous to the distance traveled to reach the food source by that route. If it is a poor solution, it is a long route and the pheromone concentrations along that route are increased by a small value. If it is a good solution, the pheromone concentrations are increased by a higher value; and all the time, pheromone is "evaporated" at a constant rate at every decision point.

It worked. In a way similar to how ants find paths, an algorithm known as Ant Colony Optimization (ACO) was developed and refined, and although it does not always find the globally best solution, it tends to find a good solution for even large problems in reasonably quick time.

In spite of all the nature-defying technological marvels scientists and engineers come up with, there seems to be an infinite depth to the workings of nature from which we learn continually. The ant optimization algorithm is but one in a wide class of algorithms under the banner of Swarm Intelligence, for ants, bees, birds and many other social denizens of nature have unique and innovative ways of doing a plethora of tasks. Computer scientists observe, and come up with smarter algorithms. Engineers observe, and come up with better control system schemes.

How wrong we are, in talking about "humble ants". It's we who are the "humble scientists".

Links for further reading:
Marco Dorigo's page on the behaviour of real ants that inspired ACO
Wikipedia
Marco Dorigo's landmark paper on Ant Systems