Kurz

logo

Neuro-evoluce


Neuro-evoluce (NE - Neuro-Evolution) je pokročilá biologicky-inspirovaná technika spojující oblast evolučních přístupů a neuronových sítí. Ještě než se podíváme, jak taková NE vypadá, udělejme menší opakování základních pojmů. Následující schéma dává neuro-evoluci do kontextu předcházejících kurzů a pojmů.

přehled různých přítupů, jež zastřešují evoluční algoritmy

Obrázek: schéma evolučních algoritmů

Genetické algoritmy (GA)
Do této kategorie patří standardní geneticý algoritmus (SGA) pracující nad binárními řetězci (viz. kurz).
Genetické programování (GP)
Evoluční algoritmus pracující s bohatší reprezentací. Typickým příkladem je formule reprezentující logický výraz, matematickou funkci nebo jinou stromovou strukturu (např. program).
Evoluční strategie (ES)
Evoluční přístupy pracující nad vektory reálných čísel. Jako modifikační (perturbační) oparátor se zde používá pouze mutace (narozdíl od SGA).
Evoluční programování (EP)
Příbuzný přístup ke GP, zde pracujeme s reprezentací pomocí gramatik či automatů

Poslední zbývající součást EA je již zmíněná neuro-evoluce. Když si povšimneme, čím se jednotlivé oblasti evolučních algoritmů navzájem liší, hned nás napadne zvolená reprezentace (a s ní spojené operátory křížení/rekombinace a mutace). Neuro-evoluce není tedy nic jiného než evouční algoritmus šlechtící neuronovou síť. S trochou nadsázky by se dala tato kategorie přičlenit do předcházejících kategorií (dle zvoleného kódování), ale je natolik obsáhlá a specifická, že tvoří samostatnou oblast.

Podívejme se na tento přístup v širším kontextu. Neuronová síť sama o sobě slouží k úlohám regrese (modelování funkce závislé na proměnných) a klasifikace (modelování funkce oddělující různé třídy). Evoluční algoritmus je zase optimalizační přístup (optimalizace - hledání extrémů funkce). Jak tyto dvě metody zapadají do sebe? Co zde optimalizujeme? V kurzu o neuronových sítích jsme si řekli, že ke klasifikaci (a regresi taktéž) je zásadní nastavení vah jednotlivých propojení mezi neurony. Hledání vah u neuronové sítě říkáme učení neuronové sítě a jedná se právě o úlohu optimalizace - hledáme takové váhy, aby chyba klasifikace na trénovací sadě byla minimální. Z oblasti učení jsme zmínili dvě techniky - učení perceptronu a zpětnou propagaci (BP - Back Propagation). Proč tedy používat evoluční algoritmy?

ukázka hledání maxima na multimodální funkci

Obrázek: hledání maxima na multimodální funkci

Proč je EA lepší než BP?

Jak je vidět z obrázku multimodální funkce, zpětná propagace se snaží najít nejvyšší kopec (minimalizovat chybu = maximalizovat počet správných). Tato metoda postupuje tak, že krok po kroku se snaží slepě jít nahoru. Pokud se vydá na špatnou stranu (například kopec nalevo se zdá zpočátku prudší), může jednoduše skončit místo v bodu B (globální maximum) v bodu A (lokální extrém). Evoluční algoritmus často bývá efektivnější, protože používá celou populaci (rozmístěnou různě po krajině). Tedy když jeden jedinec skončí v lokálním extrému (A), jiní mu mohou dát vědět, že by měl hledat jinde.

Prozatím jsme si představili, k čemu je dobré použít evoluční algoritmus, podívejme se nyní na to, jak takový algoritmus sestavit. Základní kostra evolučního algoritmu zůstává pořád stejná. Co musíme definovat je hlavně přesný popis naší reprezentace a s ním spojené perturbační operátory (křížení, mutace).

  1. inicializace populace
  2. vyber rodiče z populace (dle určité strategie)
  3. vytvoř potomky pomocí operátoru křížení
  4. uprav potomky pomocí operátoru mutace
  5. zařaď potomky do populace (dle určité strategie)
  6. jdi na bod 2 dokud nenastace ukončovací podmínka (např. max. počet generací)

Jak můžeme naši neuronovou síť reprezentovat? První možností je každou váhu ( $w_{ij} \in \mathbb{R}$ ) zakódovat jako binární vektor na přesně daném místě chromozomu (gen) a použít SGA. Druhou variantou je rozšířit kódování a pracovat přímo s vektorem reálných čísel. Druhá reprezentace má hned nekolik výhod - předně, kódování je menší, přirozenější a lépe se pro něj definují perturbační operátory.

binární kódování vah neuronové sítě (ukázka na perceptronu)

Obrázek: binární kódování vah neuronové sítě (ukázka na perceptronu)

přímé kódování vah neuronové sítě (ukázka rozdílu oproti binární reprezentaci)

Obrázek: přímé kódování vah neuronové sítě (ukázka rozdílu oproti binární reprezentaci)

Zamysleme se nyní nad operátorem křížení. Dostáváme se zde do problému, kdy jedno řešení může být reprezentováno mnoha jedinci (genomy). Fitness funkce takovéto úlohy má typicky mnoho extrémů (reprezentujících jedno řešení) a křížení zde produkuje deformované jedince. Anglická terminoligie používá pro tento problém termín "competing conventions problem".

Základním algoritmem, který se s tímto problémem vypořádává je GNARL. Přístup je jednoduchý, zakážeme operátor křížení a budeme používat pouze mutaci (přístup podobný ES). Na začátku inicializujeme populaci náhodných sítí (dopředu dáme pouze počet vstupních a výstupních neuronů a neuronů ve skrytých vrstvách) a definujeme dva druhy mutace.

parametrická mutace
upravujeme hodnotu jednotivých vah pomocí tzv. Gaussovského šumu $g(x; \sigma) = \frac{1}{\sigma \sqrt{2\pi}} e^{-\frac{x^2}{2\sigma^2}}$ (malé změny s velkou pravděpodobnosí, velké s malou)
strukturální mutace
přidání/odebrání neuronu nebo propojení mezi neurony
náhodná iniciální neuronová síť pro algoritmus GNARL

Obrázek: náhodná iniciální neuronová síť pro algoritmus GNARL

Gaussovký šum (parametrická mutace)

Obrázek: Gaussovký šum (parametrická mutace)

Pokročilejším a dnes používaným přístupem je algoritmus NEAT. Tento algoritmus se liší od předešlého především tím, že inicializuje topologicky malé sítě a postupně je dle potřeby zvětšuje (komplexifikace). Z toho vyplývá, že jednotliví jedinci mohou mít rozdílně dlouhý genom. Algoritmus opět používá parametrickou a strukturální mutaci. Strukturální mutace ovšem v základní variantě pouze přidávává neurony a spoje, případně vypíná/aktivuje použité neurony. Navíc NEAT definuje operátor křížení nad dvěma rodiči, produkující jednoho potomka. K detailnímu popisu tohoto operátoru zde není prostor a odkéžeme zvídavého čtenáře k referencím na konci tohoto kurzu. Na závěr zmiňme další problém spojený s dynamickým obohacováním sítě, a totiž problém, kdy novou obohacenou síť trvá déle optimalizovat než menší. Nová síť má také často horší fitness. Na druhou stranu nové topologie jsou to, co od algoritmu očekáváme, tedy musí být v evoluci nějak chráněny. Právě k tomuto účelu se používá technika zvaná "niching" (bohužel je tato obsáhlá technika opět nad rámec naší diskuze).

iniciální neuronová síť pro algoritmus NEAT (tzv. minimální substrát)

Obrázek: iniciální neuronová síť pro algoritmus NEAT (tzv. minimální substrát)

ukázka komplexifikace neuronové sítě

Obrázek: ukázka komplexifikace neuronové sítě

Reference:

Test znalostí