Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 36 ยท Selection

Roulette Wheel and Stochastic Universal Sampling

Implement fitness-proportionate (roulette wheel) selection and stochastic universal sampling in Python, see how it behaves, and learn its weaknesses with negative or skewed fitness.

Selection decides who gets to reproduce. It is the force that turns random variation into progress: without it, crossover and mutation would just shuffle genes. The oldest and most intuitive selection method is roulette wheel selection, also called fitness-proportionate selection. Each individual gets a slice of a wheel whose size is proportional to its fitness, and you spin the wheel once per parent you need.

This lesson implements the wheel, measures how it behaves, adds the lower-variance variant called stochastic universal sampling (SUS), and shows where proportional selection goes wrong.

The idea

Suppose four individuals have fitness 10, 30, 40 and 20. The total is 100, so their probabilities of being picked are 10 %, 30 %, 40 % and 20 %. Picture a roulette wheel cut into four pie slices of those sizes and a single ball. Better individuals are more likely to be chosen, but weak ones still have a chance, which keeps diversity alive.

Formally, individual i is selected with probability

p_i = f_i / (f_1 + f_2 + ... + f_N)

This requires non-negative fitness where higher is better, which is why designing fitness functions matters.

Implementing the wheel

The standard trick is a cumulative sum. Compute running totals of the fitness values, draw a random number r between 0 and the total, and return the first individual whose cumulative sum reaches r.

Python Roulette wheel selection from scratch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

bisect_left finds the slice in O(log N) time. A naive loop that walks the list takes O(N) per spin, which is fine for small populations but slow for large ones. The observed shares converge to the expected shares when the draws are many.

Why the wheel has high variance

The wheel is fair in expectation, but with only N spins it is noisy. An individual with a 10 % share has an expected 3 copies in 30 spins, but may get 0 or 7. This sampling error can cause a good individual to vanish by bad luck, or an average one to dominate.

Stochastic universal sampling (SUS) fixes this with a single spin. Instead of one ball, put N equally spaced pointers on the wheel and spin once. The number of copies an individual receives is then within one of its expected value, so the selection is much more faithful.

Python Wheel versus SUS: how noisy are the copies?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both methods give the same average number of copies, but SUS deviates only about half as much from the expected count on each run. That is why many libraries use SUS whenever they select proportionally.

Weaknesses of proportional selection

Roulette selection has well-known problems:

  1. Negative fitness breaks it. Probabilities must be non-negative. Shift all values by the smallest, which then makes the worst individual impossible to select.
  2. Scale sensitivity. Adding a constant to every fitness changes the selection probabilities, though the problem itself is unchanged. With fitness 1000 to 1010, every individual has nearly the same slice, and there is almost no selection pressure.
  3. Dominant individual. Early in a run one super-fit individual can take a large slice and be copied everywhere, causing premature convergence.
  4. Pressure fades as the population converges. When all fitnesses are close, selection is almost uniform and progress stalls.
Python The scale problem

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The ranking is identical, yet the best individual's probability drops from 40 % to about 25 %, which is pure uniform random choice among four. Two cures exist: fitness scaling (subtract a baseline such as the population minimum, or use sigma scaling relative to the standard deviation) and switching to comparison-based selection, which only uses the order of fitness values. The next lessons cover tournament selection and rank selection.

flowchart LR
    A["Raw fitness"] --> B{"Scaling<br/>needed?"}
    B -- "negative or big offset" --> C["Shift or sigma-scale"]
    B -- "compare only" --> D["Use rank or<br/>tournament"]
    C --> E["Roulette or SUS"]

Proportional selection depends on the numeric values of fitness, so prepare them first or avoid it.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Four individuals have fitness 10, 30, 40 and 20. What is the probability that the third one is selected in one spin?

    Its share is 40 out of a total of 100, so p = 0.4.
  2. 2. What is the advantage of stochastic universal sampling over repeated roulette spins?

    With N equally spaced pointers each individual receives within one copy of its expected number, reducing the variance of the wheel.
  3. 3. Why does adding 1000 to every fitness value weaken roulette selection?

    Proportional selection uses ratios, so a large constant offset hides the differences between individuals.
  4. 4. Which of these is a known weakness of roulette wheel selection?

    A huge slice means one individual is copied many times, quickly reducing diversity (premature convergence).

Summary

  • Roulette wheel selection picks individuals with probability proportional to fitness.
  • Implement it with a cumulative sum and binary search (bisect).
  • Stochastic universal sampling uses one spin and equally spaced pointers for far lower variance.
  • Proportional selection fails with negative fitness and is sensitive to scale and to dominant individuals.
  • Scale fitness first, or switch to tournament or rank selection.

Next: Tournament Selection