Selection (genetic algorithm)
Encyclopedia
Selection is the stage of a genetic algorithm
in which individual genomes are chosen from a population for later breeding (recombination or crossover).
A generic selection procedure may be implemented as follows:
If this procedure is repeated until there are enough selected individuals, this selection method is called fitness proportionate selection
or roulette-wheel selection. If instead of a single pointer spun multiple times, there are multiple, equally spaced pointers on a wheel that is spun once, it is called stochastic universal sampling
.
Repeatedly selecting the best individual of a randomly chosen subset is tournament selection
. Taking the best half, third or another proportion of the individuals is truncation selection
.
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.
Retaining the best individuals in a generation unchanged in the next generation, is called elitism or elitist selection. It is a successful (slight) variant of the general process of constructing a new population.
See the main article on genetic algorithm
s for the context in which selection is used.
Genetic algorithm
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
in which individual genomes are chosen from a population for later breeding (recombination or crossover).
A generic selection procedure may be implemented as follows:
- The fitness functionFitness functionA fitness function is a particular type of objective function that is used to summarise, as a single figure of merit, how close a given design solution is to achieving the set aims....
is evaluated for each individual, providing fitness values, which are then normalized. Normalization means dividing the fitness value of each individual by the sum of all fitness values, so that the sum of all resulting 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 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.
If this procedure is repeated until there are enough selected individuals, this selection method is called fitness proportionate selection
Fitness proportionate selection
Fitness proportionate selection, also known as roulette-wheel selection, is a genetic operator used in genetic algorithms for selecting potentially useful solutions for recombination....
or roulette-wheel selection. If instead of a single pointer spun multiple times, there are multiple, equally spaced pointers on a wheel that is spun once, it is called stochastic universal sampling
Stochastic universal sampling
Stochastic universal sampling is a technique used in genetic algorithms for selecting potentially useful solutions for recombination. It was introduced by James Baker....
.
Repeatedly selecting the best individual of a randomly chosen subset is tournament selection
Tournament selection
Tournament selection is a method of selecting an individual from a population of individuals in a genetic algorithm. Tournament selection involves running several "tournaments" among a few individuals chosen at random from the population. The winner of each tournament is selected for crossover...
. Taking the best half, third or another proportion of the individuals is truncation selection
Truncation selection
Truncation selection is a selection method used in genetic algorithms to select potential candidate solutions for recombination.In truncation selection the candidate solutions are ordered by fitness, and some proportion, p, , of the fittest individuals are selected and reproduced 1/p times...
.
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.
Retaining the best individuals in a generation unchanged in the next generation, is called elitism or elitist selection. It is a successful (slight) variant of the general process of constructing a new population.
See the main article on genetic algorithm
Genetic algorithm
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
s for the context in which selection is used.
See Also
- Fitness proportionate selectionFitness proportionate selectionFitness proportionate selection, also known as roulette-wheel selection, is a genetic operator used in genetic algorithms for selecting potentially useful solutions for recombination....
- Stochastic universal samplingStochastic universal samplingStochastic universal sampling is a technique used in genetic algorithms for selecting potentially useful solutions for recombination. It was introduced by James Baker....
- Tournament selectionTournament selectionTournament selection is a method of selecting an individual from a population of individuals in a genetic algorithm. Tournament selection involves running several "tournaments" among a few individuals chosen at random from the population. The winner of each tournament is selected for crossover...