Neuroevolúcia: evolúcia váh aj tvaru neurónových sietí a algoritmus NEAT

Nech n ∈ ℕ, n ≥ 1, w = (w₁, …, w_n) ∈ ℝⁿ sú váhy, b ∈ ℝ je prah a σ : ℝ → ℝ je funkcia, ktorú nazývame aktivačná funkcia. Neurón s týmito parametrami je funkcia y : ℝⁿ → ℝ, ktorá vstupom x = (x₁, …, x_n) priradí

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

Bežné aktivačné funkcie sú sigmoida σ(z) = 1/1 + e^−z a skok σ(z) = 1 pre z > 0, σ(z) = 0 pre z ≤ 0.

Neurónová sieť je orientovaný graf G = (V, E), kde

1. množina uzlov V = V_in ∪ V_N je disjunktné zjednotenie vstupov siete V_in a neurónov V_N, pričom do vstupov nevedie žiadna hrana;
2. každá hrana (u, v) ∈ E vedie do neurónu v ∈ V_N a má váhu w_uv ∈ ℝ;
3. každý neurón v ∈ V_N má prah b_v ∈ ℝ a aktivačnú funkciu σ_v a jeho hodnota je y_v = σ_v(∑_{u : (u, v) ∈ E} w_uv y_u + b_v), kde y_u je pre vstup u ∈ V_in zadaná vstupná hodnota;
4. neprázdna množina V_out ⊆ V_N sú výstupné neuróny; ich hodnoty sú výstupom siete.

Sieť je dopredná práve vtedy, keď graf G nemá orientovaný cyklus — potom možno hodnoty neurónov vypočítať jednu po druhej v topologickom poradí. Neuróny z V_N ∖ V_out (nie sú vstupom ani výstupom) sú skryté.

1. Stav je štvorica s = (x, v, θ, ω) ∈ ℝ⁴: poloha x (m) a rýchlosť v (m/s) vozíka, uhol θ (rad) tyče od zvislice a jej uhlová rýchlosť ω (rad/s). Vozík má hmotnosť 1 kg, tyč 0,1 kg a dĺžku 1 m.
2. Akcia: v každom kroku t = 0, 1, 2, … (krok trvá 0,02 s) zvolí regulátor silu F_t ∈ {−10 N, +10 N}.
3. Prechod: s_t+1 sa vypočíta z s_t a F_t podľa pohybových rovníc nižšie.
4. Koniec pokusu: pokus skončí po kroku t práve vtedy, keď |θ_t+1| > 12° ∨ |x_t+1| > 2,4 m (tyč spadla alebo vozík vyšiel z koľajnice), alebo keď prebehlo 1 000 krokov (20 s). Cieľom je vydržať 1 000 krokov.

Regulátorom bude jediný neurón so skokovou aktiváciou: pre váhy (w₁, w₂, w₃, w₄, b) ∈ ℝ⁵ je

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

Regulátor teda tlačí vozík v smere kladného x práve vtedy, keď je vážený súčet stavu kladný. Zdatnosť regulátora (priemerný počet krokov z troch rôznych štartov) definujeme nižšie.

Nech s = (x, v, θ, ω) je stav (uhol θ meriame od zvislice) a F ∈ {−10, +10} N sila regulátora; kladná sila tlačí vozík v smere kladného x. Konštanty: hmotnosť vozíka m_v = 1 kg, hmotnosť tyče m_t = 0,1 kg, ich súčet M = m_v + m_t = 1,1 kg, l = 0,5 m polovica dĺžky tyče (vzdialenosť ťažiska od kĺbu) a tiažové zrýchlenie g = 9,8 m/s². Bez trenia (rovnice v tvare, ako ich uvádzajú Barto, Sutton a Anderson, 1983, a ako ich dodnes používa väčšina implementácií) sú pomocné zrýchlenie a_F, uhlové zrýchlenie tyče ε a zrýchlenie vozíka a dané predpismi

Simulácia postupuje Eulerovou metódou s krokom Δt = 0,02 s: zo stavu s_t a sily F_t sa vypočí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 ε,

t. j. nová poloha je stará plus Δt krát stará rýchlosť a nová rýchlosť je stará plus Δt krát zrýchlenie.

Štart (0, 0, 0,05, 0), teda tyč naklonená o 0,05 rad ≈ 2,9°; cos 0,05 ≈ 0,9988 a sin 0,05 ≈ 0,0500. Farby podľa rozboru vzorca pre ε vyššie. Menovateľ: 0,5 · (4/3 − 0,1 · 0,9988²/1,1) ≈ 0,621.

Sila ±10 N je oproti tiaži obrovská — jediné trhnutie obráti smer pádu. Úloha teda nie je v sile, ale v načasovaní: kedy prestať tlačiť, aby sa tyč neprehupla na druhú stranu.

Nech w = (w₁, …, w₄, b) ∈ ℝ⁵ sú váhy regulátora z úlohy kyvadla a s⁽¹⁾ = (0, 0, 0,05, 0), s⁽²⁾ = (0, 0, −0,08, 0), s⁽³⁾ = (0,5, 0, 0,02, 0,1) tri štartovacie stavy. Pre k ∈ {1, 2, 3} označme T_k(w) ∈ {1, …, 1 000} počet krokov, ktoré pokus zo štartu s^(k) s týmto regulátorom trvá (do pádu tyče alebo vyjazdu vozíka, najviac 1 000). Zdatnosť regulátora je

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

Tri štarty namiesto jedného bránia tomu, aby evolúcia našla regulátor, ktorý zvláda len jednu východiskovú polohu. Z je po častiach konštantná — malá zmena váh počet krokov väčšinou nezmení vôbec, takže gradient je takmer všade nula. Preto evolúcia.

Evolúcia váh evolučnou stratégiou (5, 20) (pozri diel Evolučné stratégie a genetické programovanie): vstupom je funkcia Z a počet generácií G ∈ ℕ, výstupom najlepšie nájdené váhy.

1. Zvoľ 5 rodičov w⁽¹⁾, …, w⁽⁵⁾ ∈ ℝ⁵, každú ich zložku nezávisle a rovnomerne z [−1, 1].
2. V každej generácii g = 1, …, G vytvor 20 potomkov: pre každého zvoľ rodiča w rovnomerne náhodne z piatich a polož w′ = w + 0,5 · z, kde z ∈ ℝ⁵ má zložky nezávislé so štandardným normálnym rozdelením N(0, 1) (pozri diel Prehľad pravdepodobnostných rozdelení).
3. Novými rodičmi je 5 potomkov s najväčšou zdatnosťou Z; starí rodičia do ďalšej generácie nepostupujú.
4. Po G generáciách vráť váhy s najväčšou zdatnosťou, aká sa počas behu objavila.

Váhy nájdené evolúciou (zaokrúhlene): w = (0,05; 1,01; 1,37; 4,23), b = 0,09 pre (x, v, θ, ω). Farby podľa rozboru neurónu na začiatku dielu: váhy, vstupy, prah.

V druhom prípade je tyč naklonená rovnako, ale regulátor tlačí opačne: uhlová rýchlosť −0,1 rad/s s váhou 4,23 má väčšiu váhu než uhol 0,05 rad s váhou 1,37. Tyč sa vracia sama, a keby vozík ďalej tlačil, prehupla by sa. Priamočiary regulátor „len podľa uhla“ by v oboch stavoch tlačil rovnako — preto tyč rozkmitá.

Nech XOR : {0, 1}² → {0, 1} je funkcia daná predpisom XOR(x₁, x₂) = 1 ⇔ x₁ ≠ x₂. Potom neexistujú čísla w₁, w₂, b ∈ ℝ také, že pre všetky (x₁, x₂) ∈ {0, 1}² platí

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

Žiadna priamka teda neoddelí body, kde sa XOR rovná 1, od bodov, kde sa rovná 0.

Dôkaz. Keby také čísla existovali, platilo by

Sčítaním prvého riadka dostaneme w₁ + w₂ + 2b ≤ 0, sčítaním druhého w₁ + w₂ + 2b > 0. Spor. ∎

Dôkaz nepoužíva tvar aktivačnej funkcie — platí pre každý jediný neurón, ktorého výstup závisí len od znamienka váženého súčtu (skok aj sigmoida s prahom 0,5).

Nech uzly siete (vstupy, prah, výstupy a skryté neuróny, pozri definíciu neurónovej siete vyššie) sú označené prirodzenými číslami. Gén spoja je pätica (u, v, w, e, i), kde u je zdrojový a v cieľový uzol spoja u → v, w ∈ ℝ jeho váha, e ∈ {0, 1} príznak (e = 1: spoj je zapnutý a v sieti sa počíta, e = 0: vypnutý) a i ∈ ℕ jeho inovačné číslo. Genóm je konečná množina génov spojov, v ktorej majú rôzne gény rôzne inovačné čísla; určuje sieť, ktorej hrany sú zapnuté spoje.

Inovačné čísla prideľuje jeden čítač pre celú populáciu: kedykoľvek mutácia prvýkrát vytvorí spoj u → v, dostane ďalšie voľné číslo; ak vznikne rovnaká štruktúrna zmena (spoj medzi tými istými uzlami) u iného jedinca, dostane rovnaké číslo.

Mutácie genómu sú tri:

1. zmena váh — váhy w génov sa zmenia (pripočítaním náhodného čísla alebo novou náhodnou hodnotou);
2. pridanie spoja — pribudne gén (u, v, w, 1, i) s náhodnou váhou w pre dva doteraz nespojené uzly u, v (náš program pridá spoj, len keď nevznikne cyklus, takže sieť zostáva dopredná);
3. pridanie neurónu — pre zvolený zapnutý gén (a, b, w, 1, i) vznikne nový skrytý neurón h, gén sa vypne (e ← 0) a pribudnú gény (a, h, 1, 1, i′) a (h, b, w, 1, i″) s novými inovačnými číslami.

Kríženie dvoch rodičov zarovná ich gény podľa inovačných čísel. Potomok dostane každý zhodný gén (inovačné číslo je v oboch rodičoch) od rodiča zvoleného náhodne s rovnakou pravdepodobnosťou a každý ostatný gén (je len v jednom z rodičov) len vtedy, ak je v genóme zdatnejšieho rodiča.

Náš NEAT používa rovnako ako pôvodný článok strmšiu sigmoidu σ(z) = 1/1 + e^−4,9z. Spoj x₁ → y s váhou 2 prispieval do výstupu 2x₁. Po rozdelení vedie x₁ → h s váhou 1 a h → y s váhou 2:

„Podobne“ tu teda znamená len sčasti: pre vstup 1 je zmena zanedbateľná, pre vstup 0 pribudne do súčtu jednotka, pretože sigmoida v nule vracia polovicu. Sieť sa tým trochu pokazí — a práve preto potrebuje nová štruktúra ochranu, o ktorej je reč ďalej.

Nech G₁, G₂ sú neprázdne genómy (pozri definíciu genómu vyššie) a I₁, I₂ množiny inovačných čísel ich génov. Označme m = min(max I₁, max I₂) a

1. zhodné gény: inovačné čísla z I₁ ∩ I₂;
2. disjunktné gény: čísla i ∈ (I₁ ∖ I₂) ∪ (I₂ ∖ I₁) s i ≤ m (chýbajú jednému z genómov „v strede“); D je ich počet;
3. prebytočné gény: čísla i ∈ (I₁ ∖ I₂) ∪ (I₂ ∖ I₁) s i > m (za koncom kratšieho genómu); E je ich počet;
4. W̄ je priemer |w_i⁽¹⁾ − w_i⁽²⁾| cez zhodné gény i (rozdiel váh toho istého génu v oboch genómoch; ak nemajú zhodné gény, W̄ = 0);
5. N = max(|G₁|, |G₂|) je počet génov väčšieho genómu, ak je aspoň 20, inak N = 1.

Pre konštanty c₁, c₂, c₃ ≥ 0 je kompatibilitná vzdialenosť genómov G₁, G₂ číslo

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

Speciácia: nech δ_t > 0 je prah a každý druh má zástupcu. Genóm patrí do prvého druhu, s ktorého zástupcom Z má δ(genóm, Z) < δ_t; ak taký neexistuje, založí nový druh. Druhy S₁, …, S_K tak rozdelia populáciu veľkosti P na disjunktné neprázdne časti.

Zdieľanie zdatnosti: ak má jedinec i ∈ S_k zdatnosť f_i ≥ 0, je jeho zdieľaná zdatnosť f′_i = f_i/|S_k|, druh k má F̄_k = ∑_{i ∈ Sk} f′_i (priemernú zdatnosť svojich členov) a dostane

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

potomkov (zaokrúhlené nadol, zvyšok dostane druh s najlepšou sieťou). Podobné genómy teda tvoria druh, zdatnosť jedinca sa delí veľkosťou jeho druhu a potomkovia sa rozdeľujú medzi druhy podľa ich priemernej zdatnosti.

Genóm A má gény 1–5. Genóm B vznikol z podobného predka: má tiež gény 1–5 (gén 3 vypnutý, pretože ho rozdelil nový neurón) a navyše gény 6 a 7 z pridania neurónu. Váhy zhodných génov sa líšia o 0,2; 0,6; 0; 0,9 a 0,8.

Keby B získal ešte jeden spoj (gén 8), vyšlo by E = 3 a δ = 3,2 ≥ 3 — B by založil nový druh. Jediný nový neurón teda sieť z druhu nevyradí, ale nový neurón s novým spojom už áno.

Populácia 150: zavedený druh A má 120 sietí s priemernou zdatnosťou 9,0, nový druh B so skrytým neurónom 30 sietí s priemernou zdatnosťou 7,5.

Bez zdieľania by nový druh za pár generácií vymrel, pretože je horší a menší. So zdieľaním dostane viac potomkov, než má členov, a má čas vyladiť váhy.

Váhy (zaokrúhlene): 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. Aktivácia je σ(z) = 1/1 + e^−4,9z. Najprv sa vypočíta h, potom y (tabuľka počíta s nezaokrúhlenými váhami, takže ručný prepočet sa môže líšiť v poslednej cifre):

Chyba je 0,150 a zdatnosť f = (4 − 0,150)² ≈ 14,82 zo 16 (farby podľa vzorca zdatnosti vyššie). Najhoršie sieť odpovedá pre (0, 1): výstup 0,855 je správne nad polovicou, ale nie pri jednotke — na riešenie to stačí, ďalšie ladenie váh by zdatnosť ešte zvýšilo.