Answers.Body: <h3>Overview</h3>
  <p>There are <strong>many selection operators</strong> (or methods) for evolutionary algorithms. These selection methods differ in the way they evaluate the individuals given their fitness or how they compute their fitness in the first place. Some selection operators select individuals <strong>deterministically</strong>, while others select them <strong>stochastically</strong>, which can prevent premature convergence, given that, for instance, in <strong>fitness proportionate selection</strong> (aka <em>roulette wheel selection</em>), a well-known selection operator, all individuals can be selected, although the fitter individuals have a higher probability of being selected. Each selection operator has different advantages and disadvantages compared to other selection operators.</p>
  <p>All these details are covered from chapter 22 (p. 166 and 203 of the linked pdf) onwards of the well-written book <a href="https://digi.lib.ttu.ee/services/copycat-pdf.php?ID=248" rel="nofollow noreferrer">Evolutionary Computation 1 Basic Algorithms and Operators</a> by Thomas Bäck et al. These concepts are also described in <a href="http://www.shahed.ac.ir/stabaii/Files/CompIntelligenceBook.pdf" rel="nofollow noreferrer">Computational Intelligence: An Introduction</a> (section 8.5, p. 135), in case you want to have an alternative reading.</p>
  <p>For completeness, I will enumerate and briefly describe some of the well-known selection operators.</p>
  <h3>Fitness proportionate selection (FPS)</h3>
  <p>This selection method is also known as <strong>roulette wheel selection (RWS)</strong>. In FPS, the probability of an individual being selected is proportional to its fitness. More precisely, let <span class="math-container">$f_i$</span> be the fitness of individual <span class="math-container">$i$</span>, then the probability of that individual being selected is</p>
  <p><span class="math-container">$$p_{i}={\frac {f_{i}}{\Sigma _{j=1}^{N}f_{j}}}$$</span></p>
  <p>FPS does not handle minimization problems directly and it requires the fitnesses to be non-negative (given that probabilities are in the range <span class="math-container">$[0, 1]$</span>), but the minimization problem can be transformed into a maximization one. The solutions are thus selected <strong>probabilistically</strong> in this case. There are other problems/issues with this selection method, which are described in the cited book (chapter 23, p. 172).</p>
  <h3>Tournament selection (TS)</h3>
  <p>In TS, at each generation, a set/group <span class="math-container">$Q = \{ a_1, \dots, a_q \}$</span> of <span class="math-container">$|Q| = q$</span> individuals is sampled (with or without replacement) <strong>at random</strong> from the current population of all individuals <span class="math-container">$P$</span>. Successively, this group <span class="math-container">$Q$</span> takes part in a so-called <strong>tournament</strong>, i.e. a loop of <span class="math-container">$\lambda$</span> iterations, where, for each iteration <span class="math-container">$j$</span>, the individual from the group <span class="math-container">$Q$</span> with the highest fitness <span class="math-container">$a_1'$</span> is selected (deterministically or stochastically) and inserted in a new set <span class="math-container">$S$</span>, which will contain the individuals that you will mutate and recombine. After this first iteration <span class="math-container">$j$</span>, <span class="math-container">$S$</span> contains only one individual, <span class="math-container">$S = \{a_1' \}$</span>. In the second iteration, we perform the same thing, and obtain <span class="math-container">$S = \{a_1', a_2' \}$</span>, and so on. So, after <span class="math-container">$\lambda$</span> iterations, <span class="math-container">$S$</span> contains <span class="math-container">$\lambda$</span> individuals, i.e. <span class="math-container">$|S| = \lambda$</span>. Note that <span class="math-container">$a_1'$</span> is not necessarily equal to <span class="math-container">$a_1 \in Q$</span>. The individuals in <span class="math-container">$S$</span> are the ones that undergo mutation and cross-over in <em>this</em> generation. In the next generation, you repeat this <em>tournament</em> process for selecting the best <span class="math-container">$q$</span> individuals. Typically, you need to have at least <span class="math-container">$q = 2$</span> (i.e. <strong>binary tournament selection</strong>), so that you have the opportunity to choose 2 different individuals for the cross-over. If <span class="math-container">$q=1$</span>, individuals are picked randomly from the population (given that you do not perform any tournament at all).</p>
  <h3>Rank-based selection (RS)</h3>
  <p>In RS, only the <strong>rank ordering</strong> of the individuals within the current population determines the probability of being selected. So, in RS, an individual has a probability of being selected <strong>not</strong> proportional to its fitness (as in FPS), but it is based on its rank (order) with respect to the other individuals. So, if the individual <span class="math-container">$a$</span> has is ranked <span class="math-container">$1$</span>st and individual <span class="math-container">$b$</span> is ranked <span class="math-container">$2$</span>nd, even if <span class="math-container">$a$</span> had a fitness a lot higher than individual <span class="math-container">$b$</span>, then its probability of being selected would not be a lot higher than the probability of selecting <span class="math-container">$b$</span>, while, in FPS, this would be the case. There are different ways of computing the rank, such as linear or non-linear. The details of how the rank can be computed are described in chapter 25 of the cited book.</p>
  <h3>Other selection methods</h3>
  <ul>
  <li>Boltzmann selection (chapter 26)</li>
  <li>Soft brood selection (chapter 27)</li>
  <li>Disruptive selection (chapter 27)</li>
  <li>Competitive selection (chapter 27)</li>
  <li>Truncation selection (chapter 29)</li>
  </ul>
  <h3>Other related concepts</h3>
  <p>There's also the related concept of <strong>elitism</strong>, where the best individuals of the current population are carried over to the next population/generation, and <a href="https://deap.readthedocs.io/en/0.7-a1/halloffame.html" rel="nofollow noreferrer"><strong>hall of fame</strong></a>, which is a data structure that stores the best individual for each generation.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-11-20T17:50:20.090Z
Answers.LastActivityDate: 2020-12-06T23:53:13.140Z
Answers.LastEditDate: 2020-12-06T23:53:13.140Z
Answers.UserDisplayName: nbro
Body: <p>In a genetic algorithm, there are different steps. One of those steps is the selection of chromosomes for reproduction. What are the available selection strategies in genetic algorithms?</p>
  
Tags: <genetic-algorithms><evolutionary-algorithms><selection-operators>
Title: What are the available selection methods in genetic algorithms?
UserDisplayName: Abbas Ali
ThreadText: # What are the available selection methods in genetic algorithms?
  
  (Asked by: username_0 on 2018-11-20)
  
  In a genetic algorithm, there are different steps. One of those steps is the selection of chromosomes for reproduction. What are the available selection strategies in genetic algorithms?
  
  **Tags:** genetic-algorithms, evolutionary-algorithms, selection-operators
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2018-11-20. Score: 3 | Accepted answer
  
  ### Overview
  
  There are **many selection operators** (or methods) for evolutionary algorithms. These selection methods differ in the way they evaluate the individuals given their fitness or how they compute their fitness in the first place. Some selection operators select individuals **deterministically**, while others select them **stochastically**, which can prevent premature convergence, given that, for instance, in **fitness proportionate selection** (aka *roulette wheel selection*), a well-known selection operator, all individuals can be selected, although the fitter individuals have a higher probability of being selected. Each selection operator has different advantages and disadvantages compared to other selection operators.
  
  All these details are covered from chapter 22 (p. 166 and 203 of the linked pdf) onwards of the well-written book [Evolutionary Computation 1 Basic Algorithms and Operators](https://digi.lib.ttu.ee/services/copycat-pdf.php?ID=248) by Thomas Bäck et al. These concepts are also described in [Computational Intelligence: An Introduction](http://www.shahed.ac.ir/stabaii/Files/CompIntelligenceBook.pdf) (section 8.5, p. 135), in case you want to have an alternative reading.
  
  For completeness, I will enumerate and briefly describe some of the well-known selection operators.
  
  ### Fitness proportionate selection (FPS)
  
  This selection method is also known as **roulette wheel selection (RWS)**. In FPS, the probability of an individual being selected is proportional to its fitness. More precisely, let $f\_i$ be the fitness of individual $i$, then the probability of that individual being selected is
  
  $$p\_{i}={\frac {f\_{i}}{\Sigma \_{j=1}^{N}f\_{j}}}$$
  
  FPS does not handle minimization problems directly and it requires the fitnesses to be non-negative (given that probabilities are in the range $[0, 1]$), but the minimization problem can be transformed into a maximization one. The solutions are thus selected **probabilistically** in this case. There are other problems/issues with this selection method, which are described in the cited book (chapter 23, p. 172).
  
  ### Tournament selection (TS)
  
  In TS, at each generation, a set/group $Q = \{ a\_1, \dots, a\_q \}$ of $|Q| = q$ individuals is sampled (with or without replacement) **at random** from the current population of all individuals $P$. Successively, this group $Q$ takes part in a so-called **tournament**, i.e. a loop of $\lambda$ iterations, where, for each iteration $j$, the individual from the group $Q$ with the highest fitness $a\_1'$ is selected (deterministically or stochastically) and inserted in a new set $S$, which will contain the individuals that you will mutate and recombine. After this first iteration $j$, $S$ contains only one individual, $S = \{a\_1' \}$. In the second iteration, we perform the same thing, and obtain $S = \{a\_1', a\_2' \}$, and so on. So, after $\lambda$ iterations, $S$ contains $\lambda$ individuals, i.e. $|S| = \lambda$. Note that $a\_1'$ is not necessarily equal to $a\_1 \in Q$. The individuals in $S$ are the ones that undergo mutation and cross-over in *this* generation. In the next generation, you repeat this *tournament* process for selecting the best $q$ individuals. Typically, you need to have at least $q = 2$ (i.e. **binary tournament selection**), so that you have the opportunity to choose 2 different individuals for the cross-over. If $q=1$, individuals are picked randomly from the population (given that you do not perform any tournament at all).
  
  ### Rank-based selection (RS)
  
  In RS, only the **rank ordering** of the individuals within the current population determines the probability of being selected. So, in RS, an individual has a probability of being selected **not** proportional to its fitness (as in FPS), but it is based on its rank (order) with respect to the other individuals. So, if the individual $a$ has is ranked $1$st and individual $b$ is ranked $2$nd, even if $a$ had a fitness a lot higher than individual $b$, then its probability of being selected would not be a lot higher than the probability of selecting $b$, while, in FPS, this would be the case. There are different ways of computing the rank, such as linear or non-linear. The details of how the rank can be computed are described in chapter 25 of the cited book.
  
  ### Other selection methods
  
  * Boltzmann selection (chapter 26)
  * Soft brood selection (chapter 27)
  * Disruptive selection (chapter 27)
  * Competitive selection (chapter 27)
  * Truncation selection (chapter 29)
  
  ### Other related concepts
  
  There's also the related concept of **elitism**, where the best individuals of the current population are carried over to the next population/generation, and [**hall of fame**](https://deap.readthedocs.io/en/0.7-a1/halloffame.html), which is a data structure that stores the best individual for each generation.
  
  
  ---
  
  