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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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 by Thomas Bäck et al. These concepts are also described in Computational Intelligence: An Introduction (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, which is a data structure that stores the best individual for each generation.