Robotics Reference
In-Depth Information
population corresponds to a satisfactory solution to the original prob-
lem.
Most organisms evolve by means of the processes of natural selection
and reproduction. Natural selection determines which members of the
population survive and reproduce, while reproduction mixes and recom-
bines the genes of the parents in their offspring. The process of natural
selection is simple. Each offspring of a reproductive process is subjected
to one or more tests of fitness. For example, in the case of a bird, one
test of fitness is recognizing that cats are predators and evading them.
If a bird fails such a test then it is likely to be attacked and seriously
injured or killed. During human reproduction, when a sperm and an
ovum meet, pairs of matching chromosomes line up together and then
cross over partway along their lengths, thereby swapping some of the ge-
netic material of each. This mixing process propagates evolution much
faster than if the genes of each offspring were merely those of a single
parent.
In the early 1960s Hans Bremermann, at the University of California
at Berkeley, developed the idea of using computer programs to simulate
biological reproduction, carrying over some of the characteristics of par-
ents into their offspring by reference to the genes of both parents. Bre-
mermann's simulated mating procedure was limited in its scope, but his
idea was soon augmented by the work of John Holland, who had become
convinced that the recombination of groups of genes during the mating
process was a critical part of evolution. By the mid-1960s Holland had
developed the idea of what he called “genetic algorithms” that evolved by
combining the benefits of mating and gene mutation.
At the start of the genetic algorithm process there is a population
of “genomes”, each of which represents a possible solution to the original
problem. This starting population might be created randomly or it might
be based on heuristic rules derived from the program's own knowledge of
the problem domain. Genetic algorithms work iteratively, that is to say
the evolution process is carried out hundreds or thousands or millions of
times, depending on the complexity of the problem, until the software
cannot improve the algorithm any further. Each iteration corresponds to
a generation in human evolution and when each new generation is cre-
ated, each member of its population is tested for its fitness according to
some pre-defined criteria, using a fitness-function, akin to the evaluation
functions employed in game playing programs. Each member of the new
population is thus assigned a fitness score.
