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?
Roulette wheel selection (aka Fitness proportionate selection)
The fitness is used to associate a probability of selection to each individual.
If fi is the fitness of individual i in the population, its probability of being selected is:
pi = fi / Σ j(fj) 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:
S
). r
in the interval [0; S]. For possible implementations see:
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)
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)