Digital Signal Processing Reference
In-Depth Information
Algorithm 8.3
: Rank Selection Method
•
Choose a mapping of the fitness values into the probabilities of selec-
tion that is appropriate from the standpoint of some objective (e.g.,
to maintain population diversity).
•
Apply the mapping to the fitness values of the individuals that will
take part in the selection process.
•
Run a random generator using the mapped probability values and
select the individual associated with the obtained index.
The last selection procedure to be considered here is tournament selec-
tion [82]. As the name indicates, this method creates a series of competitions,
based on fitness, between groups of individuals of the population, and uses
the outcome of these tournaments to define those that are selected. A key
aspect is that the procedure allows control over the selective pressure. This
can be understood if we consider, for instance, a competition with
q
individ-
uals of a population with, for instance, 10 solutions. If
q
10, the selection
mechanism will be deterministic, since the individual with the highest fit-
ness value will always be chosen. On the other hand, if
q
=
1, the fitness
will have no impact on the choice of an individual, since the choice of the
participants is based on a uniform distribution. Finally, 1
=
10, we will
reach a controllable intermediate level of selective pressure. This elegant con-
trol mechanism is responsible for the wide applicability of this method. The
pseudo-code in Algorithm 8.4 gives an idea of the method, when applied to
the selection of a single individual.
<
q
<
Algorithm 8.4
: Tournament Selection Method
•
Define the number of tournaments and the number of individuals
taking part in a tournament.
•
Start the tournaments. Use a uniform random generator to define
which individuals will be chosen to take part and keep a table of the
winners, directly defined by the fitness measure.
•
Choose the individual with the largest number of wins.
Different criteria can be used to deal with draws and with the selection of
multiple individuals, but this is not part of the structure of the tournament
itself. It is also important to point out that alternative tournament schemes
can be defined [23].
8.2.5 Crossover and Mutation Operators
There are many ways to perform crossover, but their essence is fundamen-
tally the same: a pair of chromosomes is combined in accordance with a
