Selection (evolutionary algorithm)

Selection is a <a href="/facts/Genetic_operator/M0VhYIBW">genetic operator</a> in an <a href="/facts/Evolutionary_algorithm/bo7eHlcA">evolutionary algorithm</a> (EA). An EA is a <a href="/facts/Metaheuristic/ECF71Rez">metaheuristic</a> inspired by <a href="/facts/Evolution/Hj0qAaBk">biological evolution</a> and aims to solve challenging problems at least <a href="/facts/Approximation/LvYHsXzq">approximately</a>. Selection has a dual purpose: on the one hand, it can choose individual genomes from a population for subsequent breeding (e.g., using the <a href="/facts/Crossover_(genetic_algorithm)/fRBnRV7r">crossover operator</a>). In addition, selection mechanisms are also used to choose candidate solutions (individuals) for the next generation. The biological model is <a href="/facts/Natural_selection/JXTte6en">natural selection</a>. 
Retaining the best individual(s) of one 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.
The basis for selection is the quality of an individual, which is determined by the <a href="/facts/Fitness_function/Xeoc1I3C">fitness function</a>. In <a href="/facts/Memetic_algorithm/m1oMttra">memetic algorithms</a>, an extension of EA, selection also takes place in the selection of those offspring that are to be improved with the help of a <a href="/facts/Meme/65Qsyhak">meme</a> (e.g. a <a href="/facts/Heuristic/BcBEkv9c">heuristic</a>).
A selection procedure for breeding used early on may be implemented as follows:

<ol><li>The fitness values that have been computed (<a href="/facts/Fitness_function/Xeoc1I3C">fitness function</a>) are normalized, such that the sum of all resulting fitness values equals 1.</li>
<li>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.</li>
<li>A random number R between 0 and 1 is chosen.</li>
<li>The selected individual is the first one whose accumulated normalized value is greater than or equal to R.</li></ol>
For many problems the above algorithm might be computationally demanding. A simpler and faster alternative uses the so-called stochastic acceptance.
If this procedure is repeated until there are enough selected individuals, this selection method is called <a href="/facts/Fitness_proportionate_selection/RSeQxJXS">fitness proportionate selection</a> 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 <a href="/facts/Stochastic_universal_sampling/NQM94tom">stochastic universal sampling</a>.
Repeatedly selecting the best individual of a randomly chosen subset is <a href="/facts/Tournament_selection/Tmm4QRsV">tournament selection</a>. Taking the best half, third or another proportion of the individuals is <a href="/facts/Truncation_selection/e9aFWxYf">truncation selection</a>.
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.

Selection (evolutionary algorithm) open-in-new

Selection (evolutionary algorithm)