IX. Selection

Introduction

As you already know from the GA outline, chromosomes are selected from the population to be parents to crossover. The question is how to select these chromosomes. According to Darwin's theory of evolution, the fittest individuals should survive and create new offspring. There are many ways to select the best chromosomes, such as roulette wheel selection, Boltzmann selection, tournament selection, rank selection, steady-state selection, and others.

Some of them will be described in this chapter.

Roulette Wheel Selection

Parents are selected according to their fitness. The better the chromosomes are, the greater their chance of being selected. Imagine a roulette wheel on which all chromosomes in the population are placed, each occupying a space proportional to its fitness, as shown in the following figure.

graph

Then a marble is thrown onto the wheel and selects a chromosome. Chromosomes with higher fitness will be selected more often.

This can be simulated by the following algorithm.

  1. [Sum] Calculate the sum of all chromosome fitness values in the population - sum S.
  2. [Select] Generate a random number from the interval (0,S) - r.
  3. [Loop] Go through the population and keep a running sum of fitness values from 0 - sum s. When the sum s becomes greater than r, stop and return the chromosome at that position.

Of course, step 1 is performed only once for each population.

Rank Selection

The previous method can cause problems when the fitness values differ too much. For example, if the best chromosome occupies 90% of the roulette wheel, the other chromosomes will have very little chance of being selected.

Rank selection first ranks the population and then every chromosome receives a fitness value based on this ranking. The worst chromosome gets fitness 1, the second worst gets 2, and so on, while the best chromosome gets fitness N (the number of chromosomes in the population).

You can see in the following figures how the situation changes when fitness is replaced by rank.

graph

Situation before ranking (graph of fitnesses)

graph

Situation after ranking (graph of order numbers)

After this, all chromosomes have a chance to be selected. However, this method can lead to slower convergence because the best chromosomes no longer differ so much from the others.

Steady-State Selection

This is not a particular method of selecting parents. The main idea of this approach is that a large part of the population should survive into the next generation.

The GA then works in the following way. In each generation, a few good chromosomes (those with high fitness) are selected to create new offspring. Then some bad chromosomes (those with low fitness) are removed, and the new offspring are placed in their positions. The rest of the population survives into the new generation.

Elitism

The idea of elitism has already been introduced. When creating a new population through crossover and mutation, there is a significant chance that we will lose the best chromosome.

Elitism is the name of a method that first copies the best chromosome (or a few best chromosomes) into the new population. The rest is then created in the usual way. Elitism can significantly improve the performance of a GA because it prevents the loss of the best found solution.