Genetické operace jsou procesy, při kterých vznikají (s výjimkou genetické operace reprodukce) noví jedinci. Mezi genetické operace se řadí reprodukce, křížení a mutace. Cílem každé z těchto operací je vytvoření nového potomka. [6]

2.7.1 Reprodukce

Při reprodukci je pomocí selekční metody vybrán jeden jedinec z populace a jeho kopie je vložena do nové populace. Reprodukce jako jediná z genetických operací vytváří přímou kopii jedince. [7]

2.7.2 Křížení

Další genetickou operací je křížení. Během této operace vznikají ze dvou vybraných jedinců (rodičů) noví potomci, kteří mají strukturu složenou z obou rodičů. Existuje několik typů křížení, přičemž nejčastěji používané jsou 3 typy křížení a to křížení podstromů, jednobodové křížení a arita-2 křížení. [7]

2.7.2.1 Křížení podstromů

U tohoto druhu křížení se nejprve vybere první rodič a dále se zvolí uzel, kde dojde ke křížení. Následně se vybere druhý rodič a také jeden uzel. Vybrané podstromy se v daných uzlech prohodí a vzniknou dva jedinci, kteří jsou následně vloženy do nové populace. [7]

Obr. 7.:Křížení podstromů

2.7.2.2 Jednobodové křížení

Dalším typem křížení je tzv. jednobodové křížení. Při tomto druhu křížení se určí části stromů, které jsou z topologického hlediska společné pro oba jedince. V této části se vybere uzel, který je tudíž společný pro oba jedince a tento uzel se stane bodem křížení. [7]

Obr. 8.:Jednobodové křížení

2.7.2.3 Arita-2 křížení

Posledním typem křížení je tzv. arita-2 křížení. Princip spočívá v náhodném výběru funkce, která má 2 argumenty. Jako první argument bude sloužit první rodič, druhým argumentem bude druhý rodič. [7]

2.7.3 Mutace

Genetická operace mutace pracuje pouze s jedním jedincem. Existuje mnoho typů mutací, nicméně nejčastěji používané jsou mutace podstromu, mutace podstromu se zachováním velikosti, bodová mutace, mutace konstanty, vyzvedávající mutace a smršťující mutace. [7]

2.7.3.1 Mutace podstromu

Nejvíce používaný druh mutace je tzv.mutace podstromu. Při této mutaci je náhodně vybraný podstrom nahrazen jiným náhodně vytvořeným stromem. [7]

Obr. 9.:Mutace podstromu

2.7.3.2 Mutace podstromu se zachováním velikosti

Mutace podstromu se zachováním velikosti nově vzniklého jedince je téměř totožná s předchozím typem mutace. Náhodně vybraný podstrom je nahrazen jiným náhodně vytvořeným podstromem, přičemž se koriguje jeho velikost. [7]

2.7.3.3 Bodová mutace

Dalším typem mutace je tzv. bodová mutace. Při této mutaci je náhodně vybraný uzel obsahující prvek z množiny funkcí nahrazen jiným prvkem z této množiny. [7]

Obr. 10.:Bodová mutace

2.7.3.4 Mutace konstanty

Při této mutaci dochází k tomu, že se náhodně změní hodnota konstanty jednoho z terminálů. [7]

2.7.3.5 Vyzvedávající mutace

Jiným typem mutace, který bývá používán je tzv. vyzvedávající mutace. Při této mutaci je náhodně vybraný podstrom nahrazen náhodně vybraným terminálem. Hlavním cílem této mutace je snížení velikosti určité větve stromu. Ve většině případů dochází ke snížení velikosti celého jedince. [7]

Obr. 11.:Vyzvedávající mutace

Obr. 11.:Vyzvedávající mutace

2.7.3.6 Smršťující mutace

Dalším typem mutace je tzv. smršťující mutace. Při této mutaci vzniká nový jedinec, který je kopií náhodně vybraného podstromu svého rodiče. [7]

Obr. 12.:Smršťující mutace

2.8 Bloat efekt

Z podstaty GP jakožto metody, která pracuje s jedinci proměnné délky a struktury, vyplívá, že může docházet k neúměrnému nárůstu velikosti zpracovávaných stromových struktur. Tento jev se nazývá bloat efekt (bobtnání). Bloat efekt se projevuje vzrůstem složitosti vyvíjených programů. Bloat efekt jde proti snaze získat efektivní řešení. Velikost nadbytečného kódu roste s počtem generací. [10], [11]

Bloat efektu lze zamezit omezením počtu uzlů nebo hloubky generovaných řešení. Jiným způsobem může být zavedení vícekriteriálního ohodnocení. [4], [5]

2.9 Parametry algoritmu genetického programování

Stejně jako jiné evoluční algoritmy, tak i algoritmus GP má několik řídících parametrů, jejichž nastavení významně ovlivňuje běh algoritmu a dosažený výsledek. Parametry mají vliv na rychlost běhu algoritmu a na kvalitu výsledného řešení. Parametry jsou:

• Generations (počet generací). Tento parametr určuje, po kolik generací algoritmus běží. Čím větší je počet generací, tím větší je i pravděpodobnost dosažení vyhovujícího výsledku.
• PopSize (velikost populace). PopSize značí počet jedinců v populaci. Velikost populace se stanovuje na základě složitosti řešeného problému. Čím větší je složitost problému, tím větší populace se volí.
• Depth (hloubka). Tento parametr značí maximální hloubku syntaktického stromu, kterým je reprezentován každý jedinec v počáteční populaci.
• Functions (množina funkcí). Tento parametr obsahuje funkce s jedním a více parametry, přičemž typy funkcí se volí v závislosti na řešeném problému
• Terminals (množina terminálů). Je to parametr obsahující proměnné, konstanty nebo funkce bez argumentů. Stejně jako u množiny funkcí, tak i zde se terminály volí v závislosti na řešeném problému
• FrMutace (frakce mutace). Parametr frakce mutace značí, kolik procent jedinců v nové generaci má vzniknout pomocí genetické operace mutace.
• FrKrizeni (frakce křížení). Parametr frakce křížení značí, kolik procent jedinců v nové generaci má vzniknout pomocí genetické operace křížení.
• FrReprodukce (frakce reprodukce). Parametr frakce reprodukce značí, kolik procent jedinců v nové generaci má vzniknout pomocí genetické operace reprodukce.

2.10 Využití

Genetického programování nachází uplatnění v mnoha odvětvích lidské a technické činnosti. Jako příklad lze uvést:[7]

• • symbolická regrese,
• • fitování a modelování dat
• • návrh elektrických obvodů,
• • zpracování obrazu a signálu,
• • predikce časových řad a ekonomických modelů,
• • řízení průmyslových procesů,
• • lékařství, biologie a bioinformatika,
• • umělá inteligence v počítačových hrách,
• • komprese obrazu, zvuku nebo dat,
• • fraktály a teorie chaosu

Za zmínku stojí, že pomocí GP byly navrženy např. elektrické obvody pro časově optimální řízení robota, PID a PID-D2 regulátory, třídící sítě, elektronický teploměr, dolno-propustný filtr, anténa vyvíjená pro NASA nebo kompresní algoritmy. Dále se GP často používá pro návrh optimální struktury neuronových sítí. [7]

Poslednú časť s overením genetického programovania v praxi uverejníme opäť o týždeň.