8.3.1 Selection

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.

8.3.1.1 Roulette Wheel Selection

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 $v$ by $\mathrm{eval}(v)$. If $F:=\sum_k \mathrm{eval}(v_k)$ is the total fitness of the population, then the probability that an individual $v_k$ is chosen is $p_k:=\mathrm{eval}(v_k)/F$. Choosing one individual $v_k$ from the population with its probability $p_k$ can be accomplished by defining its cumulative probability $q_k := \sum_{i=1}^k p_i$ and setting $q_0:=0$. Given a random real number $r$ from the interval $[0,1]$, the individual $v_k$ is chosen so that $q_{k-1} \le r < q_k$.

Simple roulette wheel selection is only possible when $\mathrm{eval}(v_k)$ 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.

8.3.1.2 Roulette Wheel Selection after Linear Scaling

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 $n$ is the number of individuals, then the best individual $v_1$ is assigned a fitness value of $\mathrm{eval}(v_1):=\alpha n$, the worst one $v_n$ a value of  $\mathrm{eval}(v_n):=1$, and all other individuals values linearly in between. Here $\alpha>1/n$ is a real parameter usually chosen from the interval $(1,5]$. Then roulette wheel selection proceeds as above.