Fitness-Proportionate Selection

A better approach to selection is to give every individual a chance of being selected to breed but to make fitter candidates more likely to be chosen than weaker individuals. This is achieved by making an individual's survival probability a function of its fitness score. Such strategies are known as fitness-proportionate selection.

Roulette Wheel Selection

The most common fitness-proportionate selection technique is called Roulette Wheel Selection. Conceptually, each member of the population is allocated a section of an imaginary roulette wheel. Unlike a real roulette wheel the sections are different sizes, proportional to the individual's fitness, such that the fittest candidate has the biggest slice of the wheel and the weakest candidate has the smallest. The wheel is then spun and the individual associated with the winning section is selected. The wheel is spun as many times as is necessary to select the full set of parents for the next generation.

Using this technique it is possible (probable) that one or more individuals is selected multiple times. That's OK, it's what we want to happen. Remember that we are not selecting the members of the next generation, we are selecting their parents and it is possible for an individual to be a parent multiple times. If there is a particularly fit member of the population we would expect it to be more successful at producing offspring than a weaker rival.

Stochastic Universal Sampling

Stochastic Universal Sampling is an elaborately-named variation of roulette wheel selection. Stochastic Universal Sampling ensures that the observed selection frequencies of each individual are in line with the expected frequencies. So if we have an individual that occupies 4.5% of the wheel and we select 100 individuals, we would expect on average for that individual to be selected between four and five times. Stochastic Universal Sampling guarantees this. The individual will be selected either four times or five times, not three times, not zero times and not 100 times. Standard roulette wheel selection does not make this guarantee.

Stochastic Universal Sampling works by making a single spin of the roulette wheel. This provides a starting position and the first selected individual. The selection process then proceeds by advancing all the way around the wheel in equal sized steps, where the step size is determined by the number of individuals to be selected. So if we are selecting 30 individuals we will advance by 1/30 x 360 degrees for each selection. Note that this does not mean that every candidate on the wheel will be selected. Some weak individuals will have very thin slices of the wheel and these might be stepped over completely depending on the random starting position.