Stochastic universal sampling

File:Statistically Uniform.png

SUS example

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

First introduced into the literature by 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. 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

• 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.