In the selection step individuals from the current population are selected to form the next population, where individuals of good fitness must be selected more often. Here good fitness means that an individual is likely to solve the optimization problem considered. The selection step is crucial since the right balance between support of individuals of good and bad fitness has to be found. The first, simple possibility is roulette wheel selection. An improved version of roulette wheel selection uses linearly scaled probabilities of selection between the best and the worst individual.
The name of this selection method stems from the fact that here a
roulette wheel with slots sized according to the fitness of the
individuals is used. We will denote the fitness (or positive
objective function) of an individual by
. If
is the total fitness of the population, then the
probability that an individual
is chosen is
.
Choosing one individual
from the population with its
probability
can be accomplished by defining its cumulative
probability
and setting
. Given a
random real number
from the interval
, the individual
is chosen so that
.
Simple roulette wheel selection is only possible when
is
positive. Moreover the probabilities of selection depend on the
absolute values of the objective function, i.e., adding a constant to
the objective function yields different probabilities of selection.
This effect can be avoided by not using the values of the objective
function directly, but indirectly by sorting the population according
to the objective function. If is the number of individuals, then
the best individual
is assigned a fitness value of
, the worst one
a value
of
, and all other individuals values linearly in
between. Here
is a real parameter usually chosen from
the interval
. Then roulette wheel selection proceeds as
above.
Clemens Heitzinger 2003-05-08