# Stochastic universal sampling

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Stochastic_universal_sampling
> Markdown URL: https://mediated.wiki/source/Stochastic_universal_sampling.md
> Source: https://en.wikipedia.org/wiki/Stochastic_universal_sampling
> Source revision: 1328685138
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Data sampling technique used in genetic algorithm}}
thumb|270px|SUS example
'''Stochastic universal sampling''' ('''SUS''') is a selection technique used in [evolutionary algorithm](/source/evolutionary_algorithm)s for selecting potentially useful solutions for recombination. It was introduced by James Baker.<ref name="baker">
{{Cite journal | last = Baker | first = James E. | title = Reducing Bias and Inefficiency in the Selection Algorithm | journal = Proceedings of the Second International Conference on Genetic Algorithms and Their Application | pages = 14–21 | publisher = L. Erlbaum Associates | location = Hillsdale, New Jersey | year = 1987 }}</ref>

SUS is a development of [fitness proportionate selection](/source/fitness_proportionate_selection) (FPS) which exhibits no bias and minimal spread. Where FPS 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 gives weaker members of the population (according to their fitness) a chance to be chosen. 

FPS 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 chooses the next candidates from the rest of population remaining, not allowing the fittest members to saturate the candidate space.

== Pseudo Code==
Described as an algorithm, pseudocode for SUS looks like:

 SUS(''Population'', ''N'')
     ''F'' := total fitness of ''Population''
     ''N'' := number of offspring to keep
     ''P'' := distance between the pointers (''F''/''N'')
     ''Start'' := random number between 0 and ''P''
     ''Pointers'' := [''Start'' + ''i''*''P'' | ''i'' '''in''' [0..(''N''-1)<nowiki>]]</nowiki>
     '''return''' RWS(''Population'',''Pointers'')
 
 RWS(''Population'', ''Points'')
     ''Keep'' = []
     '''for''' ''P'' '''in''' ''Points''
         ''I'' := 0
         '''while''' fitness sum of ''Population''[0..''I''] < ''P''
             ''I''++
         add ''Population''[''I''] to ''Keep''
     '''return''' ''Keep''

Where <code>''Population''[''0''..''I'']</code> is the set of individuals with array-index 0 to (and including) {{mono|''I''}}.

Here RWS() describes the bulk of fitness proportionate selection (also known as "[roulette wheel selection](/source/roulette_wheel_selection)") – in true fitness proportional selection the parameter {{mono|''Points''}} is always a (sorted) list of random numbers from 0 to {{mono|''F''}}. The algorithm above is intended to be illustrative rather than canonical.

==See also==
*[Fitness proportionate selection](/source/Fitness_proportionate_selection)
*[Reward-based selection](/source/Reward-based_selection)

==References==
<references />

Category:Selection (evolutionary algorithm)

---
Adapted from the Wikipedia article [Stochastic universal sampling](https://en.wikipedia.org/wiki/Stochastic_universal_sampling) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Stochastic_universal_sampling?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.