Selection (evolutionary algorithm)

Selection is the stage of a genetic algorithm or more general evolutionary algorithm in which individual genomes are chosen from a population for later breeding (e.g., using the crossover operator). Selection mechanisms are also used to choose candidate solutions (individuals) for the next generation. 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.

A selection procedure for breeding used early on^[1] 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.

Methods of selection

The listed methods differ mainly in the selection pressure,^[2]^[3] which can be set by a strategy parameter in the rank selection described below. The higher the selection pressure, the faster a population converges against a certain solution and the search space may not be explored sufficiently. For more selection methods and further detail see.^[4]^[5]

Roulette wheel selection

In the roulette wheel selection, the probability of choosing an individual for breeding of the next generation is proportional to its fitness, the better the fitness is, the higher chance for that individual to be chosen. Choosing individuals can be depicted as spinning a roulette that has as many pockets as there are individuals in the current generation, with sizes depending on their probability. Probability of choosing individual $i$ is equal to $p_{i}={\frac {f_{i}}{\Sigma _{j=1}^{N}f_{j}}}$ , where $f_{i}$ is the fitness of $i$ and $N$ is the size of current generation (note that in this method one individual can be drawn multiple times).

Rank selection

In rank selection, the selection probability does not depend directly on the fitness, but on the fitness rank of an individual within the population. This puts large fitness differences into perspective; moreover, the exact fitness values themselves do not have to be available, but only a sorting of the individuals according to quality.

Linear ranking, which goes back to Baker,^[6]^[7] is often used. It allows the selection pressure to be set by the parameter $sp$ , which can take values between 1.0 (no selection pressure) and 2.0 (high selection pressure). The probability $P$ for rank positions $R_{i}$ is obtained as follows:

P(R_{i})={\frac {1}{n}}{\Bigl (}sp-(2sp-2){\frac {i-1}{n-1}}{\Bigr )}\quad \quad 1\leq i\leq n,\quad 1\leq sp\leq 2\quad {\mathsf {with}}\quad P(R_{i})\geq 0,\quad \sum _{i=1}^{n}P(R_{i})=1

In addition to the adjustable selection pressure, an advantage of rank-based selection can additionally be seen in the fact that it also gives worse individuals a chance to reproduce and thus to improve.^[8] This can be particularly helpful in applications with restrictions, since it facilitates the overcoming of a restriction in several intermediate steps, i.e. via a sequence of several individuals rated poorly due to restriction violations.

Steady state selection

In every generation few chromosomes are selected (good - with high fitness) for creating a new offspring. Then some (bad - with low fitness) chromosomes are removed and the new offspring is placed in their place. The rest of population survives to new generation.

Tournament selection

Tournament selection is a method of choosing the individual from the set of individuals. The winner of each tournament is selected to perform crossover.

Elitist selection

Often to get better results, strategies with partial reproduction are used. One of them is elitism, in which a small portion of the best individuals from the last generation is carried over (without any changes) to the next one.

Boltzmann selection

In Boltzmann selection, a continuously varying temperature controls the rate of selection according to a preset schedule. The temperature starts out high, which means that the selection pressure is low. The temperature is gradually lowered, which gradually increases the selection pressure, thereby allowing the GA to narrow in more closely to the best part of the search space while maintaining the appropriate degree of diversity.^[9]

References

^ Holland, John H. (1992). Adaptation in natural and artificial systems. PhD thesis, The University of Michigan, 1975. Cambridge, Mass.: MIT Press. ISBN 0-585-03844-9. OCLC 42854623.
^ Back, T. (1994). "Selective pressure in evolutionary algorithms: A characterization of selection mechanisms". Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence. Orlando, FL, USA: IEEE. pp. 57–62. doi:10.1109/ICEC.1994.350042. ISBN 978-0-7803-1899-1. S2CID 195867383.
^ Goldberg, David E.; Deb, Kalyanmoy (1991), "A Comparative Analysis of Selection Schemes Used in Genetic Algorithms", Foundations of Genetic Algorithms, vol. 1, Elsevier, pp. 69–93, CiteSeerX 10.1.1.101.9494, doi:10.1016/b978-0-08-050684-5.50008-2, ISBN 978-0-08-050684-5, S2CID 938257, retrieved 2023-01-09
^ Eiben, A.E.; Smith, J.E. (2015). "Fitness, Selection, and Population Management". Introduction to Evolutionary Computing. Natural Computing Series. Berlin, Heidelberg: Springer. pp. 79–98. doi:10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID 20912932.
^ De Jong, Kenneth A. (2006). Evolutionary computation : a unified approach. Cambridge, Mass.: MIT Press. ISBN 978-0-262-25598-1. OCLC 69652176.
^ Baker, James E. (1985), Grefenstette, John J. (ed.), "Adaptive Selection Methods for Genetic Algorithms", Conf. Proc. of the 1st Int. Conf. on Genetic Algorithms and Their Applications (ICGA), Hillsdale, New. Jersey: L. Erlbaum Associates, pp. 101–111, ISBN 0-8058-0426-9
^ Baker, James E. (1987), Grefenstette, John J. (ed.), "Reducing Bias and Inefficiency in the Selection Algorithm", Conf. Proc. of the 2nd Int. Conf. on Genetic Algorithms and Their Applications (ICGA), Hillsdale, New. Jersey: L. Erlbaum Associates, pp. 14–21, ISBN 0-8058-0158-8
^ Whitley, Darrell (1989), Schaffer, J.D. (ed.), "The GENITOR Algorithm and Selection Pressure: Why Rank-Based Allocation of Reproductive Trials is Best", Proceedings of the Third International Conference on Genetic Algorithms (ICGA), San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., pp. 116–121, ISBN 978-1-55860-066-9
^ Sivanandam, S. N. (2013). Principles of soft computing. Deepa, S. N. New Delhi: Wiley. ISBN 978-1-118-54680-2. OCLC 891566849.

External links

[1] Holland, John H. (1992). Adaptation in natural and artificial systems. PhD thesis, The University of Michigan, 1975. Cambridge, Mass.: MIT Press. ISBN 0-585-03844-9. OCLC 42854623.

[2] Back, T. (1994). "Selective pressure in evolutionary algorithms: A characterization of selection mechanisms". Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence. Orlando, FL, USA: IEEE. pp. 57–62. doi:10.1109/ICEC.1994.350042. ISBN 978-0-7803-1899-1. S2CID 195867383.

[3] Goldberg, David E.; Deb, Kalyanmoy (1991), "A Comparative Analysis of Selection Schemes Used in Genetic Algorithms", Foundations of Genetic Algorithms, vol. 1, Elsevier, pp. 69–93, CiteSeerX 10.1.1.101.9494, doi:10.1016/b978-0-08-050684-5.50008-2, ISBN 978-0-08-050684-5, S2CID 938257, retrieved 2023-01-09

[4] Eiben, A.E.; Smith, J.E. (2015). "Fitness, Selection, and Population Management". Introduction to Evolutionary Computing. Natural Computing Series. Berlin, Heidelberg: Springer. pp. 79–98. doi:10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID 20912932.

[5] De Jong, Kenneth A. (2006). Evolutionary computation : a unified approach. Cambridge, Mass.: MIT Press. ISBN 978-0-262-25598-1. OCLC 69652176.

[6] Baker, James E. (1985), Grefenstette, John J. (ed.), "Adaptive Selection Methods for Genetic Algorithms", Conf. Proc. of the 1st Int. Conf. on Genetic Algorithms and Their Applications (ICGA), Hillsdale, New. Jersey: L. Erlbaum Associates, pp. 101–111, ISBN 0-8058-0426-9

[7] Baker, James E. (1987), Grefenstette, John J. (ed.), "Reducing Bias and Inefficiency in the Selection Algorithm", Conf. Proc. of the 2nd Int. Conf. on Genetic Algorithms and Their Applications (ICGA), Hillsdale, New. Jersey: L. Erlbaum Associates, pp. 14–21, ISBN 0-8058-0158-8

[8] Whitley, Darrell (1989), Schaffer, J.D. (ed.), "The GENITOR Algorithm and Selection Pressure: Why Rank-Based Allocation of Reproductive Trials is Best", Proceedings of the Third International Conference on Genetic Algorithms (ICGA), San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., pp. 116–121, ISBN 978-1-55860-066-9

[9] Sivanandam, S. N. (2013). Principles of soft computing. Deepa, S. N. New Delhi: Wiley. ISBN 978-1-118-54680-2. OCLC 891566849.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

v t e Evolutionary computation
Main Topics	Evolutionary algorithm Evolutionary data mining Evolutionary multimodal optimization Human-based evolutionary computation Interactive evolutionary computation
Algorithms	Cellular evolutionary algorithm Covariance Matrix Adaptation Evolution Strategy (CMA-ES) Cultural algorithm Differential evolution Evolutionary programming Genetic algorithm Genetic programming Gene expression programming Evolution strategy Natural evolution strategy Neuroevolution Learning classifier system
Related techniques	Swarm intelligence Ant colony optimization Bees algorithm Cuckoo search Particle swarm optimization Bacterial Colony Optimization
Metaheuristic methods	Firefly algorithm Harmony search Gaussian adaptation Memetic algorithm
Related topics	Artificial development Artificial intelligence Artificial life Digital organism Evolutionary robotics Fitness function Fitness landscape Fitness approximation Genetic operators Interactive evolutionary computation No free lunch in search and optimization Machine learning Mating pool Premature convergence Program synthesis
Journals	Evolutionary Computation (journal)