Stochastic universal sampling

  Stochastic universal sampling (SUS) is a genetic operator used in genetic algorithms for selecting potentially useful solutions for recombination.

Additional recommended knowledge

Don't let static charges disrupt your weighing accuracy

Safe Weighing Range Ensures Accurate Results

Weighing the right way

First introduced into the literature by Baker^[1], 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. Described as an algorithm SUS looks something 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)
    order population by fitness
    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.

References

1. ^ 1

• James E. Baker. Reducing Bias and Inefficiency in the Selection Algorithm, in Proceedings of the Second International Conference on Genetic Algorithms and their Application (Hillsdale), pp. 14-21, 1987.