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

Селекция на принципа на рулетката (на английски: roulette wheel selection, RWS) е термин от областта на генетичните алгоритми, с който се означава най-простата разновидност на генетичния оператор селекция. При оператора селекция от популацията от „геноми“ (решения) се избират целесъобразно подбран брой отделни индивиди, над които след селекцията да се приложи операторът кръстосване (рекомбинация, кросоувър). Представлява техника за избор, основана на аналогията с въртенето на рулетка, която спира на един определен „показалец“ и избира съответстващата срещу „показалеца“ стойност на поле от рулетката. Други термини за този вид селекция, срещани в литературата, са стохастично семплиране (stochastic sampling)^[1] и пропорционална на фитнеса селекция (fitness proportionate selection, FPS).

Алгоритъм

Селекцията на принципа на рулетката следва следния алгоритъм:

1. Фитнес функцията на всеки индивид (геном, решение) от текущата популация се оценява. Съвкупността от всички стойности на фитнес функцията за индивидите, се нормализира. (Нормализацията означава всяка отделна фитнес стойност на индивид да се раздели на сбора от стойностите на всички индивиди, така че нормализиран този сбор се приравнява на 1, а всяка от отделните фитнес стойности се нормализира до число в интервала [0, 1].)
2. Популацията от индивиди се сортира по намаляващ ред на техните фитнес стойности (т.е. се въвежда линейна наредба между индивидите).
3. Изчисляват се акумулираните нормализирани фитнес стойности по формулата ${\displaystyle p_{i}={\frac {f_{i}}{\Sigma _{j=1}^{N}f_{j}}}}$, където с ${\displaystyle f_{i}}$ е означена стойността на фитнес функцията на ${\displaystyle i}$-тия индивид в популацията. Акумулираната фитнес стойност на индивид е сборът от неговата собствена фитнес стойност плюс фитнес стойностите на сортираните преди него индивиди, разделен на сбора от фитнес стойностите на всички индивиди в популацията; за последно сортирания индивид акумулираната фитнес стойност трябва да бъде точно 1. Акумулираната нормализирана фитнес стойност на индивида представлява математическата вероятност той да бъде селектиран на принципа на рулетката.
4. На случаен принцип се избират определен брой числа ${\displaystyle R_{1},...,R_{n}}$ между 0 и 1.
5. За всяко ${\displaystyle R_{i}}$ съответният селектиран индивид е първият, чиято акумулирана нормализирана фитнес функция е по-голяма от R.

Акумулирана нормализирана фитнес функция съответства на математическата вероятност за избор.^[1]

Обосновката за така конструираният алгоритъм е, че за индивидите с по-висока фитнес функция съществува по-голяма математическа вероятност да бъдат селектирани.

Пример

Нека е дадена популация от 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.0, 1.0]), например:

0.81, 0.32, 0.96, 0.01, 0.65, 0.42

Това означава, че селектираните за следващото поколение решения ще бъдат съответно:

8, 9, 2, 10, 11, 5

На фигурата графично е визуализиран резултатът от прилагане на селекция на принципа на рулетката.^[1]

Вижте също

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

Източници

1. Hartmut Pohlheim, "Evolutionary Algorithms: Overview, Methods and Operators. Documentation for GEATbx v. 3.7, Genetic and Evolutionary Algorithm Toolbox for Matlab, 2005