Intelligence and nature
Nature has given rise to intelligent techniques to tackle several kinds of problems, such as adaptive behavior, the immune system and social coordination among insects.
Genetic algorithms (and evolutionary computation in general) take their inspiration from the Darwinian theory of the natural evolution of species. Its main principle is that the fittest individuals of a population have a longer life, therefore they have on average a higher number of children. Thus, the genes of the fittest individuals will spread among the population. Very simplistically, we can say that this mechanism allows for the generation of individuals best adapted to the environment they live in.
The fittest individuals are very likely to mate and their genetic code is recombined (crossover) and mutated before generating a new child. In this way, good characteristics are passed from one generation to the other and also a limited amount of diversity is allowed by means of random mutation.
A simple model of this mechanism can be simulated by computer programs which describe a kind of "learning and optimization" mechanism. Individuals represent possible solutions to the given problem. For instance, let's
consider the Traveling Salesman Problem:
given a set of cities, we want to find the shortest route that visits all the cities. A solution to this problem could be encoded by the sequence of numbers representing the cities. The shorter the
route, the greater the fitness of the corresponding individual. (For instance, we can take the inverse of the
route length as fitness measure)
John Holland was the first man to implement genetic algorithms in the 1970s. The algorithm was named Simple Genetic Algorithm. Over the years, many variants and improvements have been designed; among them, a particularly successful variant is Genetic Programming that deals with genetic codes represented by computer programs.
Evolutionary Computation is successfully applied in robotics, circuit design, industrial optimization problems, digital signal processing and financial forecasting.
"Who's leading? Who is giving orders, foresees the future, makes plans and keeps equilibrium?
The Belgian poet Maurice Maeterlinck describes with these lines the coordinated behavior of insects such as bees, wasps, termites and ants. Insects seem to behave in accordance
with a predefined overall plan in such a way that the whole system behaves as if it were centrally coordinated and programmed to achieve a predefined goal (e.g.
nest construction). The key concept of these systems is that coordinated
behavior emerges autonomously, without any intervention from centralized control. Swarm intelligence is the research area that uses biological models of social insects' behavior to design artificial intelligent systems. Problems in optimization, data analysis and extraction and robotics can be effectively tackled by means of such techniques.
Real and artificial ants
A notable example of swarm intelligence applications is that of ant algorithms; such algorithms are inspired by the foraging behavior of real ants.
Some ant species are able to find the shortest path between the nest and a food source. They achieve this behavior by using a kind of indirect communication, laying on the ground a chemical substance called pheromone that they can smell. While an ant walks, it deposits pheromone on the ground. Ants choose their direction by choosing higher probability paths with an intense pheromone trail. As time passes, some pheromone traces evaporate and others are possibly reinforced by ants traversing them. Now, positive feedback comes into play: the higher the number of ants on a path, the higher the pheromone quantity on it; therefore, more ants will choose this path. Hence, after a transient phase, almost all the ants will eventually follow the same path. Since pheromone evaporates, the longer paths will be discarded in favor of the shorter ones.
It is possible to design algorithms inspired by ants' foraging behavior to tackle optimization problems, such as the traveling salesman problem. These algorithms are called
You can see an ant algorithm in action by following this link: TSP Applet.