12. Neuroevoluce a přírodou inspirovaná optimalizace

Definice¶

Neuroevoluce používá evoluční algoritmy k generování neuronových sítí. Jedná se o poměrně složitý problém, jelikož optimalizace neuronové sítě kombinuje spojitý (váhy) a diskrétní (topologie) prostor. Také je problém v tom, že síť může mít hodně ekvivaletních stavů, které jsou ale stejně zakódované, takže tyto symetrie je třeba vyřešit, aby nebyl stavový prostor moc obrovský.

Otázky¶

GNARL¶

Ma dve mutace
- Parametricka - váhy mutucí gaussovským šumem
- Strukturální - přidávání a odebírání neuronů a spojů

Princip SANE?¶

SANE¶

Využíval princip koevoluce, kde se v jedné populaci šlechtí váhy, v další neurony, a jsou spojeny přes společnou fitness funkci.
Neurony se vyvíjejí jakožto váhy spojů vstupujících do neuronu. Fitness se počítá jako fitness 5 nejlepších sítí, ve kterých se ten neuron objevil.
Blueprint se vyvíjí formou spojování neuronů do sítě. Fitness se počítá jako fitness celé sítě.
Postupně se SANE vylepšoval, že se třeba přidávaly restrikce na topologii (např. aby byly jen dopředné sítě) nebo aby se přepoužívaly určité komponenty, ale v základu je důlěžité, že byly dvě populace v koevoluci.

Jak funguje mutace a křížení v NEAT?¶

NEAT (NeuroEvolution of Augmenting Topologies)¶

Využívá komplexifikace, kde se začíná z malých topologií (fully connected feedforward síť bez skrytých vrstev), které se evolucí postupně komplikují a propojují.
Jelikož se přidávají neurony a spoje, tak je délka genomu proměnlivá.
Ma dve mutace
- Parametricka - váhy mutucí gaussovským šumem
- Strukturální - přidávání a odebírání neuronů a spojů
Chromozom je objekt, který má v sobě neurony (mají info jestli jsou vstupy/výstupy/ve skryté vrstvě) a spoje (odkud kam, váha, enabled/disabled).
Mutace
- Přidáme spoj mezi dva nespojené neurony.
- Rozpojíme spoj a přidáme tam neuron, který bude dva původní sousedy propojovat. Takto nejméně poškodíme aktuální topologii, jinak by se celá dosavadní práce rozbila. Link původních dvou bude DISABLED, takže ponecháváme informaci o tom, že tam jednou spoj byl, ale ukázalo se jako lepší je rozpojit.
Při tvorbě nových genů (při mutaci) se změna označuje inovačním číslem, které značí jakési pořadí genetických změn (counter se zvyšuje při nové generaci). Pokud při křížení dvou sítí narazíme na geny se stejným inovačním číslem, můžeme předpokládat, že byly změněny ve stejné generaci a plní tedy podobnou funkci.
Křížení
- Seřadíme si genotypy rodičů podle inovačních čísel a postupně slučujeme do potomka. Pokud mají stejný gen v daném čase, tak ho zkopírujem, pokud se liší, tak se můžem rozhodnout od kterého rodiče gen převzít. Pokud má jeden rodič víc genů protože je třeba starší, tak ty také můžeme přidat a zkopírovat.
- Tím vznikne strukturálně komplexnější potomek.

Proč se v NEAT používá niching a jak funguje?¶

Niching - "druhy"
V populace máme spoustu sítí různých velikostí a ty menší se pochopitelně učí rychleji. Přidáním nového genu většinou dočasně snížíme fitness, ale kdybychom pořád brali jen vyšší fitness, tak nebudeme zvětšovat sítě a hledat komplexnější topologie.
Proto se používá niching, kde máme populaci rozdělenou na druhy, přičemž sítě podobných vlastností (patřící do jednoho druhu) se vyvíjí odděleně od jiných druhů.
Výpočet podobnosti sítí přes nějakou vzdálenostní metriku (genotypická vzdálenost která započítává počty neuronů a vzdálenosti vah).
Pokud je jedinec dostatečně odlišný, tak se zařadí do nového niche a nechá se vyvíjet tam.
Používá se fitness sharing, kde fitness je vydělen počtem jedinců v daném nichi, takže je šance pro zajímavé slabší jedince se vyvinout. Také to zabraňuje přemnožení nějakých zrovna dobrých řešení.

Jaký je rozdíl u přímého a nepřímého kódování NS?¶

Přímé kódování (direct encoding) znamená, že všechny linky jsou reprezentovány dedikovaným genem.
- Toto není vhodná strategie pro velké NN, evoluční algoritmy nejsou dělané na miliony parametrů.
Nepřímé kódování (indirect encoding) optimalizuje nějaké DNA (předpis), ze kterého se síť pak postaví. Příkladem je celulární kódování, HyperNEAT, HyperGP,...
- Podobně jako v přírodě chceme, aby nepřímé kódování stavělo sítě, které mají nějaké symetrie (symetrická křídla hmyzu), nepravé symetrie (třeba velikosti plic se liší, nebo klepeta raků,...), regularitu (opakující se segmenty stonožky),...
- CPPN (Compositional Pattern Producing Network) funguje jako funkce, které se lze dotázat na hodnotu nějaké váhy a ona ji vygeneruje jakožto kompozici nějakých symetrických, periodických a jiných funkcí.

Jak se učí HyperNEAT?¶

HyperNEAT¶

NEAT není použít k vývinu samotné topologie sítě, ale k vývinu jejího nepřímého kódování stylem CPPN (tedy CPPN je nějaká síť, která přiřazuje neuronům váhy).
Neurony jsou rozmístěné v prostoru zvaném substrate, například nějaká rovina, ve které má každý neuron souřadnice (x, y). CPPN dostane na vstup tyto souřadnice a vypočte jejich váhu podle nějaké funkce. Substrát také definuje možnosti propojování neuronů, bývají povolené i rekurentní vztahy, minimální threshold pro aktivaci neuronu atd...
Lze škálovat substrate density, tedy hustotu toho systému souřadnic. Pokud máme neurony na nějakých pozicích, můžeme mezi ně vložit další souřadnice a zkoušet tak zvýšit rozlišení problému a přitom se zachovává funkce původní sítě.

Co je Novelty search a curiosity driven learning?¶

Novelty search¶

Pokud se evolucí chceme dostat k nějakýmu konkrétnímu výsledku, o kterém víme, jak vypadá, tak to bývá velmi obtížné.
- Například máme fitness funkci, která měří podobnost daného řešení k tomu co hledáme a ani tak nejsme schopni se tam dostat, protože prostor bývá plný lokálních minim a často je třeba jít zdánlivě velmi odlišnou cestou, abychom nakonec vyvinuli ono hledané řešení.
Novelty search je inspirován myšlenkou, že místo abychom hledali něco konkrétního co už známe, tak dáme šanci věcem zcela jiným, protože spousta kvalitních řešení se občas objeví omylem.
Každé individuum je při evoluci odměněno pokud objeví něco nového i pokud to třeba nenapomáhá přímo v zdokonalení fitness. Může se stát, že časem tento nový krok povede k výraznému zlepšení.
Curiosity driven learning funguje také na tomto principu, že agent v prostředí získává odměnu za to, že se dostane do bodu kde předtím nebyl.

Co je CMAES?¶

Covarience Matrix Adaptation Evolution Strategy (CMA-ES)¶

Strategie pro zlepsovani nuronovych siti
Strategie pro složitou numerickou nelineární nekonvexní black box optimalizaci.
Kombinuje vlastnosti evolučních algoritmů i gradientních technik, čímž dobře překonává lokální minima.

Rozdíly ACO a PSO?¶

Ant Colony Optimization (ACO)¶

Mravenci komunikují pomocí feromonů a algoritmus se toto snaží napodobit tím, že agenti nanášejí v prostoru tolik „feromonu“, jak dobré je současné řešení. Čím více feromonu je někde naneseno, tím více agentů tudy bude chodit.
Velmi často uvázne v lokálním minimu, takže často kombinováno s tabu searchem.
Často používáno pro hledání cest v grafech, kde nejvíce feromonu se na hrany nanáší když je daná cesta kratka.

Particle Swarm Optimization (PSO)¶

Částice jsou řešení problému, které mají nějaký rychlostní vektor udávající směr jejich pohybu.
Každý jedinec si pamatuje svoje lokální nejlepší řešení a snaží se k němu vrátit.
Zároveň si celé hejno pamatuje globální nejlepší řešení a všichni míří k tomuto řešení.
Lokální a globální optima se balancují pomocí parametrů (bez lokální inteligence by nebyla dostatečná explorace a bez globální inteligence by se rozletěly a nebyla by hejnová spolupráce) a postupně tak prohledávají prostor řešení.
Velmi záleží na počáteční rychlosti, protože pokud je moc malá tak se jedinec nestačí dostat na zajímavá řešení a pokud je moc velká, tak budou obrovské oscilace.