Neuroewolucja: ewolucja wag i kształtu sieci neuronowych oraz algorytm NEAT

Neuron i sieć w pigułce, ewolucja regulatora dla wahadła na wózku, dlaczego ewolucja zamiast gradientu, XOR i neurony ukryte, NEAT ze znacznikami historycznymi i specjacją, co się dzieje bez specjacji oraz następcy od HyperNEAT po AmoebaNet.

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

Seria Podstawy AI Część 31 z 52

1. Mapa sztucznej inteligencji: co jest czym i jak to do siebie pasuje
2. Krótka historia sztucznej inteligencji: od Turinga do modeli językowych
3. Dane, model, trening, inferencja: podstawowe pojęcia na jednym przykładzie
4. Jak czytać zapis matematyczny: symbole, indeksy, sumy i kwantyfikatory
5. Zbiory i relacje: klocki, z których składają się definicje w AI
6. Funkcje i odwzorowania: dlaczego każdy model AI jest funkcją
7. Logika i dowody: reguły, według których rozumuje AI
8. Grafy i drzewa: struktura, na której opierają się przeszukiwanie i sieci neuronowe
9. Algebra liniowa dla uczenia maszynowego: wektory, macierze i dlaczego AI głównie mnoży
10. Pochodne, gradient i reguła łańcuchowa: jak model ustala, w którą stronę się uczyć
11. Spadek gradientu: jak uczy się model
12. Czym jest prawdopodobieństwo: od rzutu kostką do aksjomatów Kołmogorowa
13. Prawdopodobieństwo warunkowe i twierdzenie Bayesa: jak zmienić ocenę, gdy dowiesz się czegoś nowego
14. Zmienna losowa i dystrybuanta: jedna funkcja, która mówi o rozkładzie wszystko
15. Funkcja gęstości i funkcja prawdopodobieństwa: dlaczego zmienna ciągła ma w punkcie prawdopodobieństwo zero
16. Wartość oczekiwana, wariancja i kowariancja: gdzie leży rozkład, jak jest szeroki i co z czym się wiąże
17. Przegląd rozkładów prawdopodobieństwa: Bernoulliego, dwumianowy, Poissona, jednostajny, normalny i wykładniczy
18. Prawo wielkich liczb i centralne twierdzenie graniczne: dlaczego średnie zachowują się tak przewidywalnie
19. Statystyka i estymacja parametrów: największa wiarygodność, MAP i przedziały ufności
20. Teoria informacji: entropia, entropia krzyżowa i dywergencja KL — skąd się biorą funkcje straty
21. Przeszukiwanie przestrzeni stanów: BFS, DFS, UCS i A* z animacjami
22. Gry i przeciwnik: minimax, przycinanie alfa-beta i Monte Carlo tree search
23. Spełnianie ograniczeń: backtracking, propagacja ograniczeń i AC-3 na sudoku i mapie czeskich krajów
24. Logika i systemy z bazą wiedzy: wnioskowanie w przód i wstecz, rezolucja i systemy ekspertowe
25. Planowanie: STRIPS, świat klocków, heurystyki z relaksacji i planowanie w agentach AI
26. Przeszukiwanie lokalne i symulowane wyżarzanie: komiwojażer przez czeskie miasta wojewódzkie
27. Algorytmy genetyczne: populacja, krzyżowanie, mutacja i selekcja na plecaku na wycieczkę
28. Strategie ewolucyjne i programowanie genetyczne: od reguły jednej piątej do prawa Keplera
29. Optymalizacja kolonią mrówek: jak ślad feromonowy znajduje krótką drogę
30. Optymalizacja rojem cząstek: bezwładność, własne doświadczenie i doświadczenie roju
31. Neuroewolucja: ewolucja wag i kształtu sieci neuronowych oraz algorytm NEAT
32. Zbiory rozmyte i funkcje przynależności: jak zapisać „trochę ciepło”
33. Logika rozmyta a prawdopodobieństwo: dlaczego „trochę ciepło” nie znaczy „prawdopodobnie ciepło”
34. Logika rozmyta: t-normy, implikacje i reguły JEŻELI–TO
35. Sterowanie rozmyte: Mamdani i Sugeno od wentylatora po wahadło na wózku
36. Klasteryzacja rozmyta: algorytm fuzzy c-means i punkty między skupieniami
37. Systemy neuro-rozmyte (ANFIS): reguły rozmyte, które uczą się z danych
38. Łańcuchy Markowa: macierz przejścia, rozkład stacjonarny i PageRank
39. Ukryte modele Markowa: algorytm Viterbiego i nieuczciwe kasyno
40. Sieci bayesowskie: dlaczego trawa jest mokra i co z tego wynika dla zraszacza
41. Filtr Kalmana: jak z niedokładnych pomiarów oszacować, gdzie jest samochód i jak szybko jedzie
42. Rodzaje uczenia maszynowego: nadzorowane, nienadzorowane, półnadzorowane i inne
43. Prompty, kontekst i RAG: jak dać modelowi właściwe informacje
44. Wariacyjne autoenkodery (VAE): nowe obrazki z ciągłej przestrzeni latentnej
45. Generatywne sieci przeciwstawne (GAN): fałszerz kontra detektyw
46. Modele dyfuzyjne: jak z czystego szumu powstaje obraz
47. Procesy decyzyjne Markowa: stany, akcje, nagrody i równania Bellmana
48. Q-learning i DQN: uczenie się wartości akcji od tabeli po sieć neuronową
49. Policy gradient i PPO: uczenie się bezpośrednio polityki
50. Jak działa agent AI: model językowy w pętli z narzędziami
51. Programowanie z agentami AI: zadanie, testy i kontrola
52. Ocena i bezpieczeństwo systemów AI: jak mierzyć i jak pilnować

Pełny program serii Gotowe: 52 z 83 tematów

Sieci neuronowe uczy się dziś niemal wyłącznie metodą spadku gradientu: sieć popełnia błąd, oblicza się, w którą stronę przekręcić każdą wagę, i wagi się przekręca. A co, jeśli błędu nie da się zróżniczkować — gdy o sukcesie dowiadujemy się dopiero na końcu gry albo gdy nie wiemy nawet, jak sieć ma wyglądać? Wtedy przychodzi kolej na ewolucję. Neuroewolucja pozwala algorytmom ewolucyjnym hodować wagi sieci, a w najciekawszej odmianie także ich kształt. Tą częścią kończy się moduł o algorytmach inspirowanych przyrodą, a zarazem otwierają się drzwi do sieci neuronowych.

Nawiązuje do części Algorytmy genetyczne oraz Strategie ewolucyjne i programowanie genetyczne.

1. Sieć neuronowa w pigułce

Definicja — sztuczny neuron i sieć

Neuron z wejściami x₁, …, x_n, wagami w₁, …, w_n i progiem (biasem) b oblicza

y = σ(w₁x₁ + … + w_nx_n + b),

gdzie σ to funkcja aktywacji — na przykład sigmoida σ(z) = 1 / (1 + e^−z) albo zwykły skok „dodatnie → 1, w przeciwnym razie 0”.

Sieć neuronowa to graf skierowany neuronów: wejścia sieci prowadzą do neuronów, wyjścia neuronów do kolejnych neuronów. W sieci jednokierunkowej graf nie ma cykli. Neurony, które nie są ani wejściem, ani wyjściem, są ukryte.

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

x_i

wejścia — to, co neuron „widzi” (w przypadku wahadła położenie, prędkość, kąt); neuron ich nie zmienia, tylko na nich liczy

w_i

wagi — jedyne, co się uczy lub ewoluuje; znak mówi, czy neuron dane wejście wspiera, czy tłumi, wielkość — jak bardzo na nim zależy

b

próg — przesuwa granicę decyzyjną; bez niego zerowe wejścia dawałyby zawsze to samo σ(0), a granica musiałaby przechodzić przez początek układu

σ

funkcja aktywacji — nieliniowość; bez niej nawet sieć o wielu warstwach obliczałaby tylko funkcję liniową, bo złożenie funkcji liniowych jest znowu liniowe

2. Ewolucja wag: wahadło na wózku

Klasyczne zadanie sterowania: na wózku stoi drążek na przegubie, a wózek musi utrzymać go w pionie, przesuwając się w lewo i w prawo — jak przy balansowaniu miotłą na dłoni.

Definicja — zadanie wahadła na wózku

Stan to czwórka (x, v, θ, ω): położenie x i prędkość v wózka, kąt θ odchylenia drążka od pionu i jego prędkość kątowa ω. Co 0,02 s regulator wybiera siłę +10 N albo −10 N, a stan zmienia się zgodnie z równaniami ruchu (wózek 1 kg, drążek 0,1 kg o długości 1 m). Próba kończy się, gdy |θ| > 12° lub |x| > 2,4 m. Celem jest wytrzymać 1 000 kroków (20 s).

Regulatorem będzie pojedynczy neuron z funkcją skokową: siła wynosi +10 N, gdy w₁x + w₂v + w₃θ + w₄ω + b > 0, w przeciwnym razie −10 N. Przystosowanie to średnia liczba kroków z trzech różnych startów.

Definicja — równania ruchu wahadła na wózku

Kąt θ mierzymy od pionu, dodatnia siła pcha wózek w kierunku dodatniego x. Oznaczmy przez M = m_v + m_t = 1 + 0,1 = 1,1 kg łączną masę wózka i drążka, przez l = 0,5 m połowę długości drążka (odległość środka ciężkości od przegubu) i g = 9,8 m/s². Bez tarcia (w postaci, jaką podają Barto, Sutton i Anderson, 1983, i jakiej do dziś używa większość implementacji) przyspieszenie kątowe drążka ε i przyspieszenie wózka a wynoszą:

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

Symulacja postępuje metodą Eulera z krokiem Δt = 0,02 s: nowe położenie to stare plus Δt razy stara prędkość, nowa prędkość to stara plus Δt razy przyspieszenie — x ← x + Δt v, v ← v + Δt a, θ ← θ + Δt ω, ω ← ω + Δt ε.

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

g sin θ

ciężar — powód, dla którego drążek się przewraca: im bardziej jest pochylony, tym mocniej grawitacja przechyla go dalej; w pionie wynosi zero, więc pion jest położeniem równowagi, tyle że chwiejnej

a_F

przyspieszenie wózka od siły regulatora (plus niewielka siła odśrodkowa drążka) — jedyna droga, którą regulator działa na drążek: wózek podjeżdża pod drążek, a przegub „popycha” go z powrotem

cos θ

jaka część poziomego popchnięcia obraca drążek — przy drążku pionowym prawie całe, przy leżącym nic; dlatego drążek pochylony o więcej niż kilka stopni trudno uratować

l (4/3 − …)

bezwładność drążka — 4/3 pochodzi z momentu bezwładności jednorodnego pręta względem końca, ⅓ m(2l)² = ⁴⁄₃ ml²; odejmowany człon uwzględnia to, że przy obrocie drążka szarpie się też wózek pod nim

Przykład — jeden krok symulacji

Start (0, 0, 0,05, 0), czyli drążek pochylony o 0,05 rad ≈ 2,9°. Mianownik: 0,5 · (4/3 − 0,1 · 0,9988² / 1,1) ≈ 0,621.

bez siły (F = 0): ε = 9,8 · 0,0500 / 0,621 ≈ +0,79 rad/s² — drążek zaczyna padać

siła +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

Siła ±10 N jest w porównaniu z ciężarem ogromna — jedno szarpnięcie odwraca kierunek upadku. Zadanie nie polega więc na sile, lecz na wyczuciu czasu: kiedy przestać pchać, żeby drążek nie przechylił się na drugą stronę.

Ile daje przypadek? Spośród tysiąca regulatorów z losowymi wagami pełne 20 sekund wytrzymał tylko jeden; mediana wynosi 9 kroków — drążek pada w niespełna jedną piątą sekundy. Prosty regulator, który jedzie po prostu tam, gdzie drążek się przechyla, wytrzymuje 39 kroków: drążek wprawdzie łapie, ale go rozkołysuje. Strategia ewolucyjna (5, 20) z części o strategiach ewolucyjnych znalazła regulator, który wytrzymuje całe 20 sekund ze wszystkich trzech startów, w 15. pokoleniu — po wypróbowaniu mniej więcej trzystu regulatorów:

Wyewoluowany regulator przypisuje największą wagę prędkości kątowej — nie łapie drążka dopiero wtedy, gdy ten pada, ale już wtedy, gdy zaczyna się rozpędzać. Niebagatelne wagi mają też kąt i prędkość wózka, dzięki czemu wózek nie oscyluje i nie wyjeżdża poza tor. Takiej „reguły” nikt nie napisał; wyłoniła się z ewolucji.

Definicja — przystosowanie regulatora i ewolucja wag

Dla wag w = (w₁, …, w₄, b) niech T_k(w) ∈ {1, …, 1 000} oznacza liczbę kroków, zanim ze startu k drążek upadnie lub wózek wyjedzie (najwyżej 1 000). Funkcja przystosowania to

Z(w) = ⅓ (T₁(w) + T₂(w) + T₃(w)),

ze startami (0, 0, 0,05, 0), (0, 0, −0,08, 0) i (0,5, 0, 0,02, 0,1). Trzy starty zamiast jednego nie pozwalają ewolucji znaleźć regulatora, który radzi sobie tylko z jednym położeniem początkowym. Z jest przedziałami stała — mała zmiana wag zwykle w ogóle nie zmienia liczby kroków, więc gradient jest prawie wszędzie zerowy. Dlatego ewolucja.

Strategia ewolucyjna (5, 20): pięciu rodziców z wagami losowanymi z [−1, 1]; w każdym pokoleniu dwudziestu potomków, każdy powstaje z losowego rodzica przez dodanie 0,5 · N(0, 1) do każdej wagi; kolejnymi rodzicami zostaje pięciu najlepszych potomków.

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       # funkcja skokowa: siła ±10 N

def zdatnost(w):                     # simuluj(): kroki do upadku, najwyżej 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): przeżywają tylko potomkowie

Przykład — jak decyduje wyewoluowany regulator

Wagi znalezione przez ewolucję (w zaokrągleniu): w = (0,05; 1,01; 1,37; 4,23), b = 0,09 dla (x, v, θ, ω).

drążek pochylony, nieruchomy: (0, 0, 0,05, 0) → u = 1,37 · 0,05 + 0,09 ≈ +0,16 → +10 N, wózek podjeżdża pod drążek

drążek pochylony, ale już wraca: (0, 0, 0,05, −0,1) → u = 0,07 − 0,42 + 0,09 ≈ −0,26 → −10 N, wózek hamuje

W drugim przypadku drążek jest pochylony tak samo, ale regulator pcha w przeciwną stronę: prędkość kątowa −0,1 rad/s z wagą 4,23 waży więcej niż kąt 0,05 rad z wagą 1,37. Drążek wraca sam, a gdyby wózek dalej pchał, drążek przechyliłby się na drugą stronę. Prosty regulator „tylko według kąta” pchałby w obu stanach tak samo — dlatego rozkołysuje drążek.

3. Dlaczego ewolucja, a nie gradient

• Rzadka nagroda. W przypadku wahadła, gry czy robota jakość poznaje się dopiero po całym epizodzie. Ewolucji wystarczy jedna liczba na końcu.
• Nieróżniczkowalne części. Funkcja skokowa, symulator fizyki, reguły gry — ewolucja nie musi ich różniczkować.
• Równoległość. Każdego osobnika można ocenić niezależnie na innym komputerze.
• Struktura. Gradient potrafi stroić wagi, ale nie doda neuronu. Ewolucja może zmieniać także to, jak sieć wygląda.

Wadą jest łapczywość: zamiast jednego gradientu, który wskazuje kierunek dla wszystkich wag naraz, ewolucja próbuje losowych zmian. Dla sieci z milionami wag gradient bywa znacznie oszczędniejszy, o ile w ogóle da się go obliczyć.

4. Gdy wagi nie wystarczą: XOR

Funkcja XOR zwraca 1, gdy dokładnie jedno z dwóch wejść wynosi 1. Jak pokazała część Logika i dowody, pojedynczy neuron jej nie potrafi: jego wyjście dzieli płaszczyznę wejść prostą, a punktów (0, 1), (1, 0) od (0, 0), (1, 1) nie oddzieli żadna prosta. Do XOR potrzebny jest co najmniej jeden neuron ukryty. I tu pojawia się pytanie, którego sama ewolucja wag nie rozstrzygnie: ile neuronów i jak je połączyć?

Twierdzenie — XOR nie jest liniowo separowalny

Nie istnieją liczby w₁, w₂, b takie, że w₁x₁ + w₂x₂ + b > 0 zachodzi dokładnie w punktach, w których XOR jest równy 1.

Dowód. Gdyby takie liczby istniały, zachodziłoby

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

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

Dodając nierówności z pierwszego wiersza, otrzymujemy w₁ + w₂ + 2b ≤ 0, dodając te z drugiego — w₁ + w₂ + 2b > 0. Sprzeczność. ∎

Dowód nie korzysta z postaci funkcji aktywacji — dotyczy każdego pojedynczego neuronu, którego wyjście zależy tylko od znaku sumy ważonej (skoku, a także sigmoidy z progiem 0,5).

Można to rozwiązać ręcznie — zaprojektować architekturę i ewolucją stroić tylko wagi. Ale przy bardziej złożonych zadaniach nie wiemy, jaka architektura jest właściwa. Dlaczego nie pozwolić, by ona również wyewoluowała?

5. NEAT: ewolucja rosnących sieci

Próby ewoluowania struktury sieci napotykały trzy problemy. Jak krzyżować dwie sieci o różnym kształcie? Jak dać szansę nowej strukturze, która na początku jest gorsza, bo jej nowe wagi nie są jeszcze dostrojone? I jak zapobiec niepotrzebnemu puchnięciu sieci? Kenneth Stanley i Risto Miikkulainen odpowiedzieli w 2002 roku algorytmem NEAT (NeuroEvolution of Augmenting Topologies) opartym na trzech pomysłach.

Definicja — genom NEAT i znaczniki historyczne

Genom to lista genów połączeń; każdy gen ma neuron źródłowy i docelowy, wagę, znacznik włączony/wyłączony oraz numer innowacji. Gdy mutacja po raz pierwszy w populacji utworzy nowe połączenie, otrzymuje ono kolejny wolny numer innowacji; ta sama zmiana strukturalna u innego osobnika dostaje ten sam numer.

Mutacje: zmiana wag; dodanie połączenia między dwoma dotąd niepołączonymi neuronami; dodanie neuronu — istniejące połączenie a → b z wagą w zostaje wyłączone i zastąpione parą a → h z wagą 1 oraz h → b z wagą w.

Krzyżowanie wyrównuje geny rodziców według numerów innowacji: geny wspólne dziedziczy się losowo po jednym z rodziców, pozostałe po lepiej przystosowanym.

Przykład — dodanie neuronu na połączeniu z wagą 2

Nasz NEAT, tak jak oryginalny artykuł, używa bardziej stromej sigmoidy σ(z) = 1 / (1 + e^−4,9z). Połączenie x₁ → y z wagą 2 wnosiło do wyjścia 2x₁. Po podziale prowadzi x₁ → h z wagą 1 i h → y z wagą 2:

x₁ = 1:   2 · σ(1) = 2 · 0,993 ≈ 1,985   (wcześniej 2)

x₁ = 0:   2 · σ(0) = 2 · 0,5 = 1   (wcześniej 0)

„Podobnie” oznacza tu więc tylko częściowo: dla wejścia 1 zmiana jest pomijalna, dla wejścia 0 do sumy dochodzi jedynka, bo sigmoida w zerze zwraca połowę. Sieć trochę się przez to psuje — i właśnie dlatego nowa struktura potrzebuje ochrony, o której mowa dalej.

Definicja — specjacja i współdzielenie przystosowania

Odległość zgodności dwóch genomów to

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

gdzie E to liczba genów nadmiarowych (o numerach za końcem krótszego genomu), D liczba genów rozłącznych (brakujących w środku), W̄ średnia różnica wag genów wspólnych, a N rozmiar większego genomu (dla małych genomów 1). Genomy o δ poniżej progu należą do tego samego gatunku. Przystosowanie osobnika dzieli się przez liczebność jego gatunku, a potomstwo rozdziela się między gatunki według ich średniego przystosowania.

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

c₁ E

geny nadmiarowe — struktura, którą jeden genom zdobył dopiero po ostatnim wspólnym „wynalazku”; oznacza młodszą, odmienną gałąź rozwoju

c₂ D

geny rozłączne — wynalazki z czasów, gdy oba genomy już istniały, które ma tylko jeden z nich; kolejna miara różnicy w budowie

N

rozmiar większego genomu — żeby dwa duże genomy różniące się kilkoma genami z wielu nie wyszły tak samo odległe jak dwa małe, które różnią się niemal wszystkim; dla genomów poniżej 20 genów przyjmuje się N = 1

c₃ W̄

średnia różnica wag genów wspólnych — tak samo połączone sieci o bardzo różnych wagach obliczają różne funkcje; waga c₃ jest mniejsza, bo budowa zmienia się rzadziej i znaczy więcej

Przykład — odległość po dodaniu neuronu

Genom A ma geny 1–5. Genom B powstał z podobnego przodka: również ma geny 1–5 (gen 3 wyłączony, bo podzielił go nowy neuron), a do tego geny 6 i 7 z dodania neuronu. Wagi genów wspólnych różnią się o 0,2; 0,6; 0; 0,9 i 0,8.

wspólne: 1–5 → W̄ = (0,2 + 0,6 + 0 + 0,9 + 0,8) / 5 = 0,5

nadmiarowe: 6, 7 (za końcem krótszego genomu, który kończy się genem 5) → E = 2;   rozłączne: brak → D = 0

δ = 1 · 2 / 1 + 1 · 0 / 1 + 0,4 · 0,5 = 2,2 < 3 → ten sam gatunek

Gdyby B zyskał jeszcze jedno połączenie (gen 8), wyszłoby E = 3 i δ = 3,2 ≥ 3 — B założyłby nowy gatunek. Pojedynczy nowy neuron nie wyrzuca więc sieci z gatunku, ale nowy neuron z nowym połączeniem już tak.

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

n_k

liczba potomków gatunku k w następnym pokoleniu — w ten sposób NEAT nagradza sukces, a nie selekcją pojedynczych osobników z całej populacji

P

liczebność populacji (150) — potomstwo dzieli się jak tort, populacja ani nie rośnie, ani nie maleje

|S_k|

liczba członków gatunku — współdzielenie przystosowania: przystosowanie każdego członka dzieli się przez liczebność jego gatunku, f′_i = f_i / |S_k|; duży gatunek nie może więc zyskać więcej tylko dlatego, że jest duży

F̄_k

suma współdzielonych przystosowań gatunku, czyli jego średnie przystosowanie — o udziale w torcie decyduje jakość, nie liczebność

∑_j F̄_j

suma po wszystkich gatunkach — dzielenie daje udziały sumujące się do 1, więc rozdziela się dokładnie P potomków (po zaokrągleniu w dół resztę dostaje najlepszy gatunek)

Przykład — dlaczego współdzielenie chroni nowy gatunek

Populacja 150: ugruntowany gatunek A ma 120 sieci o średnim przystosowaniu 9,0, nowy gatunek B z neuronem ukrytym — 30 sieci o średnim przystosowaniu 7,5.

ze współdzieleniem: n_A = 150 · 9,0 / 16,5 ≈ 81,8 → 81 (+1 reszta) = 82,   n_B = 150 · 7,5 / 16,5 ≈ 68,2 → 68

bez współdzielenia (według sumy przystosowań 1 080 i 225): A ≈ 150 · 1 080 / 1 305 ≈ 124,   B ≈ 26

Bez współdzielenia nowy gatunek wymarłby po kilku pokoleniach, bo jest gorszy i mniejszy. Ze współdzieleniem dostaje więcej potomków, niż ma członków, i ma czas dostroić wagi.

Trzeci pomysł jest najprostszy: zacząć od minimum. Na początku żadna sieć nie ma ani jednego neuronu ukrytego — wejścia prowadzą wprost do wyjścia. Struktury przybywa tylko wtedy, gdy się to opłaca. Dlatego powstające sieci bywają małe.

Wszystko razem — jedno pokolenie naszego uproszczonego NEAT-u (prawdopodobieństwa są te, z którymi działa program dla XOR):

populacja ← 150 minimalnych sieci (x₁, x₂ i próg wprost do y, wagi losowo z [−2, 2])
dla pokolenia g = 0, 1, …, 100:
    oceń każdą sieć przystosowaniem f
    jeśli któraś sieć rozwiązuje zadanie: koniec
    podziel sieci na gatunki: sieć należy do pierwszego gatunku, z którego
                              przedstawicielem ma δ < 3,
                              w przeciwnym razie zakłada nowy
    usuń gatunki, które nie poprawiły się przez 15 pokoleń (oprócz gatunku z najlepszą
        siecią)
    gatunkowi k przydziel n_k = 150 · F̄_k / ∑ F̄_j potomków
    w każdym gatunku:
        rodzice ← najlepsze 20 % członków
        jeśli gatunek ma więcej niż 5 członków, jego najlepsza sieć przechodzi bez zmian
        każdy kolejny potomek:
            z prawdopodobieństwem 0,75 krzyżowanie dwojga rodziców, w przeciwnym razie
                kopia jednego
            z prawdopodobieństwem 0,8 zmień wagi
                (90 %: w ← w + N(0, 1), 10 %: nowa losowa)
            z prawdopodobieństwem 0,1 dodaj połączenie
            z prawdopodobieństwem 0,03 dodaj neuron (podziel losowe włączone połączenie)

6. NEAT na XOR

Nasz uproszczony NEAT ma populację 150 sieci i najwyżej 100 pokoleń. W przebiegu z rysunku rozwiązał XOR w pokoleniu 27 siecią z jednym neuronem ukrytym i siedmioma połączeniami — co jest najmniejszym możliwym rozwiązaniem:

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

∑ |y − t|

błąd — suma odchyleń wyjścia y od poprawnej wartości t dla wszystkich czterech wejść; wartość bezwzględna, żeby błędy w górę i w dół się nie znosiły

4

największy możliwy błąd (cztery wejścia, każde odchylenie najwyżej 1) — odejmowanie zamienia błąd, który chcemy zmniejszyć, w przystosowanie, które ewolucja zwiększa, a które jest zawsze nieujemne

²

podniesienie do kwadratu — wzmacnia różnice blisko rozwiązania: sieć z błędem 0,5 ma przystosowanie 12,25, sieć z błędem 1 tylko 9, więc selekcja mocniej nagradza ostatnie kilka procent

Sieć da się odczytać. Neuron ukryty h zapala się tylko wtedy, gdy oba wejścia wynoszą 0 (oba mają dużą ujemną wagę, próg jest dodatni). Połączenia bezpośrednie do wyjścia same obliczałyby „nie oba naraz” — wyjście 1 dla wszystkiego oprócz (1, 1) —, ale silnie ujemna waga od h wyłącza je dla (0, 0). Wyjścia 0,000; 0,855; 1,000 i 0,005 po zaokrągleniu dają dokładnie XOR. Liczba gatunków wzrosła w tym czasie z jednego do mniej więcej dwudziestu.

Przykład — obliczenie sieci dla wszystkich czterech wejść

Wagi (w zaokrągleniu): do h z x₁, x₂ i progu −3,37; −3,67; 0,95; do y z x₁, x₂, progu i h −1,42; −2,96; 3,32; −5,69. Aktywacja to σ(z) = 1 / (1 + e^−4,9z). Najpierw oblicza się h, potem y (tabela liczy z niezaokrąglonymi wagami, więc przeliczenie ręczne może się różnić na ostatniej cyfrze):

(x1, x2)	zh	h	zy	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

Błąd wynosi 0,150, a przystosowanie (4 − 0,150)² ≈ 14,82 na 16. Najgorzej sieć odpowiada dla (0, 1): wyjście 0,855 jest poprawnie powyżej połowy, ale nie przy jedynce — do rozwiązania to wystarcza, dalsze strojenie wag podniosłoby przystosowanie jeszcze bardziej.

Z pięćdziesięciu przebiegów z różnymi ziarnami NEAT rozwiązał XOR w 47, średnio w 31 pokoleń, z 2,6 neuronu ukrytego, który rzeczywiście coś robi. Oryginalny artykuł podaje 32 pokolenia i 2,35 neuronu ukrytego — nasz uproszczony NEAT jest więc blisko.

7. Na czym opiera się NEAT

Te same 50 przebiegów z wyłączoną częścią algorytmu:

Bez specjacji NEAT prawie nie działa. Sieć z neuronem ukrytym jest tuż po powstaniu gorsza od ugruntowanych sieci bez niego, bo jej nowe wagi są losowe — a we wspólnej rywalizacji selekcja natychmiast ją eliminuje. Specjacja chroni ją, dopóki nie dojrzeje. Bez krzyżowania XOR też zostaje rozwiązany, tylko wolniej i większymi sieciami (3,1 aktywnego neuronu ukrytego): krzyżowanie pomaga składać w całość cząstkowe odkrycia różnych osobników.

8. Następcy NEAT-u

• HyperNEAT (Stanley i in., 2009) ewoluuje małą sieć, która dopiero generuje wagi dużej sieci zgodnie z geometrią zadania — jak genom, który nie opisuje każdej komórki, lecz reguły wzrostu.
• Poszukiwanie nowości (Lehman i Stanley, 2011) nie nagradza przystosowania, lecz nowe zachowanie. W labiryncie ze zwodniczymi ślepymi zaułkami znajdowało cel częściej niż poszukiwanie kierowane przystosowaniem.
• Głęboka neuroewolucja. W 2017 roku zespół Uber AI pokazał, że zwykły algorytm genetyczny potrafi trenować sieci z milionami wag w grach Atari porównywalnie z uczeniem ze wzmocnieniem.
• Ewolucyjne przeszukiwanie architektur. Sieć AmoebaNet (Google, 2019) powstała przez ewolucję bloków konstrukcyjnych i w rozpoznawaniu obrazów z ImageNetu należała wówczas do najlepszych. Dziś architektury częściej projektują ludzie lub inne metody, ale ewolucja pozostaje jedną z możliwości.

9. Podsumowanie

• Neuroewolucja hoduje sieci neuronowe algorytmami ewolucyjnymi — przydaje się tam, gdzie gradientu nie da się obliczyć albo gdzie nagroda przychodzi dopiero na końcu.
• Ewolucja wag jednego neuronu utrzymuje wahadło na wózku przez 20 sekund po mniej więcej trzystu próbach; losowe wagi dają medianę 9 kroków.
• Do XOR jeden neuron nie wystarcza — trzeba zmienić strukturę sieci.
• NEAT ewoluuje wagi i strukturę: znaczniki historyczne umożliwiają krzyżowanie, specjacja chroni nowe struktury, a sieci rosną od minimum.
• Bez specjacji NEAT rozwiązał XOR w 1 z 50 przebiegów, ze specjacją w 47 — a najlepsze rozwiązanie miało jeden neuron ukryty.

Chcesz spróbować sam? Poproś agenta AI, żeby napisał wahadło na wózku z ewolucją regulatora, a potem spróbuj dwóch drążków różnej długości na jednym wózku — słynnej trudniejszej wersji, w której NEAT swego czasu błyszczał.

Masz inne zdanie? Napisz na support@coden-app.com.