Selection (evolutionary algorithm)
In evolutionary algorithms (EA), selection is a mechanism by which individuals are chosen from a population. In a broader sense, selection is often counted among the genetic operators , although selection in EA does not operate at the gene level, but at the individual level. Evolutionary algorithms seek a solution to an optimization problem using principles of natural evolution . Selection is used to select solution candidates (individuals) for recombination ( parent selection ) and to determine the next generation ( environmental selection ), for this purpose the quality of the solution candidates is used, which is assigned to them by a fitness function . The biological model is natural selection . The procedures listed differ mainly in the selection pressure . The higher the selection pressure, the faster a population converges towards a particular solution and the search space is not sufficiently explored. If the pressure is too low, the population does not converge even after a long computation time .
In principle, each method can be used for both parent and environmental selection; special concepts have been established for the specific types of evolutionary algorithms .
Common methods
Best selection
The simplest method of selecting individuals from a population of solution candidates is to sort the population according to fitness and to take over the first individuals. In the case of environmental selection , a distinction is made between the consideration of only descendants ( comma selection :) or parents and descendants ( plus selection :) .
Fitness-proportional selection
The method of environmental selection originally proposed by John H. Holland for genetic algorithms is fitness-proportional selection. The selection of individuals corresponds to throwing a ball in roulette , each individual being assigned a portion of the roulette wheel that corresponds to their fitness. Even poorer solution candidates have a chance of being selected in this way, but at the beginning of the optimization often a few higher quality candidates dominate the entire selection process, as well above-average individuals benefit from the fact that each selection is made individually and with each selection there is a high probability that they will be selected. In this regard, stochastic universal sampling is an improvement. Here equidistant balls are thrown at once. Although individuals can also be selected several times here, stochastic universal sampling has a diversity-preserving effect compared to selection proportional to fitness.
Tournament selection
In the tournament selection , individuals are repeatedly selected from the population. Their fitness values are compared and the best individual wins (the tournament). The process is run multiple times. Advantages are the easy implementation, the low complexity and the fact that fitness values do not have to be available for every individual, but only for those who take part in the tournaments. The problem is that the best individuals do not necessarily have to be selected.
Rank selection
In the case of rank selection, the selection probability does not depend directly on fitness, but on the fitness rank of an individual within the population. This relativizes large differences in fitness, and the exact fitness values themselves do not have to be available, but only a sorting of the individuals according to quality.