Uživatelské nástroje

Nástroje pro tento web


mrm:ea:eo

Evoluční operace

Rozeznáváme tři základní typy evolučních operací – mutaci, křížení a reprodukci. Při křížení a mutaci vzniká nový jedinec (nová varianta dat). V případě reprodukce se jedinec zkopíruje do nové populace, bez jakékoliv změny. Druh operace je volen náhodně na základě zadaných pravděpobností.

Mutací rozumíme změnu náhodně vybrané hodnoty na průsečíku řádku a sloupce datové matice, případně prohození dvou náhodně vybraných hodnot v jednom sloupci. Vzniká jeden nový jedinec. Křížením vznikají dva noví jedinci ze dvou rodičů a to náhodně zvoleným řezem buď ve smyslu řádků/záznamů (první X řádků od prvního rodiče, zbytek od druhého), nebo ve smyslu sloupců (prvních Y sloupců od prvního rodiče, zbytek od druhého). Šlechtění je speciální typ křížení, při kterém se vezme aktuálně nejlepší jedinec a několik náhodně vybraných řádků/záznamů se nahradí odpovídajícími řádky z jiného jedince. Druhým rodičem však může být pouze jedinec, který je aktuálně nejlepší variantou řešení pro některou z úloh DZD s požadavky na data.

Výběr rodičů

Jedinci mající právo na rozmnožování se vybírají systémem turnaje, a to pouze na základě setřídění jedinců podle fitness (nikoliv podle velikosti rozdílu jejich fitness). Je-li třeba získat rodiče, provede se náhodný výběr tolika jedinců z populace, kolik je zadáno v parametru Tournament Size. Z tohoto počtu náhodně vybraných jedinců se rodičem stane ten s nejlepší (nejnižší) hodnotou fitness. Čím je hodnota parametru Tournament Size vyšší, tím se snižuje pravděpodobnost, že šanci na rozmnožení dostane horší jedinec (ve velké skupině je větší pravděpodobnost, že tam bude i jedinec s lepší fitness a ten vyhraje turnaj). Vyšší hodnoty Tournament Size tak vedou ke snižování diverzity populace.

Přehled evolučních operací

Mutace

Mutací rozumíme změnu hodnot v náhodně vybraném sloupci datové matice. Jako rodič figuruje pouze jeden jedinec (vybraný turnajem) a vznikne opět jeden jedinec, ale s (drobně) pozměněnými hodnotami oproti svému rodiči.

K dispozici jsou tři typy mutací:

  • Prohození hodnot (angl. swap) – souvislá posloupnost hodnot počínaje záznamem na pozici n je prohozena se stejně dlouhou posloupností hodnot na pozici m ve stejném sloupci. Délka posloupnosti je zvolena jako náhodné číslo od 1 do hodnoty dané parametrem Swap Length Max. Přitom se hodnoty ve sloupci opět považují za „zatočené samy do sebe“ – po poslední hodnotě následuje opět první. Je zaručeno, že se obě posloupnosti nepřekrývají. Při vytváření jedince je možné provést prohození dvou úseků hodnot vícekrát. Počet prohození se určí náhodně v rozmezí 1 až hodnota parametru Swap Count Max. Délka prohazované sekvence zůstává stále stejná. Při opakovaném prohazování může dojít k překrytí některé dříve prohozené posloupnosti. Tento typ mutace je možné použít vždy.
  • Nahrazení hodnot (angl. fill) – souvislá posloupnost hodnot počínaje záznamem na pozici n a délce m je nastavena na náhodně zvolenou hodnotu (přitom se dodržuje povolený rozsah/výčet a rozdělení četností nastavené na záložce 3 Columns pro tento sloupec). Sloupec je opět zatočený sám do sebe. Délka posloupnosti je zvolena jako náhodné číslo od 1 do Fill Length Max. Při vytváření jedince je možné provést nastavení hodnoty vícekrát. Počet opakování se určí náhodně v rozmezí 1 až hodnota parametru Fill Count Max. Délka posloupnosti zůstává stále stejná. Při opakovaném vyplňování může dojít k překrytí některé dříve vyplněné posloupnosti. Tento typ mutace je možný pouze v případě, že není zaškrtnutá volba Distribution cannot change u daného sloupce C.
  • Změna hodnot (angl. modify) – na souvislou posloupnost hodnot počínaje záznamem na pozici n a délce m je aplikována operace přičtení/odečtení hodnoty zadané v dialogovém okně pro zadání charakteristik sloupce. Sloupec je opět zatočený sám do sebe. Délka posloupnosti je zvolena jako náhodné číslo od 1 do Modify Length Max. Při vytváření jedince je možné provést změnu hodnoty vícekrát. Počet opakování se určí náhodně v rozmezí 1 až hodnota parametru Modify Count Max. Délka posloupnosti zůstává stále stejná. Při opakovaném vyplňování může dojít k překrytí některé dříve vyplněné posloupnosti. Tento typ mutace je možný pouze v případě, že není zaškrtnutá volba Distribution cannot change u daného sloupce C.

Je-li možné použít pro sloupec C všechny typy mutace, volí se mezi nimi náhodně v poměru daném parametrem Swap Prob [%] (prohození hodnot), Modify Prob [%] (změna hodnot) a Fill Prob = (100 – Swap Prob- Change Prob) [%] (nahrazení hodnot).

Parametr Swap Length Max musí být menší nebo roven polovině počtu záznamů (Target DataRows). Parametr Modify Length Max a Fill Length Max musí být menší nebo roven počtu záznamů (Target DataRows).

Křížení

Pro křížení jsou zapotřebí dva rodiče (každý vybrán systémem turnaje – přitom je kontrolováno, že v obou případech nebyl vybrán stejný jedinec). Následně dojde k vlastnímu křížení, kterým vzniknou dva noví jedinci. Křížení je možné ve dvou směrech:

  1. Křížení ve smyslu sloupců – první nově vznikající jedinec převezme celý sloupec C od prvního rodiče a druhý vznikající jedinec tento sloupec převezme od rodiče druhého. Případně opačně – je voleno náhodně pro každý sloupec. Tento typ křížení je možné použít vždy.
  2. Křížení ve smyslu řádků/záznamů – první nově vzniklý jedinec bude mít jednu podmnožinu hodnot ve sloupci C od prvního rodiče a druhou od druhého rodiče; druhý jedinec naopak. Tento typ křížení je možný pouze v případě, že není zaškrnutá volba „Distribution cannot change“ u daného sloupce C. Pro výběr podmnožin hodnot od jednoho a druhé rodiče existují dvě možnosti:
    1. „Row Half and Half“ – Hodnoty se rozdělí na dvě poloviny počínaje n-tým záznamem. Hodnota n je zvolena náhodně v rozmezí 1 až počet_řádků_datové_matice a záznamy se považují za „zatočené samy do sebe“ – po posledním následuje opět první.
    2. „Row Random“ U každé hodnoty se náhodně volí (s pravděpodobností 50 %), jestli bude přiřazena prvnímu jedinci, nebo druhému.

Oba noví jedinci vznikají postupně sloupec po sloupci, jak byly sloupce nadefinovány na záložce 3 Columns. Pro každý sloupec se nejprve zjistí, jestli je vůbec možné vybírat z obou typů křížení – podle nastavení volby „Distribution cannot change“. Je-li zaškrtnutá, může se použít pouze křížení typu ad a). Není-li volba pro sloupec C zaškrtnutá, volí se mezi oběma typy křížení náhodně v poměru daném parametrem Cross Col Prob [%] (pro křížení ve smyslu sloupců) a Cross Row Prob = (100 - Cross Col Prob) [%] pro křížení ve smyslu řádků.

Je-li zvoleno křížení ve smyslu řádků, volí se opět náhodně typ rozdělení (Half  Random) a to v poměru podle parametru Cross Row Random Prob [%] (pro náhodné rozdělení mezi jedince) a Cross Row Half Prob [%] (pro rozdělení na dvě části).

V případě křížení „Row Half and Half“ se ukázalo, že není vhodné používat hodnotu n (počáteční záznam) stejnou pro všechny sloupce pro právě vznikající dva nové jedince. Hodnota n je proto volena náhodně pro každý sloupec zvlášť. Pro náhodné rozdělení („Row Random“) je však použit stejný předpis pro všechny sloupce, aby se do právě vznikajících nových jedinců měly šanci přenést případně existující vztahy mezi hodnotami ve více sloupcích.

Šlechtění (Breeding)

Jde o speciální typ křížení. Smyslem této operace je zanést do aktuálně nejlepšího jedince malou část z jedince, který představuje aktuálně nejlepší řešení jedné z dílčích úloh.

Jako první rodič vystupuje vždy aktuálně nejlepší jedinec. Druhý rodič se pak vybírá pouze z jedinců, kteří představují momentálně nejlepší řešení pro jednu dílčí úlohu. Nový jedinec se vytvoří jako klon prvního rodiče. Následně se z druhého rodiče vybere náhodný počet řádků (až do hodnoty parametru Breed Copy Length Max) a hodnoty ze všech sloupců se zkopírují do nového jedince. Kopírování náhodně zvoleného úseku řádků může být opakováno vícekrát (až do hodnoty parametru Breed Copy Count Max).

V případě, že druhým rodičem je jedinec představující výsledky dřívější evoluce (Data Preset), tak se do výsledného jedince kopírují pouze sloupce, jejichž hodnoty byly skutečně generovány (byly součástí evoluce v odkazovaném RM případu). To zajistí, že se v aktuální evoluci neovlivní hodnoty v ostatních sloupcích, které jsou zde navíc.

Reprodukce

Jedinec vybraný turnajem je bez jakékoliv změny zkopírován do nové populace. Procento takto kopírovaných jedinců je dáno jako doplněk do 100 % po součtu procentní pravděpodobnosti křížení a procentní pravděpodobnosti mutace.

Do nové populace je vždy reprodukován aktuálně nejlepší jedinec.

mrm/ea/eo.txt · Poslední úprava: 2015/10/13 15:27 (upraveno mimo DokuWiki)