Stochastic universal sampling

SUS example

Stochastic universal sampling (SUS) is a technique used in genetic algorithms for selecting potentially useful solutions for recombination. It was introduced by James Baker.

SUS is a development of fitness proportionate selection which exhibits no bias and minimal spread. Where fitness proportionate selection chooses several solutions from the population by repeated random sampling, SUS uses a single random value to sample all of the solutions by choosing them at evenly spaced intervals. This simply means that this gives a chance to bad members of the population (according to their fitness) to have a chance to be chosen and thus reduce the unfair nature of fitness-proportional selection methods. Other methods like roulette wheel can have bad performance when a member of the population has a really large fitness in comparison with other members. Using a comb-like ruler, SUS starts from a small random number, and choose next candidates from the rest of population remaining, not giving the fittest members to saturate the candidate space. Described as an algorithm, pseudocode for SUS looks like:

RWS(population, f)
    Ptr := 0
    for p in population
        if Ptr < f and Ptr + fitness of p > f
            return p
        Ptr := Ptr + fitness of p

SUS(population, N)
    F := total fitness of population
    Start := random number between 0 and F/N
    Ptrs := [Start + i*F/N | i in [0..N-1]]
    return [RWS(i) | i in Ptrs]

Here "RWS" describes the bulk of fitness proportionate selection (also known as "roulette wheel selection") - in true fitness proportional selection the parameter f is always a random number from 0 to F. The algorithm above is very inefficient both for fitness proportionate and stochastic universal sampling, and is intended to be illustrative rather than canonical.

See also

• Fitness proportionate selection
• Reward-based selection