Selection (genetic algorithm)
From Wikipedia, the free encyclopedia
Selection is the stage of a genetic algorithm in which individual genomes are chosen from a population for later breeding (recombination or crossover).
There are several generic selection algorithms. One of the common ones is the so-called roulette wheel selection, which can be implemented as follows:
- The fitness function is evaluated for each individual, providing fitness values, which are then normalized. Normalization means multiplying the fitness value of each individual by a fixed number, so that the sum of all fitness values equals 1.
- The population is sorted by descending fitness values.
- Accumulated normalized fitness values are computed (the accumulated fitness value of an individual is the sum of its own fitness value plus the fitness values of all the previous individuals). The accumulated fitness of the last individual should of course be 1 (otherwise something went wrong in the normalization step!).
- A random number R between 0 and 1 is chosen.
- The selected individual is the first one whose accumulated normalized value is greater than R.
There are other selection algorithms that do not consider all individuals for selection, but only those with a fitness value that is higher than a given (arbitrary) constant. Other algorithms select from a restricted pool where only a certain percentage of the individuals are allowed, based on fitness value.
See the main article on genetic algorithms for more details.
