58
N.R. Harvey, S. MarshaNlSignal Processing: Image Communication 8 (1996) 55-71
current Gen~ation
r{
Next Generation
Fig. 1. Principle genetic algorithm components.
by copying each individual in the population, the
number of times being dependent upon an indi-
vidual’s observed performance. The number of
copies made is determined stochastically, so that the
expected number of copies made increases in pro-
portion to its observed performance. During phase
two genetic operators are applied to the interme-
diate population, interchanging and modifying sets
of alleles, to produce the new generation. Fig. 1
shows an overview of the components of a simple
GA.
3.1. Genetic operators
The metaphor underlying genetic algorithms is that
of evolution. In evolution, the problem each species
faces is one of searching for beneficial adaptations to
a complicated and changing environment. The knowl-
edge that each species has gained is embodied in the
makeup of the chromosomes of its members. Opera-
tions that alter this chromosomal makeup are applied
when parents reproduce, among them being mutation
and crossover.
When genetic operators are used with reproductive
plans, the result is a surprisingly sophisticated set of
adaptive plans. The two most commonly used genetic
operators are crossover and mutation.
3.1.1. Crossover
In biological systems, crossover is a process yield-
ing recombination of alleles via exchange of segments
between pairs of chromosomes.
Simple crossover proceeds in three steps.
(1)
(2)
(3)
Two structures (parents) are selected (often at
random) from the current population.
A crosspoint is selected (usually at random).
Two new structures are formed from the struc-
tures (parents), by exchanging the set of genes
to the right of the crosspoint on one parent with
those from the other parent.
Crossover is the key to genetic algorithms’ power.
Without crossover, for an individual to acquire two
beneficial and unlikely mutations, one of the unlikely
mutations would have to occur, by chance, to a parent,
and then the second unlikely mutation would have
to occur, by chance, to one of the parent’s offspring.
With crossover, beneficial mutations on two parents
can be combined immediately when they reproduce:
if the most successful parents reproduce more often
than less successful parents, and crossover occurs, the
probability becomes high that this will happen.
This feature of natural evolution - the ability of
a population of chromosomes to explore its search
space in parallel, and combine the best findings,
through crossover, is exploited with the use of ge-
netic algorithms. Fig. 2 shows the application of the
simple crossover operator to two binary chromo-
somes.
3.1.2. Mutation
Though mutation is one of the most familiar of
the genetic operators, its role in adaptation is fre-
quently misinterpreted. In genetics, mutation is a pro-
cess wherein one allele of a gene is randomly replaced
by (or modified to) another, to yield a new structure.
Generally, there is a small probability of mutation at
each gene in the structure. Formally, each structure in