Genetic Algorithms Selection

The selection operator refers to the method used for selecting which chromosomes will be reproducing. The fitness function evaluates each of the chromosomes (candidate solutions), and the fitter the chromosome, the more likely it will be selected to reproduce. Selection procedures can be broadly classified into two classes as follows.

Fitness Proportionate Selection

This includes methods such as roulette-wheel selection (Holland, 1975; Goldberg, 1989b) and stochastic universal selection (Baker, 1985; Grefenstette and Baker, 1989). In roulette-wheel selection, each individual in the population is assigned a roulette wheel slot sized in proportion to its fitness. That is, in the biased roulette wheel, good solutions have a larger slot size than the less fit solutions. The roulette wheel is spun to obtain a reproduction candidate. The roulettewheel selection scheme can be implemented as follows:

1. Evaluate the fitness, ƒ_i , of each individual in the population.
2. Compute the probability (slot size), p_i , of selecting each member of the population:
   , where n is the population size.
3. Calculate the cumulative probability, qi , for each individual: qi =
4. Generate a uniform random number, r ∈ (0, 1).
5. If r< q₁ then select the first chromosome, x₁, else select the individual x_i such that q_i-1< r = q_i.
6. Repeat steps 4–5 n times to create n candidates in the mating pool.

Ordinal Selection

This includes methods such as tournament selection (Goldberg et al., 1989b), and truncation selection (Muhlenbein and Schlierkamp-Voosen, 1993). In tournament selection, s chromosomes are chosen at random (either with or without replacement) and entered into a tournament against each other. The fittest individual in the group of k chromosomes wins the tournament and is selected as the parent. The most widely used value of s is 2. Using this selection scheme, n tournaments are required to choose n individuals. In truncation selection, the top (1/s)th of the individuals get s copies each in the mating pool.

Related Posts :
Genetic Algorithms
Genetic Algorithm Operators
Genetic Algorithms Selection
Genetic Algorithms Crossover
Genetic Algorithms Mutation and Replacement