Prírodou inšpirované algoritmy

Udržiavanie rôznosti

Udržiavanie rôznosti

Pri prehľadávaní priestoru riešení genetickým algoritmom po určitom čase sa populácia jedincov sústredí do nejakej menšej oblasti s relatívne vysokou vhodnosťou, pritom sa však v tejto oblasti nemusí nachádzať hľadaný extrém. Teda populácia skonvergovala ešte pred nájdením riešenia, čo nazývame predčasnou konvergenciou. Problém je v tom, že zvyšný genetický materiál nemusí obsahovať všetky stavebné prvky riešenia. Proti tomuto nežiadúcemu zredukovaniu genetického materiálu je možné bojovať udržiavaním rôznosti v populácii, a to niekoľkými metódami:

• Jedným z najjednoduchších spôsobov je šachovanie s veľkosťou populácie, čo je založené na tom, že pri väčšom počte jedincov populácie by malo chvíľu dlhšie trvať kým to skonverguje.
• Boj proti príčinám predčasnej konvergencie. Základným faktorom, ktorý konvergenciu ovplyvňuje je selekčný tlak. Čím väčší selekčný tlak, tým skôr populácia skonverguje. Selekčný tlak možno znížiť napr. zmenou parametrov selekcie resp. výberom inej selekčnej metódy, alebo zvýšením disjunkčného potenciálu genetických operátorov (napr. nastavením vysokej pravdepodobnosti mutácie).
• Genetická infúzia. Jej cieľom je dodávať nový genetický materiál, čo možno zabezpečiť napr. odstraňovaním duplikácií, reinicializáciou prípadne nastavením vysokej pravdepodobnosti mutácie tzv. hypermutáciou v určitých momentoch. Nejakými prostriedkami udržiavať v populácii prítomnosť subpopulácií s rôznym genetickým materiálom. Keďže každá populácia je primárnym nositeľom určitého genetického materiálu, pokiaľ tam existujú subpopulácie, tak tam je aj daný genetický materiál. Takýmito prostriedkami môžu byť obmedzené párenie len jedincov tej istej subpopulácie (analógia s prírodou, kde je fyzicky nemožné párenie medzi druhmi) alebo obmedzená súťaž pri náhrade, kde potomok nahrádza najpodobnejšieho jedinca z určitej skupiny jedincov (podobné jedince vypĺňajú ten istý priestor a teda musia súperiť o zdroje).
• Snaha rovnomerne rozvrstvovať jedince v priestore, pričom sa vychádza z obmedzenosti zdrojov a ich zdieľania v určitej časti priestoru (sharing). Z nedostatkového priestoru jedince migrujú do priestoru s relatívne väčším dostatkom, čo je zabezpečené tým, že jedincom trpiacim nedostatkom sa umelo znižuje vhodnosť. Tým ich pravdepodobnosť selekcie za rodičov bude menšia a teda budú mať menej potomkov, čím sa počet jedincov v danej časti priestoru v ďalšej generácii bude znižovať.