Evoluční výpočetní techniky
Selekce pomocí ruletového mechanismu (Roulette Wheel Selection)

| Úvod a cíle |

Zřejmě nejrozšířenější formou implementace přirozeného výběru je použití takzvaného ruletového mechanizmu selekce. Na rozdíl od klasické rulety, kde každé z čísel může být kvůli ekvivalentnímu obsahu předělených výsečí vybráno se stejnou pravděpodobností, v tomto případě budou favorizována kvalitnější jedinci (jedinci s vyšším ohodnocením). Takovým jedincům je na ruletovém kole přiřazena větší výseč a existuje tedy větší pravděpodobnost, že se při hře kulička zastaví právě v jejich výseči. Slabší individua mají přiřazenu menší výseč, což je sice předem nevylučuje, ale pravděpodobnost, že se kulička zastaví v jim přiřazené výseči a dojde tak k vybrání příslušného individua, je menší. Existuje několik běžně používaných způsobů, jak "upřednostňující" ruletové kolo zkonstruovat.

Liší se zejména ve způsobu určování velikosti výsečí pro jednotlivá individua. Velmi rozšířený je tzv. ruletový mechanizmus selekce s pravděpodobností výběru individua přímo úměrnou jeho ohodnocení (tzv. Fitness Proportionate Selection, kde - jak již název napovídá - má každé individuum přiřazenou výseč, jejíž plocha je přímo úměrná ohodnocení tohoto individua.

K vytvoření takového ruletového kola stačí sečíst ohodnocení všech členů populace a potom přiřadit každému jedinci proporcionálně odpovídající kruhovou výseč.

Nechť uvažovaný seznam (populace transformovaná na seznamu - záleží na pořadí jedinců) obsahuje jedinců kde ohodnocující funkce . Pravděpodobnost, s jakou bude -tý jedinec vybrán (a odpovídající velikost kruhové výseče), je dána následujícím vztahem:

kde:

• … Pravděpodobnost výběru -tého jedince do dalšího kola algoritmu.

• … Funkce, která poskytuje jako výstup hodnotu fitness zkoumaného -tého jedince .

• … Velikost vstupní populace jedinců - .

• … Součet hodnot fitness všech jedinců v populaci.

Uvedený vztah je transformací vztahu pravděpodobnosti výběru -tého jedince v populaci definovaného v předchozím studijním článku. Vztah upřednostňuje jedince s vyššími hodnotami fitness - jedná se tedy o maximalizaci přiřazovací funkce .

Následující tabulka (viz ) ilustruje podstatu ruletového mechanismu - maximalizace fitness funkce .

V kontextu vysvětlovaných evolučních algoritmů se jedná o minimalizaci přiřazovací funkce poskytující hodnoty fitness. Znamená to tedy, že vyšší hodnota fitness v případě minimalizace značí nevhodného jedince, zatímco menší hodnota fitness značí užitečnost jedince. Kromě toho, fitness hodnoty jsou normalizovány do rozmezí , protože selekce přímo úměrná fitness jinak zachází s hodnotami fitness, jako jsou např. a jinak s hodnotami . Whitley [24] definoval vztah, který určuje jak při výpočtu ruletového mechanismu v tomto případě postupovat: [6]

> kde:

• … Hodnota minima funkce fitness ze všech jedinců v populaci .

• … Funkce, která poskytuje hodnotu fitness jedince s nejmenší hodnotou fitness z celé populace. Rozdíl oproti globálnímu minimu je, že populace může obsahovat více stejných globálních minim.

• … Hodnota maxima funkce fitness ze všech jedinců v populaci.

• … Funkce, která poskytuje hodnotu fitness jedince s nejvyšší hodnotou fitness z celé populace. Rozdíl oproti globálnímu maximu je, že populace může obsahovat více stejných globálních maxim.

• … Populace, ve kterém je uloženo jedinců.

• … Pravděpodobnost výběru -tého jedince z do dalšího kola algoritmu - do populace určené pro páření (reprodukci).

Jako příklad ruletové selekce pomocí norem pro případ minimalizace využijeme stejných hodnot fitness. V tabulce jsou uvedeny vypočtené hodnoty (viz ). Hodnoty v tabulce jsou zobrazeny ve výsečovém grafu (viz ).