Neuroevoluce: evoluce vah i tvaru neuronových sítí a algoritmus NEAT

Neuron a síť v kostce, evoluce regulátoru pro kyvadlo na vozíku, proč evoluce místo gradientu, XOR a skryté neurony, NEAT s historickými značkami a speciací, co se stane bez speciace a následovníci od HyperNEAT po AmoebaNet.

15 minut Matěj Žalmánek 2026-10-15

Série Základy AI Díl 31 z 83

Celá osnova série 83 z 83 témat hotovo

Co si odnesete

Jak evoluce najde váhy sítě, když se o úspěchu dozvíme až na konci.
Proč na XOR nestačí ladit váhy a jak NEAT nechává síť růst od minima.
Proč NEAT bez speciace skoro nefunguje a kam neuroevoluce vede dnes.

Co se hodí znát předem: Genetické algoritmy: populace, křížení, mutace a výběr na batohu na výlet, Evoluční strategie a genetické programování: od pravidla jedné pětiny po Keplerův zákon

Neuronové sítě se dnes učí skoro výhradně gradientním sestupem: síť udělá chybu, spočítá se, kterým směrem pootočit každou váhu, a pootočí se. Co když ale chybu nejde derivovat — když se o úspěchu dozvíme až na konci hry, nebo když nevíme ani to, jak má síť vypadat? Pak přichází na řadu evoluce. Neuroevoluce nechává evoluční algoritmy pěstovat váhy sítí, a v nejzajímavější podobě i jejich tvar. Tímhle dílem končí modul o přírodou inspirovaných algoritmech a zároveň se otevírají dveře k neuronovým sítím.

Navazuje na díly Genetické algoritmy a Evoluční strategie a genetické programování.

1. Neuronová síť v kostce

Definice — umělý neuron a síť

Nechť n ∈ ℕ, n ≥ 1, w = (w₁, …, w_n) ∈ ℝⁿ jsou váhy, b ∈ ℝ je práh a σ : ℝ → ℝ je funkce, které říkáme aktivační funkce. Neuron s těmito parametry je funkce y : ℝⁿ → ℝ, která vstupům x = (x₁, …, x_n) přiřadí

y(x) = σ(w₁x₁ + … + w_nx_n + b) = σ(∑_i=1ⁿ w_ix_i + b).

Běžné aktivační funkce jsou sigmoida σ(z) = 1/1 + e^−z a skok σ(z) = 1 pro z > 0, σ(z) = 0 pro z ≤ 0.

Neuronová síť je orientovaný graf G = (V, E), kde

množina uzlů V = V_in ∪ V_N je disjunktní sjednocení vstupů sítě V_in a neuronů V_N, přičemž do vstupů nevede žádná hrana;
každá hrana (u, v) ∈ E vede do neuronu v ∈ V_N a má váhu w_uv ∈ ℝ;
každý neuron v ∈ V_N má práh b_v ∈ ℝ a aktivační funkci σ_v a jeho hodnota je y_v = σ_v(∑_{u : (u, v) ∈ E} w_uv y_u + b_v), kde y_u je pro vstup u ∈ V_in zadaná vstupní hodnota;
neprázdná množina V_out ⊆ V_N jsou výstupní neurony; jejich hodnoty jsou výstupem sítě.

Síť je dopředná, právě když graf G nemá orientovaný cyklus — pak lze hodnoty neuronů spočítat jednu po druhé v topologickém pořadí. Neurony z V_N ∖ V_out (nejsou vstupem ani výstupem) jsou skryté.

Laicky řečeno

Neuron sečte vstupy, každý vynásobený svou vahou, a podle součtu se „rozsvítí“, nebo ne. Váhy určují, na čem mu záleží. Síť je mnoho neuronů zapojených za sebou. Celé chování sítě je v číslech vah a v tom, kdo je s kým spojený — a obojí se dá pěstovat evolucí. Neuronovým sítím a jejich učení gradientem se v osnově věnuje celý samostatný modul.

y = σ( ∑_i=1ⁿ w_i x_i + b )

x_i: vstupy — to, co neuron „vidí“ (u kyvadla poloha, rychlost, úhel); neuron je nemění, jen s nimi počítá
w_i: váhy — jediné, co se učí nebo evolvuje; znaménko říká, jestli vstup neuron podporuje, nebo tlumí, velikost, jak moc na něm záleží
b: práh — posune rozhodovací hranici; bez něj by nulové vstupy daly vždy totéž σ(0) a hranice by musela procházet počátkem
σ: aktivační funkce — nelinearita; bez ní by i síť o mnoha vrstvách počítala jen lineární funkci, protože složení lineárních funkcí je zase lineární

Součet ∑ w_ix_i + b je vážené hlasování vstupů; σ z něj udělá výstup. Hranice mezi „rozsvítí se“ a „nerozsvítí“ je množina, kde je součet nula — přímka (v rovině), obecně nadrovina.

2. Evoluce vah: kyvadlo na vozíku

Klasická úloha řízení: na vozíku stojí tyč na kloubu a vozík ji musí udržet ve svislé poloze tím, že popojíždí vlevo a vpravo — jako když balancujete koště na dlani.

Definice — úloha kyvadla na vozíku

Stav je čtveřice s = (x, v, θ, ω) ∈ ℝ⁴: poloha x (m) a rychlost v (m/s) vozíku, úhel θ (rad) tyče od svislice a její úhlová rychlost ω (rad/s). Vozík má hmotnost 1 kg, tyč 0,1 kg a délku 1 m.
Akce: v každém kroku t = 0, 1, 2, … (krok trvá 0,02 s) zvolí regulátor sílu F_t ∈ {−10 N, +10 N}.
Přechod: s_t+1 se spočítá z s_t a F_t podle pohybových rovnic níže.
Konec pokusu: pokus skončí po kroku t, právě když |θ_t+1| > 12° ∨ |x_t+1| > 2,4 m (tyč spadla nebo vozík vyjel z koleje), nebo když proběhlo 1 000 kroků (20 s). Cílem je vydržet 1 000 kroků.

Regulátorem bude jediný neuron se skokovou aktivací: pro váhy (w₁, w₂, w₃, w₄, b) ∈ ℝ⁵ je

u(s) = w₁x + w₂v + w₃θ + w₄ω + b, F(s) = +10 N pro u(s) > 0, F(s) = −10 N pro u(s) ≤ 0.

Regulátor tedy tlačí vozík ve směru kladného x, právě když je vážený součet stavu kladný. Zdatnost regulátoru (průměrný počet kroků ze tří různých startů) definujeme níže.

Laicky řečeno

Pět čísel rozhoduje, kdy vozík cuknout doleva a kdy doprava. Žádný učitel neříká, jaká síla byla v kterém okamžiku správná — dozvíme se jen, jak dlouho tyč vydržela. Přesně taková situace se gradientem řeší těžko a evolucí snadno.

Definice — pohybové rovnice kyvadla na vozíku

Nechť s = (x, v, θ, ω) je stav (úhel θ měříme od svislice) a F ∈ {−10, +10} N síla regulátoru; kladná síla tlačí vozík ve směru kladného x. Konstanty: hmotnost vozíku m_v = 1 kg, hmotnost tyče m_t = 0,1 kg, jejich součet M = m_v + m_t = 1,1 kg, l = 0,5 m polovina délky tyče (vzdálenost těžiště od kloubu) a tíhové zrychlení g = 9,8 m/s². Bez tření (rovnice ve tvaru, jak je uvádí Barto, Sutton a Anderson, 1983, a jak je dodnes používá většina implementací) jsou pomocné zrychlení a_F, úhlové zrychlení tyče ε a zrychlení vozíku a dány předpisy

a_F = F + m_t l ω² sin θ/M

ε = g sin θ − cos θ · a_F/l (4/3 − m_t cos² θ/M)

a = a_F − m_t l ε cos θ/M

Simulace postupuje Eulerovou metodou s krokem Δt = 0,02 s: ze stavu s_t a síly F_t se spočítají a a ε a nový stav je

x_t+1 = x_t + Δt v_t, v_t+1 = v_t + Δt a, θ_t+1 = θ_t + Δt ω_t, ω_t+1 = ω_t + Δt ε,

tj. nová poloha je stará plus Δt krát stará rychlost a nová rychlost je stará plus Δt krát zrychlení.

ε = g sin θ − cos θ · a_F/l (4/3 − m_t cos² θ/M)

g sin θ: tíže — důvod, proč tyč padá: čím víc je nakloněná, tím silněji ji gravitace překlápí dál; ve svislé poloze je nulová, takže svislá poloha je rovnováha, jenže vratká
a_F: zrychlení vozíku od síly regulátoru (plus malá odstředivá síla tyče) — jediná cesta, kterou regulátor na tyč působí: vozík podjede pod tyč a kloub ji „postrčí“ zpátky
cos θ: jak velká část vodorovného postrčení tyč otáčí — u svislé tyče skoro všechno, u ležící nic; proto se tyč nakloněná o víc než pár stupňů zachraňuje těžko
l (4/3 − …): setrvačnost tyče — 4/3 pochází z momentu setrvačnosti homogenní tyče kolem konce, 1/3 m(2l)² = 4/3 ml²; odečtený člen opravuje to, že při otáčení tyče ucukne i vozík pod ní

Úhlové zrychlení tyče je souboj dvou členů: tíže tyč překlápí, zrychlení vozíku ji vrací.

Příklad — jeden krok simulace

Start (0, 0, 0,05, 0), tedy tyč nakloněná o 0,05 rad ≈ 2,9°; cos 0,05 ≈ 0,9988 a sin 0,05 ≈ 0,0500. Barvy podle rozboru vzorce pro ε výše. Jmenovatel: 0,5 · (4/3 − 0,1 · 0,9988²/1,1) ≈ 0,621.

bez síly (F = 0, tedy i a_F = 0): ε = 9,8 · 0,0500/0,621 ≈ +0,79 rad/s² — tyč začíná padat

síla +10 N: a_F = 10/1,1 ≈ 9,09 m/s², ε = 0,490 − 0,999 · 9,09/0,621 ≈ −13,8 rad/s²

po kroku: ω = 0 + 0,02 · (−13,8) ≈ −0,28 rad/s, v ≈ 0 + 0,02 · 9,72 ≈ 0,19 m/s

Síla ±10 N je proti tíži obrovská — jediné cuknutí převrátí směr pádu. Úloha tedy není v síle, ale v načasování: kdy přestat tlačit, aby se tyč nepřehoupla na druhou stranu.

Kolik dá náhoda? Z tisíce regulátorů s náhodnými vahami vydržel všech 20 sekund jediný; medián je 9 kroků — tyč spadne za necelou pětinu sekundy. Přímočarý regulátor, který jen jede tam, kam se tyč naklání, vydrží 39 kroků: tyč sice chytí, ale rozkmitá ji. Evoluční strategie (5, 20) z dílu o evolučních strategiích našla regulátor, který vydrží celých 20 sekund ze všech tří startů, v 15. generaci — po zhruba třech stech vyzkoušených regulátorech:

Kyvadlo na vozíku: prvních 8 sekund simulace

Vyvinutý regulátor dává největší váhu úhlové rychlosti — tyč nechytá, až když padá, ale už když se do pádu rozjíždí. Nezanedbatelné váhy má i úhel a rychlost vozíku, takže vozík nekmitá a nevyjede z koleje. Takové „pravidlo“ nikdo nenapsal; vypadlo z evoluce.

Definice — zdatnost regulátoru a evoluce vah

Nechť w = (w₁, …, w₄, b) ∈ ℝ⁵ jsou váhy regulátoru z úlohy kyvadla a s⁽¹⁾ = (0, 0, 0,05, 0), s⁽²⁾ = (0, 0, −0,08, 0), s⁽³⁾ = (0,5, 0, 0,02, 0,1) tři startovní stavy. Pro k ∈ {1, 2, 3} označme T_k(w) ∈ {1, …, 1 000} počet kroků, které pokus ze startu s^(k) s tímto regulátorem trvá (do pádu tyče či vyjetí vozíku, nejvýš 1 000). Zdatnost regulátoru je

Z(w) = T₁(w) + T₂(w) + T₃(w)/3 ∈ [1, 1 000].

Tři starty místo jednoho brání tomu, aby evoluce našla regulátor, který umí jen jednu výchozí polohu. Z je po částech konstantní — malá změna vah počet kroků většinou nezmění vůbec, takže gradient je skoro všude nula. Proto evoluce.

Evoluce vah evoluční strategií (5, 20) (viz díl Evoluční strategie a genetické programování): vstupem je funkce Z a počet generací G ∈ ℕ, výstupem nejlepší nalezené váhy.

Zvol 5 rodičů w⁽¹⁾, …, w⁽⁵⁾ ∈ ℝ⁵, každou jejich složku nezávisle a rovnoměrně z [−1, 1].
V každé generaci g = 1, …, G vytvoř 20 potomků: pro každého zvol rodiče w rovnoměrně náhodně z pěti a polož w′ = w + 0,5 · z, kde z ∈ ℝ⁵ má složky nezávislé se standardním normálním rozdělením N(0, 1) (viz díl Přehled pravděpodobnostních rozdělení).
Novými rodiči je 5 potomků s největší zdatností Z; staří rodiče do další generace nepostupují.
Po G generacích vrať váhy s největší zdatností, jaká se za běh objevila.

import random

def regulator(w, s):                 # s = (x, v, θ, ω)
    u = w[0]*s[0] + w[1]*s[1] + w[2]*s[2] + w[3]*s[3] + w[4]
    return 10 if u > 0 else -10       # skoková aktivace: síla ±10 N

def zdatnost(w):                     # simuluj(): kroky do pádu, nejvýš 1000
    return sum(simuluj(regulator, w, start) for start in STARTY) / 3

rodice = [[random.uniform(-1, 1) for _ in range(5)] for _ in range(5)]
for generace in range(30):
    deti = [[wi + 0.5 * random.gauss(0, 1) for wi in random.choice(rodice)]
            for _ in range(20)]
    deti.sort(key=zdatnost, reverse=True)
    rodice = deti[:5]                # (5, 20): přežijí jen potomci

Příklad — jak se vyvinutý regulátor rozhoduje

Váhy nalezené evolucí (zaokrouhleně): w = (0,05; 1,01; 1,37; 4,23), b = 0,09 pro (x, v, θ, ω). Barvy podle rozboru neuronu na začátku dílu: váhy, vstupy, práh.

tyč nakloněná, stojí: (0, 0, 0,05, 0) → u = 1,37 · 0,05 + 0,09 ≈ +0,16 → +10 N, vozík podjede pod tyč

tyč nakloněná, ale už se vrací: (0, 0, 0,05, −0,1) → u = 1,37 · 0,05 + 4,23 · (−0,1) + 0,09 ≈ 0,07 − 0,42 + 0,09 ≈ −0,26 → −10 N, vozík brzdí

Ve druhém případě je tyč nakloněná stejně, ale regulátor tlačí opačně: úhlová rychlost −0,1 rad/s váží s vahou 4,23 víc než úhel 0,05 rad s vahou 1,37. Tyč se vrací sama, a kdyby vozík dál tlačil, přehoupla by se. Přímočarý regulátor „jen podle úhlu“ by v obou stavech tlačil stejně — proto tyč rozkmitá.

3. Proč evoluce, a ne gradient

Řídká odměna. U kyvadla, hry nebo robota se kvalita pozná až po celé epizodě. Evoluci stačí jedno číslo na konci.
Nederivovatelné části. Skoková aktivace, simulátor fyziky, pravidla hry — evoluce je nemusí derivovat.
Paralelnost. Každého jedince lze ohodnotit na jiném počítači nezávisle.
Struktura. Gradient umí ladit váhy, ale ne přidat neuron. Evoluce může měnit i to, jak síť vypadá.

Nevýhodou je hladovost: místo jednoho gradientu, který řekne směr pro všechny váhy najednou, zkouší evoluce náhodné změny. Pro sítě s miliony vah bývá gradient mnohem úspornější, pokud ho vůbec jde spočítat.

4. Když nestačí váhy: XOR

Funkce XOR vrací 1, když je právě jeden ze dvou vstupů 1. Jak ukázal díl Logika a důkazy, jediný neuron ji neumí: jeho výstup dělí rovinu vstupů přímkou a body (0, 1), (1, 0) od (0, 0), (1, 1) žádná přímka neoddělí. Na XOR je potřeba aspoň jeden skrytý neuron. A tím se otevírá otázka, kterou samotná evoluce vah nevyřeší: kolik neuronů a jak je zapojit?

Věta — XOR není lineárně separabilní

Nechť XOR : {0, 1}² → {0, 1} je funkce daná předpisem XOR(x₁, x₂) = 1 ⇔ x₁ ≠ x₂. Pak neexistují čísla w₁, w₂, b ∈ ℝ taková, že pro všechna (x₁, x₂) ∈ {0, 1}² platí

w₁x₁ + w₂x₂ + b > 0 ⇔ XOR(x₁, x₂) = 1.

Žádná přímka tedy neoddělí body, kde je XOR roven 1, od bodů, kde je roven 0.

Důkaz. Kdyby taková čísla existovala, platilo by

(0, 0): b ≤ 0 (1, 1): w₁ + w₂ + b ≤ 0

(1, 0): w₁ + b > 0 (0, 1): w₂ + b > 0

Sečtením prvního řádku dostaneme w₁ + w₂ + 2b ≤ 0, sečtením druhého w₁ + w₂ + 2b > 0. Spor. ∎

Důkaz nepoužívá tvar aktivační funkce — platí pro každý jediný neuron, jehož výstup závisí jen na znaménku váženého součtu (skok i sigmoida s prahem 0,5).

Odpovídat se dá ručně — navrhnout architekturu a evolucí ladit jen váhy. Ale u složitějších úloh netušíme, jaká architektura je správná. Proč ji nenechat vyvinout taky?

5. NEAT: evoluce rostoucích sítí

Pokusy evolvovat strukturu sítí narážely na tři problémy. Jak křížit dvě sítě s jiným tvarem? Jak dát šanci nové struktuře, která je zpočátku horší, protože její nové váhy ještě nejsou vyladěné? A jak zabránit, aby sítě zbytečně bobtnaly? Kenneth Stanley a Risto Miikkulainen v roce 2002 odpověděli algoritmem NEAT (NeuroEvolution of Augmenting Topologies) se třemi myšlenkami.

Definice — genom NEAT a historické značky

Nechť uzly sítě (vstupy, práh, výstupy a skryté neurony, viz definici neuronové sítě výše) jsou označené přirozenými čísly. Gen spoje je pětice (u, v, w, e, i), kde u je zdrojový a v cílový uzel spoje u → v, w ∈ ℝ jeho váha, e ∈ {0, 1} příznak (e = 1: spoj je zapnutý a v síti se počítá, e = 0: vypnutý) a i ∈ ℕ jeho inovační číslo. Genom je konečná množina genů spojů, v níž mají různé geny různá inovační čísla; určuje síť, jejíž hrany jsou zapnuté spoje.

Inovační čísla přiděluje jeden čítač pro celou populaci: kdykoli mutace poprvé vytvoří spoj u → v, dostane další volné číslo; vznikne-li stejná strukturální změna (spoj mezi týmiž uzly) u jiného jedince, dostane číslo stejné.

Mutace genomu jsou tři:

změna vah — váhy w genů se změní (přičtením náhodného čísla nebo novou náhodnou hodnotou);
přidání spoje — přibude gen (u, v, w, 1, i) s náhodnou váhou w pro dva dosud nespojené uzly u, v (náš program přidá spoj, jen když nevznikne cyklus, takže síť zůstává dopředná);
přidání neuronu — pro zvolený zapnutý gen (a, b, w, 1, i) vznikne nový skrytý neuron h, gen se vypne (e ← 0) a přibudou geny (a, h, 1, 1, i′) a (h, b, w, 1, i″) s novými inovačními čísly.

Křížení dvou rodičů zarovná jejich geny podle inovačních čísel. Potomek dostane každý shodný gen (inovační číslo je v obou rodičích) od rodiče zvoleného náhodně se stejnou pravděpodobností a každý ostatní gen (je jen v jednom z rodičů) jen tehdy, je-li v genomu zdatnějšího rodiče.

Laicky řečeno

Inovační číslo je rodný list spoje. Když dvě sítě mají spoj s číslem 7, jde o „tentýž“ spoj, i když se k němu každá dostala jinou cestou — a při křížení se dají spárovat jako stejné geny u dvou rodičů. Nový neuron se vkládá tak, aby síť zpočátku počítala podobně jako předtím; nic zásadního se nerozbije, jen přibude možnost.

Příklad — přidání neuronu na spoj s vahou 2

Náš NEAT používá stejně jako původní článek strmější sigmoidu σ(z) = 1/1 + e^−4,9z. Spoj x₁ → y s vahou 2 přispíval do výstupu 2x₁. Po rozdělení vede x₁ → h s vahou 1 a h → y s vahou 2:

x₁ = 1: 2 · σ(1) = 2 · 0,993 ≈ 1,985 (předtím 2)

x₁ = 0: 2 · σ(0) = 2 · 0,5 = 1 (předtím 0)

„Podobně“ tu tedy znamená jen zčásti: pro vstup 1 je změna zanedbatelná, pro vstup 0 přibude do součtu jednička, protože sigmoida v nule vrací polovinu. Síť se tím trochu pokazí — a právě proto potřebuje nová struktura ochranu, o které je řeč dál.

Definice — speciace a sdílení zdatnosti

Nechť G₁, G₂ jsou neprázdné genomy (viz definici genomu výše) a I₁, I₂ množiny inovačních čísel jejich genů. Označme m = min(max I₁, max I₂) a

shodné geny: inovační čísla z I₁ ∩ I₂;
disjunktní geny: čísla i ∈ (I₁ ∖ I₂) ∪ (I₂ ∖ I₁) s i ≤ m (chybí jednomu z genomů „uprostřed“); D je jejich počet;
přebytečné geny: čísla i ∈ (I₁ ∖ I₂) ∪ (I₂ ∖ I₁) s i > m (za koncem kratšího genomu); E je jejich počet;
W̄ je průměr |w_i⁽¹⁾ − w_i⁽²⁾| přes shodné geny i (rozdíl vah téhož genu v obou genomech; nemají-li shodné geny, W̄ = 0);
N = max(|G₁|, |G₂|) je počet genů většího genomu, pokud je aspoň 20, jinak N = 1.

Pro konstanty c₁, c₂, c₃ ≥ 0 je kompatibilitní vzdálenost genomů G₁, G₂ číslo

δ(G₁, G₂) = c₁ E/N + c₂ D/N + c₃ W̄.

Speciace: nechť δ_t > 0 je práh a každý druh má zástupce. Genom patří do prvního druhu, s jehož zástupcem Z má δ(genom, Z) < δ_t; neexistuje-li takový, založí nový druh. Druhy S₁, …, S_K tak rozdělí populaci velikosti P na disjunktní neprázdné části.

Sdílení zdatnosti: má-li jedinec i ∈ S_k zdatnost f_i ≥ 0, je jeho sdílená zdatnost f′_i = f_i/|S_k|, druh k má F̄_k = ∑_{i ∈ S_k} f′_i (průměrnou zdatnost svých členů) a dostane

n_k = P · F̄_k/∑_j=1^K F̄_j

potomků (zaokrouhleno dolů, zbytek dostane druh s nejlepší sítí). Podobné genomy tedy tvoří druh, zdatnost jedince se dělí velikostí jeho druhu a potomci se rozdělují mezi druhy podle jejich průměrné zdatnosti.

Laicky řečeno

Sítě s podobnou stavbou soutěží hlavně mezi sebou, ne s celou populací. Nový neuron tak dostane pár generací na to, aby se jeho váhy vyladily, místo aby ho hned smetly zavedené sítě. A protože se zdatnost v druhu dělí, žádný druh nemůže ovládnout celou populaci.

δ = c₁ E/N + c₂ D/N + c₃ W̄

c₁ E: přebytečné geny — struktura, kterou jeden genom získal až po posledním společném „vynálezu“; znamená mladší, odlišnou větev vývoje
c₂ D: disjunktní geny — vynálezy z doby, kdy už oba existovali, které má jen jeden z nich; další míra rozdílu stavby
N: velikost většího genomu — aby dva velké genomy, které se liší o pár genů z mnoha, nevyšly stejně vzdálené jako dva malé, které se liší skoro ve všem; u genomů pod 20 genů se bere N = 1
c₃ W̄: průměrný rozdíl vah shodných genů — stejně zapojené sítě s velmi jinými vahami počítají jiné funkce; váha c₃ je menší, protože stavba se mění vzácněji a víc znamená

Konstanty c₁ = c₂ = 1, c₃ = 0,4 a práh δ_t = 3 jsou hodnoty, které pro XOR použili Stanley a Miikkulainen (2002); stejné má i náš program.

Příklad — vzdálenost po přidání neuronu

Genom A má geny 1–5. Genom B vznikl z podobného předka: má také geny 1–5 (gen 3 vypnutý, protože ho rozdělil nový neuron) a navíc geny 6 a 7 z přidání neuronu. Váhy shodných genů se liší o 0,2; 0,6; 0; 0,9 a 0,8.

shodné: 1–5 → W̄ = 0,2 + 0,6 + 0 + 0,9 + 0,8/5 = 0,5

přebytečné: 6, 7 (za koncem kratšího genomu, ten končí genem 5) → E = 2; disjunktní: žádné → D = 0; genomy mají pod 20 genů → N = 1

δ = 1 · 2/1 + 1 · 0/1 + 0,4 · 0,5 = 2,2 < 3 → stejný druh (barvy podle vzorce výše)

Kdyby B získal ještě jeden spoj (gen 8), vyšlo by E = 3 a δ = 3,2 ≥ 3 — B by založil nový druh. Jediný nový neuron tedy síť z druhu nevyřadí, ale nový neuron s novým spojem už ano.

n_k = P · F̄_k/∑_j F̄_j, F̄_k = ∑_{i ∈ S_k} f_i/|S_k|

n_k: počet potomků druhu k v další generaci — tím se v NEATu odměňuje úspěch, ne výběrem jednotlivců z celé populace
P: velikost populace (150) — potomci se dělí jako koláč, populace neroste ani nezmenšuje
|S_k|: počet členů druhu — sdílení zdatnosti: zdatnost každého člena se dělí velikostí jeho druhu, f′_i = f_i/|S_k|; velký druh tak nemůže získat víc jen tím, že je velký
F̄_k: součet sdílených zdatností druhu, tedy jeho průměrná zdatnost — o podílu na koláči rozhoduje kvalita, ne počet
∑_j F̄_j: součet přes všechny druhy — dělením vznikne podíl, který se sečte na 1, takže se rozdělí přesně P potomků (po zaokrouhlení dolů dostane zbytek nejlepší druh)

Příklad — proč sdílení chrání nový druh

Populace 150: zavedený druh A má 120 sítí s průměrnou zdatností 9,0, nový druh B se skrytým neuronem 30 sítí s průměrnou zdatností 7,5.

se sdílením (barvy podle vzorce výše): n_A = 150 · 9,0/16,5 ≈ 81,8 → 81 (+1 zbytek) = 82, n_B = 150 · 7,5/16,5 ≈ 68,2 → 68

bez sdílení (podle součtu zdatností 120 · 9,0 = 1 080 a 30 · 7,5 = 225): A ≈ 150 · 1 080/1 305 ≈ 124, B ≈ 26

Bez sdílení by nový druh za pár generací vymřel, protože je horší a menší. Se sdílením dostane víc potomků, než má členů, a má čas vyladit váhy.

Třetí myšlenka je nejjednodušší: začít od minima. Všechny sítě na začátku nemají žádný skrytý neuron — vstupy vedou rovnou do výstupu. Struktura přibývá jen tehdy, když se vyplatí. Výsledné sítě proto bývají malé.

Všechno dohromady — jedna generace našeho zjednodušeného NEATu (pravděpodobnosti jsou ty, se kterými běží program pro XOR):

populace ← 150 minimálních sítí (x₁, x₂ a práh rovnou do y, váhy náhodně z [−2, 2])
pro generaci g = 0, 1, …, 100:
    ohodnoť každou síť zdatností f
    pokud některá síť řeší úlohu: konec
    rozděl sítě do druhů: síť patří do prvního druhu, s jehož zástupcem má δ < 3,
                          jinak založí nový
    vyřaď druhy, které se 15 generací nezlepšily (kromě druhu s nejlepší sítí)
    druhu k přiděl n_k = 150 · F̄_k / ∑ F̄_j potomků
    v každém druhu:
        rodiče ← nejlepších 20 % členů
        má-li druh víc než 5 členů, jeho nejlepší síť přejde beze změny
        každý další potomek:
            s pravděpodobností 0,75 křížení dvou rodičů, jinak kopie jednoho
            s pravděpodobností 0,8 změň váhy (90 %: w ← w + N(0, 1), 10 %: nová náhodná)
            s pravděpodobností 0,1 přidej spoj
            s pravděpodobností 0,03 přidej neuron (rozděl náhodný zapnutý spoj)

6. NEAT na XOR

Náš zjednodušený NEAT má populaci 150 sítí a nejvýš 100 generací. V běhu z obrázku vyřešil XOR v generaci 27 sítí s jediným skrytým neuronem a sedmi spoji — což je nejmenší možné řešení:

f = ( 4 − ∑ |y − t| )²

∑ |y − t|: chyba — součet odchylek výstupu y od správné hodnoty t přes všechny čtyři vstupy; absolutní hodnota, aby se chyby nahoru a dolů nevyrušily
4: největší možná chyba (čtyři vstupy, každá odchylka nejvýš 1) — odečtením se z chyby, kterou chceme zmenšit, stane zdatnost, kterou evoluce zvětšuje, a ta je vždy nezáporná
²: umocnění — zesílí rozdíly blízko řešení: síť s chybou 0,5 má zdatnost 12,25, síť s chybou 1 jen 9, takže výběr víc odmění posledních pár procent

Zdatnost pro XOR podle původního článku NEAT (Stanley a Miikkulainen, 2002); nejvýš 16. Síť, která na všechno odpoví 0,5, má zdatnost (4 − 2)² = 4. Za řešení se síť počítá, když po zaokrouhlení výstupu odpoví správně na všechny čtyři vstupy.

Síť pro XOR, kterou vypěstoval NEAT; vpravo její výstupy

Síť se dá přečíst. Skrytý neuron h se rozsvítí jen tehdy, když jsou oba vstupy 0 (oba mají velkou zápornou váhu, práh je kladný). Přímé spoje do výstupu by samy počítaly „ne oba zároveň“ — výstup 1 pro všechno kromě (1, 1) —, ale silně záporná váha od h ho pro (0, 0) vypne. Výstupy 0,000; 0,855; 1,000 a 0,005 jsou po zaokrouhlení přesně XOR. Počet druhů mezitím vzrostl z jednoho na zhruba dvacet.

Příklad — výpočet sítě pro všechny čtyři vstupy

Váhy (zaokrouhleně): do h z x₁, x₂ a prahu −3,37; −3,67; 0,95; do y z x₁, x₂, prahu a h −1,42; −2,96; 3,32; −5,69. Aktivace je σ(z) = 1/1 + e^−4,9z. Nejdřív se spočítá h, pak y (tabulka počítá s nezaokrouhlenými vahami, takže ruční přepočet se může lišit v poslední cifře):

(`x`₁, `x`₂)	`z`_h	`h`	`z`_y	`y`	\|`y` − `t`\|
(0, 0)	0,95	0,990	3,32 − 5,69 · 0,990 = −2,32	0,000	0,000
(0, 1)	−2,72	0,000	−2,96 + 3,32 = 0,36	0,855	0,145
(1, 0)	−2,43	0,000	−1,42 + 3,32 = 1,89	1,000	0,000
(1, 1)	−6,09	0,000	−1,42 − 2,96 + 3,32 = −1,06	0,005	0,005

Chyba je 0,150 a zdatnost f = (4 − 0,150)² ≈ 14,82 z 16 (barvy podle vzorce zdatnosti výše). Nejhůř síť odpovídá pro (0, 1): výstup 0,855 je správně nad polovinou, ale ne u jedničky — na řešení to stačí, další ladění vah by zdatnost ještě zvedlo.

Z padesáti běhů s různými semínky vyřešil NEAT XOR ve 47, v průměru za 31 generací, s 2,6 skrytého neuronu, které opravdu něco dělají. Původní článek uvádí 32 generací a 2,35 skrytého neuronu — náš zjednodušený NEAT je tedy blízko.

7. Na čem NEAT stojí

Stejných 50 běhů s vypnutou částí algoritmu:

Varianta	Vyřešilo XOR	Průměrná generace
NEAT	47 z 50	31,1
bez speciace (jeden druh)	1 z 50	—
bez křížení	50 z 50	47,3

Bez speciace NEAT skoro nefunguje. Síť se skrytým neuronem je po vzniku horší než zavedené sítě bez něj, protože její nové váhy jsou náhodné — a v jedné společné soutěži ji výběr okamžitě vyřadí. Speciace ji ochrání, dokud nedozraje. Bez křížení se XOR vyřeší také, jen pomaleji a s většími sítěmi (3,1 aktivního skrytého neuronu): křížení pomáhá skládat dohromady dílčí objevy různých jedinců.

8. Následovníci NEATu

HyperNEAT (Stanley a kol., 2009) evolvuje malou síť, která teprve vygeneruje váhy velké sítě podle geometrie úlohy — jako genom, který nepopisuje každou buňku, ale pravidla růstu.
Hledání novosti (Lehman a Stanley, 2011) neodměňuje zdatnost, ale nové chování. V bludišti s klamavými slepými uličkami našlo cíl častěji než hledání řízené zdatností.
Hluboká neuroevoluce. V roce 2017 ukázal tým Uber AI, že prostý genetický algoritmus dokáže trénovat sítě s miliony vah na hrách Atari srovnatelně se zpětnovazebním učením.
Evoluční hledání architektur. Síť AmoebaNet (Google, 2019) vznikla evolucí stavebních bloků a v rozpoznávání obrázků na ImageNetu patřila v té době k nejlepším. Dnes architektury častěji navrhují lidé nebo jiné metody, ale evoluce zůstává jednou z možností.

9. Shrnutí

Neuroevoluce pěstuje neuronové sítě evolučními algoritmy — hodí se tam, kde gradient nejde spočítat nebo kde odměna přichází až na konci.
Evoluce vah jednoho neuronu udrží kyvadlo na vozíku 20 sekund po zhruba třech stech pokusech; náhodné váhy dají v mediánu 9 kroků.
Na XOR nestačí jeden neuron — je potřeba změnit strukturu sítě.
NEAT evolvuje váhy i strukturu: historické značky umožní křížení, speciace chrání nové struktury a sítě rostou od minima.
Bez speciace vyřešil NEAT XOR v 1 z 50 běhů, se speciací ve 47 — a nejlepší řešení mělo jediný skrytý neuron.

Chcete si to osahat? Nechte AI agenta napsat kyvadlo na vozíku s evolucí regulátoru a pak zkuste dvě tyče různé délky na jednom vozíku — slavnou těžší verzi, na které NEAT kdysi vynikal.

Máte na to jiný názor? Napište na support@coden-app.com.

Neuroevoluce: evoluce vah i tvaru neuronových sítí a algoritmus NEAT

1. Neuronová síť v kostce

2. Evoluce vah: kyvadlo na vozíku

3. Proč evoluce, a ne gradient

4. Když nestačí váhy: XOR

5. NEAT: evoluce rostoucích sítí

6. NEAT na XOR

7. Na čem NEAT stojí

8. Následovníci NEATu

9. Shrnutí

Agent na vašem počítači, ovládaný z telefonu