What is the difference between roulette wheel selection, rank selection and tournament selection?

Question

I'm reading a slide about genetic programming, where some methods to select individuals, such as roulette wheel selection, rank selection and tournament selection, are mentioned.

What is the difference between these three selection methods?

Faucal

Answer 1

Roulette wheel selection (aka Fitness proportionate selection)

The fitness is used to associate a probability of selection to each individual.

If f_i is the fitness of individual i in the population, its probability of being selected is:

p_i = f_i / Σ _j(f_j) for j = 1 … N (N is the number of individuals in the population)

It's called roulette wheel because it can be seen as a roulette wheel in a casino:

This can be simulated by the following (naive) algorithm:

1. Calculate the sum of all fitnesses in population (sum S).
2. Generate a random number r in the interval [0; S].
3. Go through the population and sum fitnesses. When the sum s is greater than r, stop and return the individual where you are.

For possible implementations see:

• Roulette wheel selection algorithm
• Roulette Selection in Genetic Algorithms

---

Rank Selection is similar to roulette wheel selection except that selection probability is proportional to relative fitness rather than absolute fitness.

It doesn't make any difference whether the fittest candidate is ten times fitter than the next fittest or 0.001% fitter. In both cases the selection probabilities would be the same.

All that matters is the ranking relative to other individuals.

Rank selection is easy to implement when you already know on roulette wheel selection. Instead of using the fitness as probability for getting selected you use the rank. So for a population of N solutions the best solution gets rank N, the second best rank N-1, etc. The worst individual has rank 1.

(Ranking Selection in Genetic Algorithm code)

---

Tournament selection

1. Choose few individuals at random from the population (a tournament).
2. The individual with the best fitness (the winner) is selected for crossover.

As you can see it's efficient to code. It also works on parallel architectures and allows the selection pressure to be easily adjusted (changing the number of individuals in a tournament).

Of course there are many variants of these algorithms.

For a comparison you could read:

Comparison of Performance between Different Selection Strategies on Simple Genetic Algorithms (Jinghui Zhong , Xiaomin Hu , Min Gu , Jun Zhang - 2005)

Aniline

Really exhaustive and documented answer about the topic! – Beguile

The above link for the comparison of Roulette Selection vs Tournament Selection is expired, please refer to link – Extraditable