Stochastic universal sampling
Encyclopedia
Stochastic universal sampling (SUS) is a technique used in genetic algorithm
s 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. 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.
Genetic algorithm
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
s for selecting potentially useful solutions for recombination. It was introduced by James Baker.
SUS is a development of fitness proportionate selection
Fitness proportionate selection
Fitness proportionate selection, also known as roulette-wheel selection, is a genetic operator used in genetic algorithms for selecting potentially useful solutions for recombination....
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, 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.