Digital Signal Processing Reference
In-Depth Information
to the areas of the different regions of the wheel in the figure. Algorithm 8.2
describes the procedure.
Algorithm 8.2
: Roulette Wheel Selection Method
•
Feed the roulette wheel random number generator with the fitness
values of the individuals that will take part in the selection process.
•
Run the generator and select the individual associated with the
obtained index.
An implementation to select multiple individuals may include additional
mechanisms, like a lookup table that prevents multiple selections of the same
individual.
Theroulettewheelmethodcanbeconsideredefficientfromthestandpoint
ofspeedofconvergence, asithasthepotentialofstronglybiasingtheselection
processtowardindividualswithfitnessvaluesexpressivelyabovetheaverage.
However, it suffers from the threat of loss of population diversity. Under a
selection mechanism that decisively favors a relatively high fitness measure,
it is possible that, after a certain while, the entire population be significantly
similartothebestindividualsofar.Thiscanhamperthedevelopmentofother
solutions that could lead to better performance levels. The idea of diversity
is essential to allow that multiple optima of a given cost function be properly
explored, and this has a decisive impact in the capability of avoiding local
minima, which is essential in many signal processing tasks [23].
Other classical selection mechanisms are responsible for mitigating this
effect, which is related to the idea known in the literature as selective
pressure [22]. Among these methods we may highlight two: the rank and
tournament selection methods [127].
The method of selection based on rank generates the probabilities not
directly from the fitness measure, but from the position occupied by the
individuals in a ranking based on this measure. Therefore, for instance, an
enormous difference in the fitness of the best and the second best individu-
als will not necessarily lead to an enormous difference in the probability of
selection of these two solutions. The conclusion is that such a strategy has the
potential of reducing selective pressure. In fact, if a high selective pressure
is not desirable, the same is valid for a significantly low selective pressure,
so that the objective is to attain a solution that will lead to a satisfactory per-
formance. Naturally, this task is extremely complex, since the ideal choice
varies from case to case, but the user of a GA must keep in mind the need of
being aware of the role of the selection mechanism. In the case of the rank-
based mechanism, the choice of different functions to map the position of
an individual onto its probability of selection is a tool to control the perfor-
mance of the operator [127]. The steps described in
Algorithm 8.3
give an
idea of an implementation of the method to select a single individual.
