Prírodou inšpirované algoritmy

Selekcia

Selekcia

Táto časť GA zabezpečuje výber jedincov z populácie, ktorí sa budú reprodukovať (výber rodičov).

V tejto etape činnosti EA sa realizuje výber jedincov z populácie, ktorí sa budú reprodukovať (výber rodičov). V prípade mäkkej selekcie (soft selection) má každý jedinec istú šancu stať sa rodičom. Šanca na reprodukciu je v prírode závislá od konkrétnej situácie (komplexu vlastností), pričom evolúcia nie je účelovo smerovaná. Pri návrhu EA sa však požaduje, aby evolúcia jedincov danej populácie išla konkrétnym smerom v záujme nájdenia hľadaného riešenia - zabezpečenie selekčného tlaku. Preto je šanca na reprodukciu zviazaná s vhodnosťou jedinca: jedinci s nadpriemernou vhodnosťou by nemali mať menšiu šancu ako jedinci s podpriemernou vhodnosťou. V prípade tvrdej selekcie (hard selection) majú dokonca šancu iba jedinci s nadpriemernou vhodnosťou.

Existuje niekoľko skupín metód ako vybrať rodičov:

1. metódy založené na očakávaných hodnotách (ruletové metódy)

Názorne si to môžete predstaviť na príklade rulety, kde sa každému jedincovi priradí výsek veľkosti úmernej jeho relatívnemu ohodnoteniu. Pri každom roztočení rulety je vybratý ten jedinec, v ktorého výseku sa gulička zastaví. Toto opakujeme kým nieje vybratý dostatočný počet jedincov.



Ruletová selekcia

2. turnaje

Náhodne sa vyberie q jedincov z populácie, pričom q je parametrom turnaja (-árnosť turnaja). Porovnajú sa vhodnosti týchto q jedincov a ten s najväčšou vhodnosťou sa stáva rodičom. Na zvyšné miesta v skupine rodičov sú opätovne vypísané ďalšie turnaje, pričom jedinec, ktorý už bol vybraný za rodiča, naďalej ostáva v populácii jedincov.

3. náhodný výber

Rodičia sú vyberaní náhodne s rovnakou pravdepodobnosťov výberu, resp. pravdepodobnosť výberu môže byť daná aj nejakou funkciou.

4. orezávanie

Jedinci populácie sú zoradení podľa vhodnosti. Potom je takto zoradená populácia rozdelená na dve časti podľa daného parametra, pričom z jednej populácie nebudú jedinci vyberaní za rodičov a z druhej budú vyberaní buď náhodne s rovnakou pravdepodobnosťou, alebo sa deterministicky každý stáva rodičom.

Tieto metódy sú vzájomne previazané a je možné jednu metódu redukovať na iné. Niekedy je potrebné pred samotným výberom spraviť premapovanie hodnôt vhodností, teda ich úpravu.