Editing Selection (evolutionary algorithm) (section)

{{Short description|none}}
{{Evolutionary algorithms}}
'''Selection''' is a [[genetic operator]] in an [[evolutionary algorithm]] (EA). An EA is a [[metaheuristic]] inspired by [[Evolution|biological evolution]] and aims to solve challenging problems at least [[Approximation|approximately]]. Selection has a dual purpose: on the one hand, it can choose individual genomes from a population for subsequent breeding (e.g., using the [[Crossover (genetic algorithm)|crossover operator]]). In addition, selection mechanisms are also used to choose candidate solutions (individuals) for the next generation. The biological model is [[natural selection]]. 

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 [[fitness function]]. In [[Memetic algorithm|memetic algorithms]], an extension of EA, selection also takes place in the selection of those offspring that are to be improved with the help of a [[meme]] (e.g. a [[heuristic]]).

A selection procedure for breeding used early on<ref>{{Cite book |last=Holland |first=John H. |title=Adaptation in natural and artificial systems |date=1992 |publisher=MIT Press |others=PhD thesis, The University of Michigan, 1975 |isbn=0-585-03844-9 |edition= |location=Cambridge, Mass. |oclc=42854623}}</ref> may be implemented as follows:
#The fitness values that have been computed ([[fitness function]]) are normalized, such that the sum of all resulting fitness values equals 1.
#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 or equal to ''R''.

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 [[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.