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

Стохастично универсално семплиране (на английски: Stochastic universal sampling, SUS) е термин от областта на генетичните алгоритми, с който се означава една от разновидностите на генетичния оператор селекция. Операторът служи от популацията от „геноми“ (решения) да се изберат определен брой потенциално полезни решения, над които да се приложи операторът кръстосване (рекомбинация, кросоувър). Техниката „стохастично универсално семплиране“ е предложена от Джеймс Бейкър.^[1]

Сравнение със селекцията на принципа на рулетката

За разлика от селекцията на принципа на рулетката (Roulette wheel selection, RWS), при която определен брой ${\displaystyle n}$ решения се избират от популацията чрез повтаряща се ${\displaystyle n}$ на брой пъти процедура, при стохастичното универсално семплиране се избира само една случайна стойност за решение, а останалите решения се получават от нея на равноотстоящи интервали с дължина ${\displaystyle 1/n}$. За разлика от селекцията на принципа на рулетката, която дава на индивидите с по-висока фитнес функция по-голяма математическа вероятност да бъдат избрани в следващото поколение на генетичния алгоритъм, при стохастичното универсално семплиране шанс да бъдат избрани имат и индивидите с по-ниски фитнес функции.^[2]

RWS може да даде лоши резултати, когато един или малко на брой индивиди от популацията регистрират много високи стойности на фитнес функцията в сравнение с останалите индивиди. Това означава тези индивиди да доминират в следващото поколение, тъй като по техниката RWS вероятността да бъдат избрани е много по-голяма от вероятността за другите индивиди. При SUS подобно на гребен, избраните за следващото поколение индивиди са равноотдалечени на интервал ${\displaystyle 1/n}$, което дава възможност в извадката да попаднат и индивиди с ниски стойности на фитнес функцията.

Пример

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

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

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

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]:

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.18	0.16	0.15	0.13	0.11	0.09	0.07	0.06	0.03	0.02	0.00

Нека по условие шест от общо единадесетте индивиди се селектират за кръстосване в следващото поколение. При техниката „стохастично универсално семплиране“ се избира една случайна стойност (нека това е стойността 0.42), а останалите се определят като равноотдалечени от нея на разстояние ${\displaystyle 1/6}$:

0.08, 0.25,0.42, 0.59, 0.76, 0.93

Съответстващите индивиди на тези стойности в съответствие с акумулираните им фитнес стойности са индивидите, които продължават за кръстосване в следващото поколение на генетичния алгоритъм:

8, 9,2,1, 11, 4

На фигурата графично е визуализиран резултатът от прилагане на стохастичното универсално семплиране.^[2]

Източници

1. Baker, James E. Reducing Bias and Inefficiency in the Selection Algorithm // Proceedings of the Second International Conference on Genetic Algorithms and their Application. Hillsdale, New Jersey, L. Erlbaum Associates, 1987. с. 14 – 21. Посетен на 1 ноември 2009.
2. Hartmut Pohlheim, "Evolutionary Algorithms: Overview, Methods and Operators. Documentation for GEATbx v. 3.7, Genetic and Evolutionary Algorithm Toolbox for Matlab, 2005