Evoluční algoritmy I NAIL025

Začneme tím nejjednodušším. Jednoduchý genetický algoritmus (Simple Genetic Algorithm) je jeden z prvních evolučních 

algoritmů a díky tomu je i velmi jednoduchý. Jedinci v SGA jsou kódováni jako bitové řetězce. Provádí se ruletová selekce 
a jednoduché jednobodové křížení s mutací, která náhodně mění hodnoty některých bitů.

Jak algoritmus funguje jste si už říkali s Romanem na přednášce, my si dneska ukážeme, jak je algoritmus implementovaný a 
také toho využijeme k popisu “knihovny”, kterou budeme používat.

Fitness a účelová funkce

Evoluční algoritmy jsou většinou implementovány tak, aby maximalizovaly fitness funkci. Na druhou stranu pří řešení 
(nejen) reálných problémů potřebujeme naopak nějakou funkci/hodnotu minimalizovat. Z toho důvodu v naší knihovně můžete 
najít dvě různé hodnoty u každého jedince (evolution.individuals.Individual) - fitnessValue a objectiveValue. 
Fitness je ta hodnota, podle které se chová evoluční algoritmus a knihovna ji používá, objective je potom ta hodnota, 
která se skutečně optimalizuje. Dnes budou obě hodnoty stejné, ale uvidíte, že časem se budou lišit. Výhodou objective 
value je, že se dá snadno porovnávat nezávisle na různých změnách fitness (např. škálování).

Dnešní cíl je velmi jednoduchý, chceme vyvinout jedince, který bude mít ve svém kódování samé jedničky. Tento problém se 
nazývá OneMAX a často se využívá i při teoretickém studium evolučních algoritmů.

Kódování jedince

V jednoduchém genetickém algoritmu je kódování jedince jednoduché. Je to jen posloupnost bitů. V naší knihovně je takový 
jedinec implementován jako evolution.individuals.BooleanIndividual. Tato třída podporuje základní operace, které s 
jedincem potřebujeme dělat, tj. přístup na libovolnou pozici v jeho genomu a její změnu. Umí se také náhodně inicializovat.

Selekce

Předtím než se populace dostane k operátorům, je potřeba vybrat, kteří jedinci se budou moci rozmnožit. K tomu slouží 
selekce (mating selection). V případě jednoduchého genetického algoritmu se používá tzv. ruletová selekce. U této selekce 
je pravděpodobnost, že jedinec bude vybrán ke křížení úměrná jeho fitness, Na implementaci ruletové selekce se můžete 
podívat ve třídě evolution.selectors.RouletteWheelSelector.

Operátory

Operátory jsou opět jednoduché. Pro křížení slouží tzv. jednobodové křížení: vezmou se dva jedinci, náhodně se vybere 
index a potom se prohodí pozice za tímto indexem mezi oběma jedinci. Křížení je implementované ve třídě 
evolution.operators.OnePtXOver. Všimněte si zde, že metoda operate() dostává jako parametr celou populaci jedinců a 
kříží mezi sebou jedince, kteří jdou hned za sebou.

Operátor mutace je stejně jednoduchý. Stejně jako křížení prochází celou populaci a s určitou pravděpodobností 
(mutationProbability) zmutuje jedince. Pří mutaci konkrétního jedince ho potom prochází od začátku do konce a u každého 
bitu se rozhoduje, jestli změní jeho hodnotu. S pravděpodobností bitFlipProbability tuto změnu udělá.

V obou případech (křížení i mutace) se nově vytvoření jedinci přidávají do populace offspring.

Promíchání rodičů a potomků, selekce prostředím

V některých obecnějších algoritmech je ještě potřeba vyřešit, kteří rodiče mají šanci přežít do další generace (např. 
abychom neztratili nejlepší řešení). K tomu naše knihovna má replacement. V SGA je to jednoduché, přežívají jen potomci, 
takže replacement rodiče zahodí (viz evolution.SGAReplacement).

Někdy se také používá selekce prostředím (environmental selection). která se pouští po operátorech. Slouží např. k tomu, 
aby se velikost populace vrátila na původní hodnotu, pokud operátory mohou vytvořit více potomků. V knihovně se dá také 
nastavit, z hlediska implementace není rozdíl mezi selekcí prostředím a selekcí k rozmnožování.

Nastavení algoritmu

Všechny parametry algoritmu (velikost populace, pravděpodobnosti operátorů, délka jedince) se dají nastavit v souboru 
properties/ga-sga.properties.

Když se potom podíváte do souboru evolution.sga.Main, tak v metodě main najdete načtení těchto parametrů a opakované 
volání metody run(int n), která provádí samotný evoluční algoritmus podle zadaných parametrů. Číslo n zde udává číslo 
běhu a slouží také jako seed pro náhodný generátor.

Jedna generace

Nyní už máme pohromadě všechny součásti evolučního algoritmu a stačí je spustit. V naší knihovně na to máme třídu 
evolution.EvolutionaryAlgorithm a její metodu evolve(), která spouští jednu generaci.

Nejprve je potřeba algoritmus nakonfigurovat, na příklad konfigurace se můžete podívat ve třídě evolution.sga.Main v 
metodě run(). Najdete tam

//Create new population Population pop = new Population(); 
pop.setPopulationSize(popSize); 
pop.setSampleIndividual(new BooleanIndividual(dimension)); 
pop.createRandomInitialPopulation();

//Set the options for the evolutionary algorithm 
EvolutionaryAlgorithm ea = new EvolutionaryAlgorithm(); 
ea.setFitnessFunction(new ExampleFitnessFunction()); 
ea.addMatingSelector(new RouletteWheelSelector()); 
ea.addOperator(new OnePtXOver(xoverProb)); 
ea.addOperator(new BitFlipMutation(mutProb, mutProbPerBit));

První 4 řádky nastavují počáteční populaci, její velikost a nastavují vzorového jedince. Tento vzorový jedinec se potom 
naklonuje do celé populace a všichni jedinci se potom náhodně inicializují v metodě createRandomInitialPopulation(). 
Volá se přitom metoda randomInitialization() na každém jedinci.

Další řádky potom nastavují chování evolučního algoritmu. Nastavuje se fitness funkce, selekce před rozmnožováním, a 
operátory.

O pár řádek dál potom najdeme cyklus, ve kterém se volá opakovaně metoda ea.evolve(pop), ta přímo provádí jeden cyklus 
evoluce na zadané populaci. Můžete si ji prohlédnout ve třídě evolution.EvolutionaryAlgorithm.

A to je celé, máme funkční evoluční algoritmus. Sice popis trval dlouho, ale využijeme ho i u dalších cvičení, kde to 
bude podobné.

Výstupy

Když dnešní zdrojové kódy pustíte, uvidíte, že se stane několik věcí a na disku se vám objeví několik nových souborů v 
adresáři sga. Jména těchto souborů i adresáře se dají změnít v souboru properties/ga-sga.properties.

• soubory sgaLog.fitness.* - soubory s jednotlivými průběhy evolučního algoritmu, obsahují dva sloupečky, v prvním je 
  fitness nejlepšího jedince po generacích, ve druhém je průměrná fitness v populaci
• soubor sgaLog.fitness_stats.log - soubor se statistikami průběhů ze souborů fitness.log.*, obsahuje 6 sloupců, v 
  prvním je počet vyhodnocení fitness funkce, ve další je fitness nejlepšího jedince v dané generaci z nejhoršího průběhu, 
  ve třetím první kvartil fitness, v prostředním je průměrná fitness nejlepších jedinců ze všech průběhů, v předposledním 
  třetí kvartil a konečně v posledním je fitness nejlepšího jedince v nejlepším průběhu
• soubory sgaLog.objective.* a sgaLog.objective_stats - jako fitness.log, ale loguje přímo optimalizovanou hodnotu, 
  může se lišit od fitness (ne dnes)
• soubory sgaLog.details.*.xml.zip - obsahuje detaily jednotlivých běhů evolučního algoritmu, nejlépe je ho rozbalit a 
  zkopírovat do stejného adresáře se souborem resources/eva.xsl a otevřít v prohlížeči (pozor, ne Chrome, blokuje 
  spouštění lokálních xml+xsl)

Vyznat se v těchto souborech není snadné, ale pomůžou vám k tomu skripty pro generování grafů. Na to, jak se používají se podívejte do textu dostupného na hlavní stránce kurzu.