Selection¶

The selection process in genetic algorithms (GA) is a pivotal mechanism that emulates the principles of natural selection, allowing the propagation of individuals with higher fitness scores while gradually phasing out less fit solutions. This mimics the survival-of-the-fittest concept from Darwinian evolution, promoting the convergence of the population toward optimal or near-optimal solutions.

One commonly employed selection method is proportional or roulette wheel selection, where individuals are assigned probabilities of being selected based on their fitness scores. Higher-fitness individuals have larger slices of the “roulette wheel,” making them more likely to be chosen for reproduction. This probabilistic approach ensures that individuals with superior fitness contribute more genetic material to the next generation, mirroring the biological concept that successful traits are more likely to be inherited.

Another widely used selection mechanism is tournament selection, wherein individuals are randomly sampled from the population, and the one with the highest fitness is chosen as a parent for reproduction. This approach introduces an element of randomness and diversity, preventing the algorithm from fixating on a limited set of solutions.

The careful design of the selection process is crucial in balancing exploration and exploitation, allowing the genetic algorithm to efficiently navigate the solution space. Effective selection mechanisms contribute to the algorithm’s ability to efficiently explore diverse regions early in the optimization process and converge towards promising solutions as generations progress. The interplay between selection and genetic operators ensures the continual refinement of the population, guiding it toward increasingly optimal solutions over successive generations.

Key concepts in selection implementation¶

Mango’s selection process has to be separated in two steps:

First, we calculate the selection probabilities for each individual in the population. This is done by the selected selection process on the configuration of the algorithm. The different selection processes will be explained in the following section.
Secondly, based on the probabilities, a method is called to select the parents needed for the crossover (typically 2). The method used here is the _select_parents method.

Selection processes¶

Random selection¶

In this selection process the probability of selection of each parent is the same (\(\frac{1}{n}\) with \(n\) being the population size).

Caution

This selection process is not recommended as it does not take into account the fitness of the individuals and it can lead to a very slow convergence.

This selection process is implemented in the method: _random_selection.

Elitism selection¶

In this selection process the \(k\) best individuals are assigned the same probability of selection (\(\frac{1}{k}\)) while the rest of the individuals have a probability of zero.

Caution

This selection process can reduce the genetic diversity of the population and it can lead to a premature convergence. If the value of \(k\) is to low it may happen that all possible choices of parents are actually the same individual causing the algorithm to stop.

If \(k\) is equal to the population size, this selection process is equivalent to the random selection process.

This selection process is implemented in the method: _elitism_selection.

Rank selection¶

This selection process assigns a selection probability to each individual based on its rank in the population. This value is calculated as:

\[p_i = \frac{1}{n} * \left( s - (2s -2)\frac{i-1}{n-1} \right)\]

where \(s\) is the selection pressure or rank pressure (usually 2), \(n\) the size of the population and \(i\) is the rank of the individual, a value between \(1\) and \(n\), where the best individual has rank \(n\) and the worst rank \(1\).

Tip

The las individual in the population is going to have a probability of selection zero.

Caution

If the rank pressure is set up to 1 this selection process es equivalent to the random selection process.

This selection process is implemented in the method: _rank_selection.

The rank pressure is a parameter that can be set up in the configuration of the algorithm. The default value is 2. The name of the parameter is rank_pressure.

Order selection¶

This selection process assigns a selection probability to each individual based on its order in the population. This value is calculated as:

\[p_i = \frac{i * 2}{n * (n+1)}\]

where \(n\) the size of the population and \(i\) is the order of the individual, a value between \(1\) and \(n\), where the best individual has order \(n\) and the worst order \(1\).

Tip

The probabilities assigned to each individual are very similar to those calculated by the rank selection (with rank pressure 2) but the last individual does have a probability of being selected in this case.

This selection process is implemented in the method: _order_selection.

Roulette wheel selection¶

This selection process is also known as proportional selection. In this selection process the probability of selection of each individual is proportional to its fitness.

This selection process has two different methods to calculate the selection probabilities depending if the problem is to minimize or maximize. For minimization problems:

\[p_i = \frac{max(f_i) - f_i}{\sum_{j=1}^{n} (max(f_j) - f_j)}\]

But for maximization problems:

\[p_i = \frac{f_i - min(f_i)}{\sum_{j=1}^{n} (f_j - min(f_j)}\]

where \(f_i\) is the fitness of the individual \(i\) and \(n\) is the size of the population.

Based on these formulas the worst individual should not have a selection probability, but one is assigned based on the probability of the second worst.

Tournament selection¶

In this selection process a group of size \(k\) set by the parameter _tournament_size is randomly selected from the population. The individual with the best fitness in this group is awarded a win in their tournament. Then the selection probability is calculated based on the amount of wins each individual has and the total number of tournaments. The selection probability is calculated as:

\[p_i = \frac{w_i}{\sum_{j=1}^{n} w_j}\]

where \(w_i\) is the number of wins of the individual \(i\) and \(n\) is the size of the population.

Tip

This selection process can be a process to control the diversity as well, as the bigger the tournament size the less diversity there is going to be among the possible parents so less diversity among the future children that can pass to the next generation.

This selection process is implemented in the method: _tournament_selection.

To select this selection process the parameter selection in the config has to be set up to be tournament.

Boltzmann selection¶

This selection process has not been implemented yet but it is planned as a future feature.

Parent selection¶

Once each possible parent has a selection probability assigned to it a process is called to randomly select the number of parents needed (by default its 2). This process makes sure that the parents have different genes or genotype so that the crossover can have a chance to generate children with new genes.

If after a certain number of tries the process is not able to find a set of parents with different genes, the genetic algorithm stops and an exception is raised. This exception is of type GeneticDiversity.