“Stochastic universal sampling”的意思、由来-开放百科全书

词条 Stochastic universal sampling

释义

See also
References

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

SUS is a development of 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 and thus reduces the unfair nature of fitness-proportional selection methods.

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.

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)]]     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 Population[0..i] is the set of individuals with array-index 0 to (and including) i.

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

References

1. ^{{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 }}

1 : Genetic algorithms

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

See also

References