Neuroevolution: Evolution der Gewichte und der Gestalt neuronaler Netze und der Algorithmus NEAT

Neuron und Netz in Kürze, Evolution eines Reglers für das inverse Pendel auf einem Wagen, warum Evolution statt Gradient, XOR und verborgene Neuronen, NEAT mit historischen Markierungen und Speziation, was ohne Speziation passiert, und Nachfolger von HyperNEAT bis AmoebaNet.

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

Serie KI-Grundlagen Teil 31 von 52

Der ganze Lehrplan der Serie 52 von 83 Themen fertig

Was du mitnimmst

Wie die Evolution die Gewichte eines Netzes findet, wenn man vom Erfolg erst am Ende erfährt.
Warum für XOR das Abstimmen der Gewichte nicht reicht und wie NEAT ein Netz vom Minimum aus wachsen lässt.
Warum NEAT ohne Speziation kaum funktioniert und wohin die Neuroevolution heute führt.

Vorher gut zu wissen: Genetische Algorithmen: Population, Kreuzung, Mutation und Selektion am Rucksack für die Wanderung, Evolutionsstrategien und genetische Programmierung: von der 1/5-Erfolgsregel zum Keplerschen Gesetz

Neuronale Netze lernen heute fast ausschließlich per Gradientenabstieg: Das Netz macht einen Fehler, man berechnet, in welche Richtung jedes Gewicht ein Stück gedreht werden soll, und dreht es. Was aber, wenn sich der Fehler nicht ableiten lässt — wenn wir erst am Ende des Spiels erfahren, ob es geklappt hat, oder wenn wir nicht einmal wissen, wie das Netz aussehen soll? Dann kommt die Evolution ins Spiel. Neuroevolution lässt evolutionäre Algorithmen die Gewichte von Netzen züchten und in ihrer interessantesten Form auch deren Gestalt. Mit diesem Teil endet das Modul über von der Natur inspirierte Algorithmen, und zugleich öffnet sich die Tür zu den neuronalen Netzen.

Er knüpft an die Teile Genetische Algorithmen und Evolutionsstrategien und genetische Programmierung an.

1. Neuronale Netze in Kürze

Definition — künstliches Neuron und Netz

Ein Neuron mit den Eingaben x₁, …, x_n, den Gewichten w₁, …, w_n und dem Bias (Schwellwert) b berechnet

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

wobei σ die Aktivierungsfunktion ist — zum Beispiel die Sigmoidfunktion σ(z) = 1 / (1 + e^−z) oder ein einfacher Sprung „positiv → 1, sonst 0“.

Ein neuronales Netz ist ein gerichteter Graph aus Neuronen: Die Eingaben des Netzes führen in Neuronen, die Ausgaben von Neuronen in weitere Neuronen. In einem vorwärtsgerichteten Netz hat der Graph keine Zyklen. Neuronen, die weder Eingabe noch Ausgabe sind, heißen verborgen.

Einfach gesagt

Ein Neuron summiert seine Eingaben, jede mit ihrem Gewicht multipliziert, und „leuchtet“ je nach Summe auf oder nicht. Die Gewichte bestimmen, worauf es ihm ankommt. Ein Netz besteht aus vielen hintereinandergeschalteten Neuronen. Das gesamte Verhalten des Netzes steckt in den Zahlenwerten der Gewichte und darin, wer mit wem verbunden ist — und beides lässt sich durch Evolution züchten. Neuronalen Netzen und ihrem Lernen per Gradient ist im Lehrplan ein ganzes eigenes Modul gewidmet.

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

x_i: Eingaben — das, was das Neuron „sieht“ (beim Pendel Position, Geschwindigkeit, Winkel); das Neuron verändert sie nicht, es rechnet nur mit ihnen
w_i: Gewichte — das Einzige, was gelernt oder evolviert wird; das Vorzeichen sagt, ob das Neuron eine Eingabe unterstützt oder dämpft, der Betrag, wie viel sie zählt
b: Bias — verschiebt die Entscheidungsgrenze; ohne ihn ergäben Nulleingaben immer dasselbe σ(0), und die Grenze müsste durch den Ursprung gehen
σ: Aktivierungsfunktion — die Nichtlinearität; ohne sie würde selbst ein Netz mit vielen Schichten nur eine lineare Funktion berechnen, denn die Verkettung linearer Funktionen ist wieder linear

Die Summe ∑ w_ix_i + b ist eine gewichtete Abstimmung der Eingaben; σ macht daraus die Ausgabe. Die Grenze zwischen „leuchtet auf“ und „leuchtet nicht auf“ ist die Menge, auf der die Summe null ist — eine Gerade (in der Ebene), allgemein eine Hyperebene.

2. Evolution der Gewichte: das inverse Pendel auf einem Wagen

Eine klassische Regelungsaufgabe: Auf einem Wagen steht ein Stab in einem Gelenk, und der Wagen muss ihn senkrecht halten, indem er nach links und rechts fährt — so, wie wenn du einen Besen auf der Handfläche balancierst.

Definition — die Aufgabe des Wagen-Pendels

Der Zustand ist ein Quadrupel (x, v, θ, ω): Position x und Geschwindigkeit v des Wagens, Winkel θ des Stabs zur Senkrechten und seine Winkelgeschwindigkeit ω. Alle 0,02 s wählt der Regler die Kraft +10 N oder −10 N, und der Zustand ändert sich gemäß den Bewegungsgleichungen (Wagen 1 kg, Stab 0,1 kg und 1 m lang). Ein Versuch endet, sobald |θ| > 12° oder |x| > 2,4 m. Ziel ist es, 1 000 Schritte (20 s) durchzuhalten.

Als Regler dient ein einziges Neuron mit Sprungfunktion als Aktivierung: Die Kraft ist +10 N, wenn w₁x + w₂v + w₃θ + w₄ω + b > 0, sonst −10 N. Die Fitness ist die mittlere Zahl der Schritte aus drei verschiedenen Startzuständen.

Einfach gesagt

Fünf Zahlen entscheiden, wann der Wagen nach links und wann nach rechts ruckt. Kein Lehrer sagt, welche Kraft in welchem Moment die richtige war — wir erfahren nur, wie lange der Stab oben blieb. Genau so eine Situation ist mit dem Gradienten schwer zu lösen und mit Evolution leicht.

Definition — Bewegungsgleichungen des Wagen-Pendels

Den Winkel θ messen wir von der Senkrechten, eine positive Kraft schiebt den Wagen in Richtung des positiven x. Sei M = m_v + m_t = 1 + 0,1 = 1,1 kg die Gesamtmasse von Wagen und Stab, l = 0,5 m die halbe Stablänge (Abstand des Schwerpunkts vom Gelenk) und g = 9,8 m/s². Ohne Reibung (die Gleichungen in der Form, wie sie Barto, Sutton und Anderson 1983 angeben und wie sie die meisten Implementierungen bis heute verwenden) sind die Winkelbeschleunigung des Stabs ε und die Beschleunigung des Wagens a:

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

Die Simulation läuft mit dem Euler-Verfahren und der Schrittweite Δt = 0,02 s: Die neue Position ist die alte plus Δt mal die alte Geschwindigkeit, die neue Geschwindigkeit ist die alte plus Δt mal die Beschleunigung — x ← x + Δt v, v ← v + Δt a, θ ← θ + Δt ω, ω ← ω + Δt ε.

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

g sin θ: Schwerkraft — der Grund, warum der Stab fällt: Je stärker er geneigt ist, desto kräftiger kippt ihn die Gravitation weiter; in der Senkrechten ist der Term null, die senkrechte Lage ist also ein Gleichgewicht, allerdings ein labiles
a_F: Beschleunigung des Wagens durch die Kraft des Reglers (plus eine kleine Zentrifugalkraft des Stabs) — der einzige Weg, auf dem der Regler auf den Stab wirkt: Der Wagen fährt unter den Stab, und das Gelenk „schubst“ ihn zurück
cos θ: welcher Anteil des waagerechten Schubs den Stab dreht — beim senkrechten Stab fast alles, beim liegenden nichts; deshalb ist ein um mehr als ein paar Grad geneigter Stab schwer zu retten
l (4/3 − …): Trägheit des Stabs — 4/3 stammt aus dem Trägheitsmoment eines homogenen Stabs um sein Ende, ⅓ m(2l)² = ⁴⁄₃ ml²; der abgezogene Term berücksichtigt, dass beim Drehen des Stabs auch der Wagen unter ihm zuckt

Die Winkelbeschleunigung des Stabs ist ein Duell zweier Terme: Die Schwerkraft kippt den Stab, die Beschleunigung des Wagens holt ihn zurück.

Beispiel — ein Simulationsschritt

Start (0, 0, 0,05, 0), der Stab ist also um 0,05 rad ≈ 2,9° geneigt. Nenner: 0,5 · (4/3 − 0,1 · 0,9988² / 1,1) ≈ 0,621.

ohne Kraft (F = 0): ε = 9,8 · 0,0500 / 0,621 ≈ +0,79 rad/s² — der Stab beginnt zu fallen

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

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

Eine Kraft von ±10 N ist gegenüber der Schwerkraft riesig — ein einziger Ruck kehrt die Fallrichtung um. Die Schwierigkeit liegt also nicht in der Kraft, sondern im Timing: wann man aufhören muss zu schieben, damit der Stab nicht auf die andere Seite überschwingt.

Wie weit kommt man mit Zufall? Von tausend Reglern mit zufälligen Gewichten hielt ein einziger alle 20 Sekunden durch; der Median liegt bei 9 Schritten — der Stab fällt nach knapp einer Fünftelsekunde. Ein naheliegender Regler, der einfach dorthin fährt, wohin sich der Stab neigt, hält 39 Schritte durch: Er fängt den Stab zwar auf, schaukelt ihn aber auf. Die Evolutionsstrategie (5, 20) aus dem Teil über Evolutionsstrategien fand in der 15. Generation einen Regler, der aus allen drei Startzuständen die vollen 20 Sekunden durchhält — nach rund dreihundert ausprobierten Reglern:

Pendel auf einem Wagen: die ersten 8 Sekunden der Simulation

Der evolvierte Regler gibt der Winkelgeschwindigkeit das größte Gewicht — er fängt den Stab nicht erst auf, wenn er fällt, sondern schon, wenn er zu fallen beginnt. Nennenswerte Gewichte haben auch der Winkel und die Geschwindigkeit des Wagens, sodass der Wagen nicht schwingt und nicht von der Bahn fährt. Diese „Regel“ hat niemand geschrieben; sie ist aus der Evolution hervorgegangen.

Definition — Fitness des Reglers und Evolution der Gewichte

Für die Gewichte w = (w₁, …, w₄, b) ist T_k(w) ∈ {1, …, 1 000} die Zahl der Schritte, bis vom Start k aus der Stab fällt oder der Wagen die Bahn verlässt (höchstens 1 000). Die Fitness ist

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

mit den Startzuständen (0, 0, 0,05, 0), (0, 0, −0,08, 0) und (0,5, 0, 0,02, 0,1). Drei Startzustände statt einem verhindern, dass die Evolution einen Regler findet, der nur eine einzige Ausgangslage beherrscht. Z ist stückweise konstant — eine kleine Änderung der Gewichte ändert die Zahl der Schritte meist überhaupt nicht, der Gradient ist also fast überall null. Deshalb Evolution.

Evolutionsstrategie (5, 20): fünf Eltern mit zufälligen Gewichten aus [−1, 1]; in jeder Generation zwanzig Nachkommen, jeder entsteht aus einem zufälligen Elternteil, indem zu jedem Gewicht 0,5 · N(0, 1) addiert wird; die nächsten Eltern sind die fünf besten Nachkommen.

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       # Sprungaktivierung: Kraft ±10 N

def zdatnost(w):                     # simuluj(): Schritte bis zum Umfallen, höchstens 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): nur die Nachkommen überleben

Beispiel — wie der evolvierte Regler entscheidet

Die von der Evolution gefundenen Gewichte (gerundet): w = (0,05; 1,01; 1,37; 4,23), b = 0,09 für (x, v, θ, ω).

Stab geneigt, in Ruhe: (0, 0, 0,05, 0) → u = 1,37 · 0,05 + 0,09 ≈ +0,16 → +10 N, der Wagen fährt unter den Stab

Stab geneigt, aber schon auf dem Rückweg: (0, 0, 0,05, −0,1) → u = 0,07 − 0,42 + 0,09 ≈ −0,26 → −10 N, der Wagen bremst

Im zweiten Fall ist der Stab genauso geneigt, doch der Regler schiebt in die Gegenrichtung: Die Winkelgeschwindigkeit −0,1 rad/s mit dem Gewicht 4,23 wiegt mehr als der Winkel 0,05 rad mit dem Gewicht 1,37. Der Stab kehrt von selbst zurück, und würde der Wagen weiter schieben, schwänge er über. Der naheliegende Regler „nur nach dem Winkel“ würde in beiden Zuständen gleich schieben — deshalb schaukelt er den Stab auf.

3. Warum Evolution und nicht der Gradient

Spärliche Belohnung. Beim Pendel, in einem Spiel oder bei einem Roboter zeigt sich die Qualität erst nach einer ganzen Episode. Der Evolution genügt eine einzige Zahl am Ende.
Nicht differenzierbare Teile. Sprungfunktion, Physiksimulator, Spielregeln — die Evolution muss sie nicht ableiten.
Parallelität. Jedes Individuum lässt sich unabhängig auf einem anderen Rechner bewerten.
Struktur. Der Gradient kann Gewichte abstimmen, aber kein Neuron hinzufügen. Die Evolution kann auch verändern, wie das Netz aussieht.

Der Nachteil ist der Hunger nach Rechenzeit: Statt eines einzigen Gradienten, der die Richtung für alle Gewichte auf einmal angibt, probiert die Evolution zufällige Änderungen aus. Für Netze mit Millionen von Gewichten ist der Gradient meist viel sparsamer — sofern er sich überhaupt berechnen lässt.

4. Wenn Gewichte nicht reichen: XOR

Die Funktion XOR liefert 1, wenn genau eine der beiden Eingaben 1 ist. Wie der Teil Logik und Beweise gezeigt hat, kann ein einzelnes Neuron sie nicht berechnen: Seine Ausgabe teilt die Ebene der Eingaben durch eine Gerade, und keine Gerade trennt die Punkte (0, 1), (1, 0) von (0, 0), (1, 1). Für XOR braucht man mindestens ein verborgenes Neuron. Damit stellt sich eine Frage, die die Evolution der Gewichte allein nicht beantwortet: Wie viele Neuronen, und wie verschaltet man sie?

Satz — XOR ist nicht linear separierbar

Es gibt keine Zahlen w₁, w₂, b, für die w₁x₁ + w₂x₂ + b > 0 genau an den Punkten gilt, an denen XOR gleich 1 ist.

Beweis. Gäbe es solche Zahlen, so gälte

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

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

Addition der ersten Zeile ergibt w₁ + w₂ + 2b ≤ 0, Addition der zweiten w₁ + w₂ + 2b > 0. Widerspruch. ∎

Der Beweis verwendet die Form der Aktivierungsfunktion nicht — er gilt für jedes einzelne Neuron, dessen Ausgabe nur vom Vorzeichen der gewichteten Summe abhängt (Sprungfunktion ebenso wie Sigmoidfunktion mit Schwelle 0,5).

Man kann die Frage von Hand beantworten — eine Architektur entwerfen und per Evolution nur die Gewichte abstimmen. Doch bei schwierigeren Aufgaben ahnen wir nicht, welche Architektur die richtige ist. Warum sie nicht ebenfalls evolvieren lassen?

5. NEAT: Evolution wachsender Netze

Versuche, die Struktur von Netzen zu evolvieren, stießen auf drei Probleme. Wie kreuzt man zwei Netze unterschiedlicher Gestalt? Wie gibt man einer neuen Struktur eine Chance, die anfangs schlechter ist, weil ihre neuen Gewichte noch nicht abgestimmt sind? Und wie verhindert man, dass Netze unnötig aufblähen? Kenneth Stanley und Risto Miikkulainen antworteten 2002 mit dem Algorithmus NEAT (NeuroEvolution of Augmenting Topologies), der auf drei Ideen beruht.

Definition — NEAT-Genom und historische Markierungen

Das Genom ist eine Liste von Verbindungsgenen; jedes Gen hat ein Quell- und ein Zielneuron, ein Gewicht, ein Flag ein/aus und eine Innovationsnummer. Sobald eine Mutation in der Population zum ersten Mal eine neue Verbindung erzeugt, erhält diese die nächste freie Innovationsnummer; dieselbe strukturelle Änderung bei einem anderen Individuum erhält dieselbe Nummer.

Mutationen: Änderung der Gewichte; Hinzufügen einer Verbindung zwischen zwei bisher unverbundenen Neuronen; Hinzufügen eines Neurons — eine bestehende Verbindung a → b mit dem Gewicht w wird abgeschaltet und durch das Paar a → h mit dem Gewicht 1 und h → b mit dem Gewicht w ersetzt.

Die Kreuzung (Crossover) richtet die Gene der Eltern nach ihren Innovationsnummern aus: Übereinstimmende Gene werden zufällig von einem der beiden Eltern geerbt, die übrigen vom fitteren.

Einfach gesagt

Die Innovationsnummer ist die Geburtsurkunde einer Verbindung. Haben zwei Netze eine Verbindung mit der Nummer 7, ist es „dieselbe“ Verbindung, auch wenn jedes auf anderem Weg zu ihr gekommen ist — und bei der Kreuzung lassen sie sich als gleiche Gene zweier Eltern paaren. Ein neues Neuron wird so eingefügt, dass das Netz anfangs ähnlich rechnet wie zuvor; nichts Wesentliches geht kaputt, es kommt nur eine Möglichkeit hinzu.

Beispiel — Hinzufügen eines Neurons auf einer Verbindung mit dem Gewicht 2

Unser NEAT verwendet wie der ursprüngliche Artikel eine steilere Sigmoidfunktion σ(z) = 1 / (1 + e^−4,9z). Die Verbindung x₁ → y mit dem Gewicht 2 trug 2x₁ zur Ausgabe bei. Nach der Aufteilung führt x₁ → h mit dem Gewicht 1 und h → y mit dem Gewicht 2:

x₁ = 1: 2 · σ(1) = 2 · 0,993 ≈ 1,985 (vorher 2)

x₁ = 0: 2 · σ(0) = 2 · 0,5 = 1 (vorher 0)

„Ähnlich“ heißt hier also nur teilweise: Für die Eingabe 1 ist die Änderung vernachlässigbar, für die Eingabe 0 kommt eine Eins zur Summe hinzu, weil die Sigmoidfunktion bei null die Hälfte liefert. Das Netz wird dadurch ein wenig schlechter — und genau deshalb braucht eine neue Struktur den Schutz, von dem gleich die Rede ist.

Definition — Speziation und Fitness-Sharing

Der Kompatibilitätsabstand zweier Genome ist

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

wobei E die Zahl der überzähligen Gene (Excess-Gene, mit Nummern jenseits des Endes des kürzeren Genoms) ist, D die Zahl der disjunkten (in der Mitte fehlenden), W̄ die mittlere Gewichtsdifferenz übereinstimmender Gene und N die Größe des größeren Genoms (für kleine Genome 1). Genome mit δ unter einer Schwelle gehören zur selben Spezies. Die Fitness eines Individuums wird durch die Größe seiner Spezies geteilt, und die Nachkommen werden nach der mittleren Fitness der Spezies auf diese verteilt.

Einfach gesagt

Netze mit ähnlichem Aufbau konkurrieren vor allem untereinander, nicht mit der ganzen Population. Ein neues Neuron bekommt so ein paar Generationen Zeit, damit sich seine Gewichte einspielen, statt sofort von den etablierten Netzen verdrängt zu werden. Und weil die Fitness innerhalb einer Spezies geteilt wird, kann keine Spezies die ganze Population beherrschen.

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

c₁ E: überzählige Gene — Struktur, die ein Genom erst nach der letzten gemeinsamen „Erfindung“ erworben hat; sie steht für einen jüngeren, abweichenden Entwicklungszweig
c₂ D: disjunkte Gene — Erfindungen aus einer Zeit, als bereits beide existierten, die aber nur eines von beiden besitzt; ein weiteres Maß für den Unterschied im Aufbau
N: Größe des größeren Genoms — damit zwei große Genome, die sich in ein paar von vielen Genen unterscheiden, nicht genauso weit auseinander liegen wie zwei kleine, die sich in fast allem unterscheiden; bei Genomen unter 20 Genen wird N = 1 genommen
c₃ W̄: mittlere Gewichtsdifferenz übereinstimmender Gene — gleich verschaltete Netze mit sehr unterschiedlichen Gewichten berechnen verschiedene Funktionen; der Faktor c₃ ist kleiner, weil sich der Aufbau seltener ändert und mehr bedeutet

Die Konstanten c₁ = c₂ = 1, c₃ = 0,4 und die Schwelle δ_t = 3 sind die Werte, die Stanley und Miikkulainen (2002) für XOR verwendet haben; unser Programm nutzt dieselben.

Beispiel — der Abstand nach dem Hinzufügen eines Neurons

Genom A hat die Gene 1–5. Genom B stammt von einem ähnlichen Vorfahren ab: Es hat ebenfalls die Gene 1–5 (Gen 3 abgeschaltet, weil es ein neues Neuron aufgeteilt hat) und zusätzlich die Gene 6 und 7 aus dem Hinzufügen des Neurons. Die Gewichte der übereinstimmenden Gene unterscheiden sich um 0,2; 0,6; 0; 0,9 und 0,8.

übereinstimmend: 1–5 → W̄ = (0,2 + 0,6 + 0 + 0,9 + 0,8) / 5 = 0,5

überzählig: 6, 7 (jenseits des Endes des kürzeren Genoms, das mit Gen 5 endet) → E = 2; disjunkt: keine → D = 0

δ = 1 · 2 / 1 + 1 · 0 / 1 + 0,4 · 0,5 = 2,2 < 3 → dieselbe Spezies

Erhielte B noch eine weitere Verbindung (Gen 8), ergäbe sich E = 3 und δ = 3,2 ≥ 3 — B würde eine neue Spezies gründen. Ein einzelnes neues Neuron wirft das Netz also nicht aus seiner Spezies, ein neues Neuron mit einer neuen Verbindung dagegen schon.

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

n_k: Zahl der Nachkommen der Spezies k in der nächsten Generation — so belohnt NEAT Erfolg, nicht durch Auswahl einzelner Individuen aus der ganzen Population
P: Populationsgröße (150) — die Nachkommen werden wie ein Kuchen aufgeteilt, die Population wächst und schrumpft nicht
|S_k|: Zahl der Mitglieder der Spezies — Fitness-Sharing: Die Fitness jedes Mitglieds wird durch die Größe seiner Spezies geteilt, f′_i = f_i / |S_k|; eine große Spezies kann so nicht mehr bekommen, nur weil sie groß ist
F̄_k: Summe der geteilten Fitnesswerte der Spezies, also ihre mittlere Fitness — über den Anteil am Kuchen entscheidet die Qualität, nicht die Anzahl
∑_j F̄_j: Summe über alle Spezies — durch die Division entsteht ein Anteil, der sich zu 1 aufsummiert, sodass genau P Nachkommen verteilt werden (nach dem Abrunden erhält den Rest die beste Spezies)

Beispiel — warum das Teilen eine neue Spezies schützt

Population 150: Die etablierte Spezies A hat 120 Netze mit der mittleren Fitness 9,0, die neue Spezies B mit einem verborgenen Neuron 30 Netze mit der mittleren Fitness 7,5.

mit Teilen: n_A = 150 · 9,0 / 16,5 ≈ 81,8 → 81 (+1 Rest) = 82, n_B = 150 · 7,5 / 16,5 ≈ 68,2 → 68

ohne Teilen (nach der Summe der Fitnesswerte 1 080 und 225): A ≈ 150 · 1 080 / 1 305 ≈ 124, B ≈ 26

Ohne Teilen würde die neue Spezies nach wenigen Generationen aussterben, weil sie schlechter und kleiner ist. Mit Teilen bekommt sie mehr Nachkommen, als sie Mitglieder hat, und hat Zeit, ihre Gewichte abzustimmen.

Die dritte Idee ist die einfachste: minimal beginnen. Zu Beginn hat kein Netz ein verborgenes Neuron — die Eingaben führen direkt zum Ausgang. Struktur kommt nur hinzu, wenn sie sich lohnt. Die resultierenden Netze sind deshalb meist klein.

Alles zusammen — eine Generation unseres vereinfachten NEAT (die Wahrscheinlichkeiten sind die, mit denen das Programm für XOR läuft):

Population ← 150 minimale Netze (x₁, x₂ und Bias direkt zu y,
    Gewichte zufällig aus [−2, 2])
für Generation g = 0, 1, …, 100:
    bewerte jedes Netz mit der Fitness f
    löst ein Netz die Aufgabe: Ende
    teile die Netze in Spezies ein: ein Netz gehört zur ersten Spezies, zu deren
                                    Vertreter δ < 3 gilt, sonst gründet es eine neue
    entferne Spezies, die sich 15 Generationen nicht verbessert haben (außer der Spezies
        mit dem besten Netz)
    weise Spezies k n_k = 150 · F̄_k / ∑ F̄_j Nachkommen zu
    in jeder Spezies:
        Eltern ← die besten 20 % der Mitglieder
        hat die Spezies mehr als 5 Mitglieder, geht ihr bestes Netz unverändert über
        jeder weitere Nachkomme:
            mit Wahrscheinlichkeit 0,75 Kreuzung zweier Eltern, sonst Kopie eines
                Elternteils
            mit Wahrscheinlichkeit 0,8 Gewichte ändern
                (90 %: w ← w + N(0, 1), 10 %: neues zufälliges)
            mit Wahrscheinlichkeit 0,1 Verbindung hinzufügen
            mit Wahrscheinlichkeit 0,03 Neuron hinzufügen (zufällige eingeschaltete
                Verbindung aufteilen)

6. NEAT löst XOR

Unser vereinfachter NEAT hat eine Population von 150 Netzen und höchstens 100 Generationen. Im Lauf aus der Abbildung löste er XOR in Generation 27 mit einem Netz mit einem einzigen verborgenen Neuron und sieben Verbindungen — das ist die kleinstmögliche Lösung:

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

∑ |y − t|: Fehler — Summe der Abweichungen der Ausgabe y vom richtigen Wert t über alle vier Eingaben; der Absolutbetrag sorgt dafür, dass sich Fehler nach oben und unten nicht aufheben
4: der größtmögliche Fehler (vier Eingaben, jede Abweichung höchstens 1) — durch die Subtraktion wird aus dem Fehler, den wir verkleinern wollen, eine Fitness, die die Evolution vergrößert, und diese ist nie negativ
²: Quadrieren — verstärkt Unterschiede nahe der Lösung: Ein Netz mit dem Fehler 0,5 hat die Fitness 12,25, ein Netz mit dem Fehler 1 nur 9, sodass die Auswahl die letzten paar Prozent stärker belohnt

Fitness für XOR nach dem ursprünglichen NEAT-Artikel (Stanley und Miikkulainen, 2002); höchstens 16. Ein Netz, das auf alles 0,5 antwortet, hat die Fitness (4 − 2)² = 4. Als Lösung zählt ein Netz, wenn es nach dem Runden der Ausgabe auf alle vier Eingaben richtig antwortet.

Das von NEAT gezüchtete Netz für XOR; rechts seine Ausgaben

Das Netz lässt sich lesen. Das verborgene Neuron h leuchtet nur auf, wenn beide Eingaben 0 sind (beide haben ein großes negatives Gewicht, der Bias ist positiv). Die direkten Verbindungen zum Ausgang würden für sich „nicht beide zugleich“ berechnen — Ausgabe 1 für alles außer (1, 1) —, doch das stark negative Gewicht von h schaltet sie für (0, 0) ab. Die Ausgaben 0,000; 0,855; 1,000 und 0,005 sind nach dem Runden genau XOR. Die Zahl der Spezies ist inzwischen von einer auf etwa zwanzig gestiegen.

Beispiel — Berechnung des Netzes für alle vier Eingaben

Gewichte (gerundet): zu h von x₁, x₂ und Bias −3,37; −3,67; 0,95; zu y von x₁, x₂, Bias und h −1,42; −2,96; 3,32; −5,69. Die Aktivierung ist σ(z) = 1 / (1 + e^−4,9z). Zuerst wird h berechnet, dann y (die Tabelle rechnet mit ungerundeten Gewichten, eine Nachrechnung von Hand kann daher in der letzten Ziffer abweichen):

(`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

Der Fehler beträgt 0,150 und die Fitness (4 − 0,150)² ≈ 14,82 von 16. Am schlechtesten antwortet das Netz für (0, 1): Die Ausgabe 0,855 liegt zwar richtig über der Hälfte, aber nicht bei eins — für eine Lösung genügt das, weiteres Abstimmen der Gewichte würde die Fitness noch erhöhen.

Von fünfzig Läufen mit verschiedenen Seeds löste NEAT XOR in 47, im Mittel nach 31 Generationen, mit 2,6 verborgenen Neuronen, die tatsächlich etwas tun. Der ursprüngliche Artikel nennt 32 Generationen und 2,35 verborgene Neuronen — unser vereinfachter NEAT liegt also nahe dran.

7. Worauf NEAT beruht

Dieselben 50 Läufe, jeweils mit einem abgeschalteten Teil des Algorithmus:

Variante	XOR gelöst	Mittlere Generation
NEAT	47 von 50	31,1
ohne Speziation (eine Spezies)	1 von 50	—
ohne Kreuzung	50 von 50	47,3

Ohne Speziation funktioniert NEAT so gut wie gar nicht. Ein Netz mit einem verborgenen Neuron ist nach seiner Entstehung schlechter als die etablierten Netze ohne ein solches, weil seine neuen Gewichte zufällig sind — und in einem einzigen gemeinsamen Wettbewerb sortiert die Selektion es sofort aus. Die Speziation schützt es, bis es ausgereift ist. Ohne Kreuzung wird XOR ebenfalls gelöst, nur langsamer und mit größeren Netzen (3,1 aktive verborgene Neuronen): Die Kreuzung hilft, Teilentdeckungen verschiedener Individuen zusammenzusetzen.

8. Die Nachfolger von NEAT

HyperNEAT (Stanley u. a., 2009) evolviert ein kleines Netz, das erst die Gewichte eines großen Netzes gemäß der Geometrie der Aufgabe erzeugt — wie ein Genom, das nicht jede Zelle beschreibt, sondern Wachstumsregeln.
Novelty Search (Lehman und Stanley, 2011) belohnt nicht die Fitness, sondern neues Verhalten. In einem Labyrinth mit trügerischen Sackgassen fand sie das Ziel häufiger als eine von der Fitness gesteuerte Suche.
Tiefe Neuroevolution. 2017 zeigte das Team von Uber AI, dass ein einfacher genetischer Algorithmus Netze mit Millionen von Gewichten auf Atari-Spielen vergleichbar gut trainieren kann wie bestärkendes Lernen.
Evolutionäre Architektursuche. Das Netz AmoebaNet (Google, 2019) entstand durch Evolution von Bausteinen und gehörte bei der Bilderkennung auf ImageNet seinerzeit zu den besten. Heute entwerfen Menschen oder andere Methoden Architekturen häufiger, doch die Evolution bleibt eine der Möglichkeiten.

9. Zusammenfassung

Neuroevolution züchtet neuronale Netze mit evolutionären Algorithmen — sie eignet sich dort, wo sich der Gradient nicht berechnen lässt oder die Belohnung erst am Ende kommt.
Die Evolution der Gewichte eines einzigen Neurons hält das Pendel auf dem Wagen nach rund dreihundert Versuchen 20 Sekunden lang aufrecht; zufällige Gewichte schaffen im Median 9 Schritte.
Für XOR reicht ein Neuron nicht — die Struktur des Netzes muss sich ändern.
NEAT evolviert Gewichte und Struktur: Historische Markierungen ermöglichen die Kreuzung, die Speziation schützt neue Strukturen, und die Netze wachsen vom Minimum aus.
Ohne Speziation löste NEAT XOR in 1 von 50 Läufen, mit Speziation in 47 — und die beste Lösung hatte ein einziges verborgenes Neuron.

Möchtest du es selbst ausprobieren? Lass einen KI-Agenten ein Pendel auf einem Wagen mit Evolution des Reglers schreiben, und versuch dann zwei Stäbe unterschiedlicher Länge auf einem Wagen — die berühmte schwierigere Variante, in der NEAT einst glänzte.

Siehst du das anders? Schreib an support@coden-app.com.

Neuroevolution: Evolution der Gewichte und der Gestalt neuronaler Netze und der Algorithmus NEAT

1. Neuronale Netze in Kürze

2. Evolution der Gewichte: das inverse Pendel auf einem Wagen

3. Warum Evolution und nicht der Gradient

4. Wenn Gewichte nicht reichen: XOR

5. NEAT: Evolution wachsender Netze

6. NEAT löst XOR

7. Worauf NEAT beruht

8. Die Nachfolger von NEAT

9. Zusammenfassung

Ein Agent auf deinem Rechner, vom Telefon aus gesteuert