Преглед на кода на Стохастично универсално семплиране

'''Стохастично универсално семплиране''' ({{lang|en|Stochastic universal sampling, SUS}}) е термин от областта на [[генетични алгоритми|генетичните алгоритми]], с който се означава една от разновидностите на [[генетичен оператор|генетичния оператор]] [[селекция (генетичен оператор)|селекция]]. Операторът служи от популацията от „геноми“ (решения) да се изберат определен брой потенциално полезни решения, над които да се приложи операторът [[кръстосване (генетичен оператор)|кръстосване]] (рекомбинация, кросоувър). Техниката „стохастично универсално семплиране“ е предложена от Джеймс Бейкър.<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 | accessdate =1 ноември 2009}}</ref>

== Сравнение със селекцията на принципа на рулетката ==
За разлика от [[селекция на принципа на рулетката|селекцията на принципа на рулетката]] (''Roulette wheel selection, RWS''), при която определен брой <math>n</math> решения се избират от популацията чрез повтаряща се <math>n</math> на брой пъти процедура, при стохастичното универсално семплиране се избира само една [[случайна величина|случайна стойност]] за решение, а останалите решения се получават от нея на равноотстоящи интервали с дължина <math>1/n</math>. За разлика от селекцията на принципа на рулетката, която дава на индивидите с по-висока [[фитнес функция]] по-голяма [[математическа вероятност]] да бъдат избрани в следващото поколение на генетичния алгоритъм, при стохастичното универсално семплиране шанс да бъдат избрани имат и индивидите с по-ниски фитнес функции.<ref name="geatbx" />

RWS може да даде лоши резултати, когато един или малко на брой индивиди от популацията регистрират много високи стойности на фитнес функцията в сравнение с останалите индивиди. Това означава тези индивиди да доминират в следващото поколение, тъй като по техниката RWS вероятността да бъдат избрани е много по-голяма от вероятността за другите индивиди. При SUS подобно на [[Гребен (коса)|гребен]], избраните за следващото поколение индивиди са равноотдалечени на интервал <math>1/n</math>, което дава възможност в извадката да попаднат и индивиди с ниски стойности на фитнес функцията.

== Пример ==
Нека е дадена популация от 11 индивида със следните (нормализирани) стойности на фитнес функцията:

{| class="wikitable" width="100%"
|- style="color: blue"
! width="20%" | ID на индивид
| 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10|| 11
|-
! Фитнес стойност
|1.4||1.6||0.8||0.6||0.4||0.0||0.2||2.0||1.8||1.2||1.0
|}

Популацията се сортира по намаляващ ред на фитнес стойностите на индивидите:

{| class="wikitable" width="100%"
|- style="color: blue"
! width="20%" | ID на индивид
| 8 || 9 || 2 || 1 ||10 ||11 || 3 || 4 || 5 || 7 || 6
|-
! Фитнес стойност
|2.0||1.8||1.6||1.4||1.2||1.0||0.8||0.6||0.4||0.2||0.0
|}

Изчисляват се акумулираните фитнес стойности на индивидите, нормализирани в интервала [0.00, 1.00]:

{| class="wikitable" width="100%"
|- style="color: blue"
! width="20%" | ID на индивид
| 8 || 9 || 2 || 1 ||10 ||11 || 3 || 4 || 5 || 7 || 6
|-
! Фитнес стойност
|2.0||1.8||1.6||1.4||1.2||1.0||0.8||0.6||0.4||0.2||0.0
|-
! Акумулирана<br/>Фитнес стойност
|0.18||0.16||0.15||0.13||0.11||0.09||0.07||0.06||0.03||0.02||0.00
|}

Нека по условие шест от общо единадесетте индивиди се селектират за кръстосване в следващото поколение. При техниката „стохастично универсално семплиране“ се избира една случайна стойност (нека това е стойността <span style="color:#00B14F">0.42</span>), а останалите се определят като равноотдалечени от нея на разстояние <math>1/6</math>:
: <span style="color:red">0.08, 0.25,</span><span style="color:#00B14F">0.42, </span><span style="color:red"> 0.59, 0.76, 0.93</span>

Съответстващите индивиди на тези стойности в съответствие с акумулираните им фитнес стойности са индивидите, които продължават за кръстосване в следващото поколение на генетичния алгоритъм:
: <span style="color:red">8, 9,</span><span style="color:#00B14F">2,</span><span style="color:red">1, 11, 4</span>

На фигурата графично е визуализиран резултатът от прилагане на стохастичното универсално семплиране.<ref name="geatbx">Hartmut Pohlheim, "Evolutionary Algorithms: Overview, Methods and Operators. Documentation for GEATbx v. 3.7, Genetic and Evolutionary Algorithm Toolbox for Matlab, 2005</ref>

[[Файл:SUS-numerical-example.png|център|800px]]

== Източници ==
<references />

[[Категория:Генетични алгоритми]]