Robotics Reference
In-Depth Information
Many different techniques are employed for deciding which mem-
bers of the population in a new generation should be selected as the
basis for creating the next generation.
27
One of the most effective is
Holland's original method, which he called “fitness-proportionate selec-
tion”, a method that avoids the “hill-climbing” problem described in
footnote 27. With Holland's method, the probability of selecting a par-
ticular member of a population as a parent is proportional to its fitness.
This means that the fittest will indeed be more likely to be selected than
the less fit, but statistically some of the less fit (and some of the least
fit) will also be selected. The rationale is that a lesser member of a par-
ticular generation just might turn out to be on the right track for the
global summit—the best of all possible solutions within the “hilly” area
of candidate solutions.
Once the selection has been made to determine which of the mem-
bers of the current generation are allowed to reproduce and which are
to be removed from the population, new members of the population
are created by two processes, both derived from genetics, called
crossover
and
mutation
. The crossover process in a genetic algorithm mimics the
way that biological chromosomes cross over one another when two ga-
metes
28
meet to form a zygote.
29
When two genomes in a genetic algo-
rithm line up, a point along the genomes is selected at random (called
the crossover point) and the portions of both genomes to one side of
that point are swapped around, thereby producing two offspring. One
of these offspring contains the data from one of the genomes up to the
crossover point and the data of the second genome beyond that point,
and the other offspring vice versa. These two offspring are then used to
replace two less fit genomes that have been weeded out by the fitness-
proportional selection process (or whatever method of selection is used
instead). So each creation of two new genomes corresponds to the dis-
carding of two from the previous generation, ensuring that the total pop-
ulation size remains constant.
27
Superficially it might appear as though the evolutionary process should automatically select all
of the fittest members of one generation as the gene pool for the next. To understand why the
process is not that simple, consider the problem of being placed somewhere in a hilly area and told
to climb to the summit of the highest hill in the area. Intuitively one might simply climb higher
and higher at every opportunity, but that approach can lead to the top of what turns out to be only
a local summit, from where it would be necessary to go downhill before going up again to a higher
summit.
28
A gamete is a mature sexual reproductive cell having a single set of unpaired chromosomes.
29
A zygote is a cell resulting from the union of an ovum and a spermatozoon (two gametes).
