[CZ] Popis knihovny v Javě
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.*
asgaLog.objective_stats
- jakofitness.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 souboremresources/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.