Editing Selection (evolutionary algorithm) (section)

== Methods of selection==
The listed methods differ mainly in the selection pressure,<ref>{{Cite book |last=Bäck |first=Thomas |title=Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence |date=1994 |publisher=IEEE |isbn=978-0-7803-1899-1 |location=Orlando, FL, USA |pages=57–62 |chapter=Selective pressure in evolutionary algorithms: A characterization of selection mechanisms |doi=10.1109/ICEC.1994.350042 |chapter-url=https://ieeexplore.ieee.org/document/350042 |s2cid=195867383}}</ref><ref>{{Citation |last1=Goldberg |first1=David E. |title=A Comparative Analysis of Selection Schemes Used in Genetic Algorithms |date=1991 |url=https://linkinghub.elsevier.com/retrieve/pii/B9780080506845500082 |work=Foundations of Genetic Algorithms |volume=1 |pages=69–93 |publisher=Elsevier |language=en |doi=10.1016/b978-0-08-050684-5.50008-2 |isbn=978-0-08-050684-5 |access-date=2023-01-09 |last2=Deb |first2=Kalyanmoy|s2cid=938257 |citeseerx=10.1.1.101.9494 }}</ref> 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. This [[premature convergence]]<ref>{{Cite journal |last1=Leung |first1=Yee |last2=Gao |first2=Yong |last3=Xu |first3=Zong-Ben |date=September 1997 |title=Degree of population diversity - a perspective on premature convergence in genetic algorithms and its Markov chain analysis |url=https://ieeexplore.ieee.org/document/623217 |journal=IEEE Transactions on Neural Networks |volume=8 |issue=5 |pages=1165–1176 |doi=10.1109/72.623217 |pmid=18255718 |issn=1045-9227|url-access=subscription }}</ref> can be counteracted by [[Population model (evolutionary algorithm)|structuring the population]] appropriately.<ref name=":0">{{Cite book |last=Gorges-Schleuter |first=Martina |title=Genetic Algorithms and Population Structures - A Massively Parallel Algorithm |date=1990 |publisher=University of Dortmund, Faculty of Computer Science |location=Dortmund, FRG |language=en |type=PhD}}</ref><ref>{{Cite book |last1=Alba |first1=Enrique |title=Cellular genetic algorithms |last2=Dorronsoro |first2=Bernabé |date=2008 |publisher=Springer |isbn=978-0-387-77610-1 |series=Operations research/computer science interfaces series |location=New York}}</ref> There is a close correlation between the population model used and a suitable selection pressure.<ref name=":0" /> If the pressure is too low, it must be expected that the population will not converge even after a long computing time. For more selection methods and further detail see.<ref>{{Cite book |last1=Eiben |first1=A.E. |url=http://link.springer.com/10.1007/978-3-662-44874-8 |title=Introduction to Evolutionary Computing |last2=Smith |first2=J.E. |date=2015 |publisher=Springer |isbn=978-3-662-44873-1 |series=Natural Computing Series |location=Berlin, Heidelberg |pages=79–98 |chapter=Fitness, Selection, and Population Management |doi=10.1007/978-3-662-44874-8|s2cid=20912932 }}</ref><ref>{{Cite book |last=De Jong |first=Kenneth A. |url=https://www.worldcat.org/oclc/69652176 |title=Evolutionary computation : a unified approach |date=2006 |publisher=MIT Press |isbn=978-0-262-25598-1 |location=Cambridge, Mass. |oclc=69652176}}</ref>

=== Roulette wheel selection ===
In the [[Fitness_proportionate_selection|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 <math>i</math> is equal to <math>p_i = \frac{f_i}{\Sigma_{j=1}^{N} f_j}</math>, where <math>f_i</math> is the fitness of <math>i</math> and <math>N</math> is the size of current generation (note that in this method one individual can be drawn multiple times).

====Stochastic universal sampling====
[[Stochastic universal sampling]] is a development of roulette wheel selection with minimal spread and no bias.

=== Rank selection ===
In rank selection, the probability for selection does not depend directly on the fitness, but on the fitness rank of an individual within the population.<ref name=selist/> The exact fitness values themselves do not have to be available, but only a sorting of the individuals according to quality.
 
In addition to the adjustable selection pressure, an advantage of rank-based selection can be seen in the fact that it also gives worse individuals a chance to reproduce and thus to improve.<ref name=":1">{{Citation |last=Whitley |first=Darrell |title=The GENITOR Algorithm and Selection Pressure: Why Rank-Based Allocation of Reproductive Trials is Best |date=1989 |work=Proceedings of the Third International Conference on Genetic Algorithms (ICGA) |pages=116–121 |editor-last=Schaffer |editor-first=J.D. |url=https://www.researchgate.net/publication/2527551 |place=San Francisco, CA, USA |publisher=Morgan Kaufmann Publishers Inc. |isbn=978-1-55860-066-9}}</ref> 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.

==== Linear rank selection ====
Linear ranking, which goes back to Baker,<ref>{{Citation |last=Baker |first=James E. |title=Adaptive Selection Methods for Genetic Algorithms |date=1985 |work=Conf. Proc. of the 1st Int. Conf. on Genetic Algorithms and Their Applications (ICGA)  |pages=101–111 |editor-last=Grefenstette |editor-first=John J. |place=Hillsdale, New. Jersey |publisher=L. Erlbaum Associates |isbn=0-8058-0426-9 }}</ref><ref>{{Citation |last=Baker |first=James E. |title=Reducing Bias and Inefficiency in the Selection Algorithm |date=1987 |work=Conf. Proc. of the 2nd Int. Conf. on Genetic Algorithms and Their Applications (ICGA)  |pages=14–21 |editor-last=Grefenstette |editor-first=John J. |place=Hillsdale, New. Jersey |publisher=L. Erlbaum Associates |isbn=0-8058-0158-8 }}</ref> is often used.<ref name=":0" /><ref name=":1" /><ref>{{Citation |last1=Hoffmeister |first1=Frank |title=Genetic Algorithms and evolution strategies: Similarities and differences |date=1991 |work=Parallel Problem Solving from Nature |volume=496 |pages=455–469 |editor-last=Schwefel |editor-first=Hans-Paul |url= |access-date= |place=Berlin, Heidelberg |publisher=Springer-Verlag |language=en |doi=10.1007/bfb0029787 |isbn=978-3-540-54148-6 |last2=Bäck |first2=Thomas |editor2-last=Männer |editor2-first=Reinhard}}</ref> It allows the selection pressure to be set by the parameter <math>sp </math>, which can take values between 1.0 (no selection pressure) and 2.0 (high selection pressure). The probability <math>P </math> for <math>n</math> rank positions <math>R_i </math> is obtained as follows:
:<math>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) \ge 0, \quad \sum_{i=1}^nP(R_i)=1 </math>

Another definition for the probability <math>P</math> for rank positions <math>i</math> is:<ref name=selist>{{cite journal |last1=Jannoud |first1=Ismael |last2=Jaradat |first2=Yousef |last3=Masoud |first3=Mohammad Z. |last4=Manasrah |first4=Ahmad |last5=Alia |first5=Mohammad |title=The Role of Genetic Algorithm Selection Operators in Extending WSN Stability Period: A Comparative Study |journal=Electronics |date=22 December 2021 |volume=11 |issue=1 |pages=28 |doi=10.3390/electronics11010028|doi-access=free }}</ref>
:<math>P(i) =\frac{2*(n-i+1)}{n*(n+1)}</math>

==== Exponential rank selection ====
Exponential rank selection is defined as follows:<ref name=selist/> 

<math>P(i) = \frac{w^{n-i}}{\sum_{k=1}^{n}{w^{n-k}}}, 0\leq w\leq 1</math>

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

=== Truncation selection ===
For [[truncation selection]], individuals are sorted according to their fitness and a portion (10% to 50%) of the top individuals is selected for next generation.<ref name=selist/>

=== 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.<ref>{{Cite book|last=Sivanandam, S. N.|url=https://www.worldcat.org/oclc/891566849|title=Principles of soft computing|date=2013|publisher=Wiley|others=Deepa, S. N.|isbn=978-1-118-54680-2|location=New Delhi|oclc=891566849}}</ref>