Evolutionsstrategien und genetische Programmierung: von der 1/5-Erfolgsregel zum Keplerschen Gesetz

Die (1+1)-ES und die 1/5-Erfolgsregel, Population und Selbstadaptation auf der Rastrigin-Funktion, CMA-ES, Programme als Bäume, symbolische Regression, die in Planetendaten das dritte Keplersche Gesetz findet, und die Aufblähung von Programmen.

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

Serie KI-Grundlagen Teil 28 von 52

Der ganze Lehrplan der Serie 52 von 83 Themen fertig

Was du mitnimmst

Wie Evolutionsstrategien reelle Zahlen abstimmen und wie sie ihre Schrittweite selbst einstellen.
Warum in zerklüftetem Gelände eine Population gegen ein einzelnes Individuum gewinnt.
Wie genetische Programmierung ganze Formeln züchtet — und warum sie zum Aufblähen neigen.

Vorher gut zu wissen: Genetische Algorithmen: Population, Kreuzung, Mutation und Selektion am Rucksack für die Wanderung

In den sechziger Jahren standen zwei Studenten der Technischen Universität Berlin, Ingo Rechenberg und Hans-Paul Schwefel, im Windkanal über einer Gelenkplatte. Sie wollten die Form mit dem geringsten Widerstand finden, doch für eine Berechnung fehlten sowohl die Gleichungen als auch die Rechner. Also würfelten sie: Sie verdrehten die Gelenke zufällig, maßen den Widerstand, und wenn er kleiner war, behielten sie die neue Form. Aus diesem Versuch entstand die Evolutionsstrategie — eine Evolution, die statt Einsen und Nullen Zahlen abstimmt. Ein Vierteljahrhundert später zeigte John Koza, dass sich mit Evolution auch ganze Programme züchten lassen.

Dieser Teil knüpft an den Artikel Genetische Algorithmen an. Dort war ein Individuum eine Bitkette; hier wird es ein Vektor reeller Zahlen und ein Programmbaum sein.

1. Evolution von Zahlen: die (1+1)-ES

Algorithmus — (1+1)-ES

Eingabe: eine zu minimierende Funktion f : ℝⁿ → ℝ (n ≥ 1), ein Startpunkt x₀ ∈ ℝⁿ, eine Schrittweite σ > 0 und eine Anzahl von Generationen K ∈ ℕ. Ausgabe: ein Punkt x ∈ ℝⁿ und sein Wert f(x). Ein Individuum ist ein Punkt x ∈ ℝⁿ.

Setze x ← x₀.
Für k = 1, …, K wiederhole:
1. ziehe z ~ N(0, I) (ein Vektor aus n unabhängigen normalverteilten Zahlen, Definition unten) und erzeuge den Nachkommen y = x + σ · z;
2. ist f(y) ≤ f(x), setze x ← y; andernfalls behalte x.
Nach K Generationen beende und gib x und f(x) zurück. (In der Praxis bricht man oft früher ab, sobald f(x) unter eine gewählte Schranke fällt.)

Der Wert f(x) wächst also nie. In dieser Grundform ist σ fest; wie man es ändert, beschreibt die 1/5-Erfolgsregel unten.

Einfach gesagt

Ein Elternteil, ein Kind. Das Kind ist der Elter mit etwas zufälligem Rauschen in jeder Zahl; ist es besser, nimmt es seinen Platz ein. Die Schrittweite σ sagt, wie groß dieses Rauschen ist — ob es kleine Anpassungen oder große Sprünge macht.

y = x + σ · z, z ~ N(0, I)

y: Nachkomme — der neue Kandidat, den wir bewerten
x: Elter — der beste bisher gefundene Punkt; der Nachkomme entsteht in seiner Umgebung, weil in der Nähe eines guten Punkts meist weitere gute Punkte liegen
σ: Schrittweite — eine einzige Zahl, die bestimmt, wie weit vom Elter gesucht wird; das Rauschen z hat Varianz 1, erst σ gibt ihm den Maßstab der Aufgabe
z ~ N(0, I): Richtung und Länge des Versuchs — der Mittelwert 0 bedeutet, dass keine Richtung im Voraus bevorzugt wird; die Einheitsmatrix I, dass sich alle Koordinaten unabhängig und gleich stark ändern

Mutation in der Evolutionsstrategie: der Elter plus ein zufälliger Schritt, dessen Länge σ steuert.

Definition — Normalverteilung N(0, 1) und N(0, I)

Sei Z eine reelle Zufallsvariable. Z hat die Standardnormalverteilung N(0, 1) genau dann, wenn sie die Dichte φ : ℝ → (0, ∞) hat,

φ(z) = 1/√2π · exp(−z²/2), d. h. P(a ≤ Z ≤ b) = ∫_a^b φ(z) dz für alle a ≤ b.

Dann ist EZ = 0 und var Z = 1. Etwa 68 % der Werte liegen im Intervall [−1, 1] und 95 % in [−1,96; 1,96].

Sei n ≥ 1 und I ∈ ℝ^n×n die Einheitsmatrix. Ein Zufallsvektor z = (z₁, …, z_n) hat die Verteilung N(0, I) genau dann, wenn z₁, …, z_n unabhängig sind und jede die Verteilung N(0, 1) hat. Dann ist E‖z‖² = ∑_i=1ⁿ Ez_i² = n, sodass die Länge ‖z‖ typischerweise bei √n liegt (für n = 10 etwa 3,2).

Unser Programm erzeugt normalverteilte Zahlen mit der Box-Muller-Methode: Sind u₁, u₂ unabhängig und gleichverteilt auf (0, 1), so hat

z = √−2 ln u₁ · cos(2πu₂)

die Verteilung N(0, 1).

Wir probieren es an der einfachsten denkbaren Funktion, der Kugel f(x) = x₁² + … + x₁₀² in zehn Dimensionen. Das Minimum liegt offensichtlich bei null; wir starten im Punkt (3, …, 3), wo f = 90. Wie wählt man σ? Ein großer Wert kommt schnell bergab, schießt aber in der Nähe des Minimums ständig übers Ziel hinaus. Ein kleiner ist genau, braucht aber eine Ewigkeit bis zum Grund.

2. Die 1/5-Erfolgsregel

Definition — 1/5-Erfolgsregel (Rechenberg, 1973)

Es laufe eine (1+1)-ES mit Schrittweite σ > 0. Eine Mutation ist erfolgreich genau dann, wenn der Nachkomme nicht schlechter als der Elter ist, f(y) ≤ f(x). Sei p_s ∈ [0, 1] der Anteil erfolgreicher Mutationen (im letzten Abschnitt des Laufs). Die 1/5-Erfolgsregel ändert σ so:

ist p_s > 1/5, vergrößere σ;
ist p_s < 1/5, verkleinere σ;
ist p_s = 1/5, behalte σ.

Die in diesem Teil verwendete Form ändert σ nach jeder Mutation:

σ ← σ · exp(1/3) nach einem Erfolg, σ ← σ · exp(−1/12) nach einem Misserfolg.

Gelingt eine Mutation mit Wahrscheinlichkeit p, ändert sich ln σ pro Schritt im Mittel um p · 1/3 − (1 − p) · 1/12, und das ist genau dann null, wenn p = 1/5: 1/5 · 1/3 = 4/5 · 1/12. Die Schrittweite bleibt also im Mittel genau dann gleich, wenn ein Fünftel der Mutationen erfolgreich ist.

Einfach gesagt

Gelingt fast jeder Versuch, bist du unnötig vorsichtig — leg zu. Gelingt fast keiner, springst du zu weit — nimm zurück. Rechenberg leitete her, dass man am schnellsten vorankommt, wenn ungefähr jeder fünfte Versuch gelingt. So stellt der Algorithmus die Schrittweite selbst ein.

Beide Zweige der Regel lassen sich in einer Formel schreiben; s = 1 nach einem Erfolg und 0 nach einem Misserfolg:

σ ← σ · exp( 5/12 · ( s − 1/5 ) )

σ: Schrittweite — sie ändert sich durch Multiplikation, nicht durch Addition: Sie bleibt positiv, und der Schritt kann um viele Größenordnungen schrumpfen (von 1 bis auf Tausendstel), wie es die Nähe des Minimums verlangt
5/12: Anpassungsrate — nach einem Erfolg exp(5/12 · 4/5) = exp(1/3) ≈ 1,40, nach einem Misserfolg exp(−5/12 · 1/5) = exp(−1/12) ≈ 0,92; eine größere Zahl würde schneller reagieren, aber σ würde stärker schwanken
s: Ergebnis des letzten Versuchs (1 = Nachkomme war nicht schlechter) — die einzige Information, die die Regel braucht
1/5: Ziel-Erfolgsquote — gelingt genau ein Fünftel der Versuche, ist der Mittelwert von s − 1/5 null und σ bleibt im Mittel gleich

Nach N Versuchen mit S Erfolgen wird der Schritt mit exp(5/12 · (S − N/5)) multipliziert: Von zehn Versuchen lassen zwei Erfolge den Schritt unverändert, vier vergrößern ihn auf das 2,30-Fache, einer verkleinert ihn auf 0,66.

(1+1)-ES auf der Kugel in zehn Dimensionen fest σ = 1σ = 0,1σ = 0,011/5-Regel

Die 1/5-Erfolgsregel kommt nach 587 Auswertungen unter 10⁻⁶ — und die Linie im Diagramm fällt gleichmäßig, weil der Schritt genauso schnell schrumpft, wie das Minimum näher rückt. Mit festem σ = 1 stößt der Algorithmus bald auf einen „Boden“ um eins, unter den man mit so großen Sprüngen nicht kommt. Mit σ = 0,01 geht es abwärts, aber langsam: Selbst nach 5 000 Auswertungen liegt er nicht unter 10⁻⁴.

import math, random

def es_1_plus_1(f, x, sigma=1.0, kroku=1000):
    fx = f(x)
    for _ in range(kroku):
        y = [xi + sigma * random.gauss(0, 1) for xi in x]
        fy = f(y)
        if fy <= fx:
            x, fx = y, fy
            sigma *= math.exp(1 / 3)     # Erfolg: zulegen
        else:
            sigma *= math.exp(-1 / 12)   # Misserfolg: zurücknehmen
    return x, fx

Beispiel — die ersten zwölf Schritte des Laufs aus dem Diagramm

Start x = (3, …, 3), f(x) = 90, σ = 1. Die Spalte σ ist die Schrittweite nach der Aktualisierung:

Schritt	`f`(`y`)	Erfolg?	`f`(`x`)	`σ`
1	115,31	nein	90,00	0,920
2	95,78	nein	90,00	0,846
3	123,94	nein	90,00	0,779
4	107,86	nein	90,00	0,717
5	101,54	nein	90,00	0,659
6	113,11	nein	90,00	0,607
7	94,03	nein	90,00	0,558
8	95,09	nein	90,00	0,513
9	86,27	ja	86,27	0,717
10	114,52	nein	86,27	0,659
11	97,72	nein	86,27	0,607
12	102,44	nein	86,27	0,558

nach 8 Misserfolgen (s = 0): σ = 1 · [exp(5/12 · (0 − 1/5))]⁸ = exp(−8/12) ≈ 0,513

Schritt 9 gelingt (86,27 < 90, s = 1): σ = 0,513 · exp(5/12 · (1 − 1/5)) = 0,513 · exp(1/3) ≈ 0,513 · 1,396 ≈ 0,717

(Farben nach der Formel der 1/5-Erfolgsregel oben.)

Mit σ = 1 hat ein Schritt in zehn Dimensionen eine Länge von etwa √10 ≈ 3,2, und die ersten acht Nachkommen sind schlechter als der Start, also zieht die Regel den Schritt ein. Danach kommen Erfolge häufiger, und σ pendelt sich dort ein, wo ungefähr jeder fünfte Versuch gelingt — im ganzen Lauf waren 99 von 587 Versuchen erfolgreich, also 17 %. Während sich der Punkt dem Minimum nähert, schrumpft mit ihm auch der Schritt: Am Ende des Laufs, nach 580 Auswertungen, ist σ ≈ 0,00055.

3. Population und Selbstadaptation

Die Kugel hat ein einziges Minimum. Echte Aufgaben haben oft jede Menge davon — und dort reicht ein Individuum nicht. Eine typische Testfunktion ist die Rastrigin-Funktion: f(x) = 10n + ∑ (x_i² − 10 cos 2πx_i). Sie ist eine Kugel, in die jemand ein regelmäßiges Gitter von Mulden gehauen hat; das globale Minimum 0 liegt im Ursprung und um es herum Hunderte lokale.

f(x) = 10n + ∑_i=1ⁿ ( x_i² − 10 cos 2πx_i )

10n: Verschiebung nach oben — der Kosinus zieht im Ursprung höchstens 10 pro Koordinate ab, die Konstante gibt das zurück, damit das globale Minimum genau den Wert 0 hat
x_i²: Kugel — das Gesamtgefälle zum Ursprung; ohne sie wären alle Mulden gleich tief und kein Minimum wäre global
10 cos 2πx_i: Wellen mit Periode 1 und Amplitude 10 — sie graben an jeder ganzen Zahl eine Mulde; die Amplitude ist viel größer als das Gefälle der Kugel zwischen benachbarten Mulden, daher bleibt eine lokale Suche in der nächsten Mulde stecken

Die Rastrigin-Funktion: eine glatte Kugel mit regelmäßig gewellter Oberfläche.

Beispiel — Start und benachbarte Mulden (n = 2)

Start (4,2; −3,8): x₁² = 17,64, 10 cos(2π · 4,2) = 10 cos(0,4π) ≈ 3,09

x₂² = 14,44, 10 cos(2π · (−3,8)) = 10 cos(0,4π) ≈ 3,09, 10n = 20

f = 20 + (17,64 − 3,09) + (14,44 − 3,09) ≈ 45,90 (Farben nach der Formel oben)

Grund der Mulden neben dem Ursprung, bei (±1; 0) und (0; ±1): f ≈ 0,99 (im Punkt 0,995, nicht genau 1 — die Kugel zieht ihn zum Ursprung)

Grund der diagonalen Mulden bei (±1; ±1): f ≈ 1,99

Der Wert 1,49 in Generation 8 (siehe unten) bedeutet also eine Population in einer benachbarten Mulde, noch nicht an ihrem Grund.

Definition — (μ, λ)-ES und (μ + λ)-ES mit Selbstadaptation

Sei f : ℝⁿ → ℝ die zu minimierende Funktion und μ, λ ∈ ℕ. Ein Individuum ist ein Paar (x, σ) ∈ ℝⁿ × (0, ∞) — ein Punkt und seine eigene Schrittweite. Die Population ist ein μ-Tupel von Individuen (Eltern). Sei τ > 0 die Lernrate des Schritts, üblicherweise τ ≈ 1/√2n. Eine Generation:

Selbstadaptation und Mutation: Für j = 1, …, λ wähle gleichverteilt zufällig einen Elter (x, σ), ziehe unabhängig ξ_j ~ N(0, 1) und z_j ~ N(0, I) und erzeuge den Nachkommen (y_j, σ′_j), wobei σ′_j = σ · exp(τ · ξ_j), y_j = x + σ′_j · z_j. Der Nachkomme mutiert also zuerst den Schritt und verschiebt erst mit dem neuen Schritt die Position.
Selektion:
- bei der (μ, λ)-ES (erfordert λ > μ) bilden die μ Nachkommen mit den kleinsten Werten f(y_j) die neue Population, und die Eltern sterben;
- bei der (μ + λ)-ES bilden die μ Individuen mit dem kleinsten Wert von f unter allen μ + λ Eltern und Nachkommen zusammen die neue Population.

Die Generationen wiederholen sich, bis die gewählte Anzahl von Generationen (oder Auswertungen) erschöpft ist.

Einfach gesagt

Die Schrittweite wird vererbt wie jede andere Eigenschaft. Wer einen gut eingestellten Schritt hat, hat bessere Kinder — und damit setzt sich auch sein Schritt durch. Niemand muss die Erfolgsquote zählen, die Evolution stimmt sich selbst ab. Die Variante (μ, λ), in der die Eltern nicht überleben, lässt sich außerdem nicht von einem einzelnen Individuum blockieren, das Glück hatte: Jede Generation fängt neu an.

σ′ = σ · exp(τ · N(0, 1)), τ = 1/√2n

σ′: Schritt des Nachkommen — mit ihm wird sofort die Position verschoben, sodass die Fitness des Nachkommen verrät, ob der Schritt gut war
σ: Schritt des Elters — wird vererbt; der Nachkomme beginnt bei dem, was sich beim Elter bewährt hat
τ: Lernrate des Schritts — wie stark sich der Schritt zwischen Generationen ändern darf; mit wachsender Dimension n wird sie kleiner, weil ein einzelner Fitnesswert dann weniger darüber verrät, ob der Schritt gut war
N(0, 1): zufällige Änderung — symmetrisch um null, also sind Vergrößern und Verkleinern gleich wahrscheinlich; über die Richtung entscheidet erst die Selektion

Der Schritt ändert sich durch Multiplikation mit einer Exponentialfunktion: Er bleibt positiv, und Verdoppeln ist genauso wahrscheinlich wie Halbieren.

Beispiel — Mutation des Schritts für n = 2

τ = 1/√2 · 2 = 1/2

N(0, 1) = +1: σ′ = σ · exp(0,5 · 1) ≈ 1,65 σ; N(0, 1) = −1: σ′ = σ · exp(0,5 · (−1)) ≈ 0,61 σ

(Farben nach der Formel oben.)

Ein typischer Nachkomme probiert also einen Schritt, der etwa 40 % kleiner bis 65 % größer ist als der des Elters. In unserem Lauf fiel der Schritt des besten Individuums in 15 Generationen von 2 auf 0,011 — fast um das Zweihundertfache.

import math, random

def es_mi_lambda(f, start, mi=15, lam=100, sigma=2.0, generaci=80):
    n = len(start)
    tau = 1 / math.sqrt(2 * n)
    rodice = [(start, sigma)] * mi
    for _ in range(generaci):
        deti = []
        for _ in range(lam):
            x, s = random.choice(rodice)                    # zufälliger Elter
            s = s * math.exp(tau * random.gauss(0, 1))      # zuerst den Schritt mutieren
            y = [xi + s * random.gauss(0, 1) for xi in x]   # dann damit die Position
            deti.append((y, s))
        deti.sort(key=lambda d: f(d[0]))
        rodice = deti[:mi]          # (μ, λ): nur die besten Nachkommen überleben
    return rodice[0]

(15, 100)-ES auf der Rastrigin-Funktion; das Kreuz ist das globale Minimum

Die Population startet um den Punkt (4,2; −3,8), wo f ≈ 45,9. Anfangs ist sie über mehrere Mulden zugleich verteilt und zieht sich zu den tieferen zusammen. In Generation 8 ist das beste Individuum noch in einer benachbarten Mulde (f ≈ 1,49), aber die Schrittweite ist schon von 2 auf 0,27 gefallen. In Generation 15 ist die Population im globalen Minimum, und der Schritt ist auf ein Hundertstel geschrumpft, damit sie es fein ausfeilen kann.

Von hundert Läufen mit verschiedenen Seeds fand die (15, 100)-ES das globale Minimum in 32 Fällen. Zum Vergleich die (1+1)-ES mit der 1/5-Erfolgsregel und demselben Budget von 8 000 Auswertungen: in einem einzigen. Auf Kugeln ist ein einzelnes Individuum am schnellsten, in zerklüftetem Gelände gewinnt die Population — und selbst sie landet oft in einer der benachbarten Mulden.

4. CMA-ES

Selbstadaptation stimmt nur die Länge des Schritts ab. Was, wenn das Minimum in einem schmalen schrägen Tal liegt, in dem sich lange Schritte in eine Richtung und kurze in eine andere lohnen? CMA-ES (Hansen und Ostermeier, 2001) lernt aus erfolgreichen Schritten die ganze Kovarianzmatrix der Mutation — die Form der Wolke, aus der sie Nachkommen zieht. Während der Suche dreht und streckt sich die Wolke entlang des Tals. Für die Optimierung stetiger Funktionen, deren Gradienten wir nicht kennen, ist CMA-ES heute eine der zuverlässigsten Methoden.

Definition — Mutation mit Kovarianzmatrix

Sei n ≥ 1 und C ∈ ℝ^n×n eine symmetrische (C = C^T) positiv definite Matrix (v^TCv > 0 für alle v ∈ ℝⁿ, v ≠ 0). Ein Zufallsvektor z hat die Verteilung N(0, C) genau dann, wenn er dieselbe Verteilung hat wie

Au, wobei u ~ N(0, I) und A ∈ ℝ^n×n eine beliebige Matrix mit AA^T = C ist

(die Verteilung hängt von der Wahl von A nicht ab; ein solches A existiert immer, z. B. die Cholesky-Zerlegung). Dann ist Ez = 0 und E[z_iz_j] = C_ij für alle i, j = 1, …, n; C ist also die Kovarianzmatrix des Vektors z.

Sei m ∈ ℝⁿ der Mittelpunkt der Population und σ > 0 die Schrittweite. Die Mutation mit Kovarianzmatrix C erzeugt den Nachkommen

y = m + σ · z, z ~ N(0, C).

Punkte gleicher Dichte liegen auf einem Ellipsoid; seine Achsen sind die Eigenvektoren von C, und die Achsenlängen sind proportional zu den Wurzeln der Eigenwerte. Für C = I ist es eine Kugel, und wir erhalten eine gewöhnliche Evolutionsstrategie.

Vereinfacht (die echte CMA-ES fügt noch sogenannte Evolutionspfade und eine eigene Steuerung von σ hinzu, siehe N. Hansen, The CMA Evolution Strategy: A Tutorial, 2016) bewegt sich die Matrix nach jeder Generation in Richtung der erfolgreichen Schritte:

C ← (1 − c) C + c ∑_i=1^μ w_i z_iz_i^T

C: Kovarianzmatrix der Mutation — die Form der Wolke, aus der die Nachkommen gezogen werden
1 − c: Gedächtnis — die alte Matrix nähert sich der neuen Information nur ein wenig, weil eine Generation eine kleine und zufällige Stichprobe ist
c: Lernrate der Matrix, eine Zahl zwischen 0 und 1 — wie viel Gewicht die Schritte der letzten Generation bekommen
∑ w_i: gewichteter Mittelwert über die μ besten Nachkommen; die Gewichte sind positiv, summieren sich zu 1, und ein besserer Nachkomme hat ein größeres — wir lernen nur aus Schritten, die sich gelohnt haben
z_iz_i^T: der erfolgreiche Schritt z_i = y_i − m/σ als Matrix — streckt die Wolke genau in seine Richtung

Richtungen, in denen es gut lief, bekommen in der nächsten Generation eine größere Varianz.

Beispiel — ein erfolgreicher Schritt entlang der Diagonale

C = I (kreisförmige Wolke), ein einziger erfolgreicher Schritt z = (1, 1), also μ = 1 und w₁ = 1, c = 0,2 (Farben nach der Formel oben):

zz^T = [[1, 1], [1, 1]]

C ← 0,8 · [[1, 0], [0, 1]] + 0,2 · 1 · [[1, 1], [1, 1]] = [[1; 0,2], [0,2; 1]]

Eigenwerte: 1 + 0,2 = 1,2 in Richtung (1, 1) und 1 − 0,2 = 0,8 in Richtung (1, −1)

Die Wolke hat sich entlang der erfolgreichen Richtung gestreckt und quer dazu verengt — nach ein paar solchen Generationen liegt sie entlang des Tals.

5. Genetische Programmierung

Definition — Programm als Baum

Sei 𝓕 eine endliche Menge von Funktionen, wobei jede h ∈ 𝓕 eine Stelligkeit ar(h) ∈ ℕ, ar(h) ≥ 1 (Anzahl der Argumente) hat, und 𝓣 eine endliche Menge von Terminalen (Variablen und Konstanten). Die Menge der Programme über 𝓕 und 𝓣 ist die kleinste Menge von Wurzelbäumen, für die gilt:

jedes Terminal t ∈ 𝓣 ist ein Programm — ein Baum mit dem einzigen Knoten t;
sind h ∈ 𝓕, k = ar(h) und g₁, …, g_k Programme, so ist auch der Baum h(g₁, …, g_k) mit der Wurzel h und den Teilbäumen g₁, …, g_k in dieser Reihenfolge ein Programm.

Die inneren Knoten sind also Funktionen mit so vielen Kindern, wie ihre Stelligkeit angibt, und die Blätter sind Terminale. Die Größe eines Programms |g| ist die Anzahl seiner Knoten. Bei gegebenen Werten der Variablen ist der Wert eines Programms rekursiv von den Blättern zur Wurzel definiert: Der Wert eines Terminals ist sein Wert, und der Wert von h(g₁, …, g_k) ist h, angewandt auf die Werte von g₁, …, g_k.

Abgeschlossenheit: Sei D die Wertemenge (hier ℝ). Die Menge 𝓕 ist abgeschlossen genau dann, wenn jede h ∈ 𝓕 für alle Eingaben definiert ist, d. h. eine Funktion h : D^ar(h) → D ist; dann hat jedes Programm einen Wert. Deshalb verwendet man die geschützte Division, a ÷ b = a/b für |b| ≥ 10⁻⁹ und a ÷ b = 1 sonst, und die Wurzel aus dem Betrag, √|a|.

Einfach gesagt

Die Formel a/5 · √a ist ein Baum: oben die Multiplikation, darunter Division und Wurzel, unten a und eine Fünf. Genetische Programmierung kreuzt Programme, indem sie einem einen Ast abschneidet und an seine Stelle einen Ast des anderen aufpfropft. Mutation ersetzt einen Ast durch einen neu gewachsenen zufälligen. Geschützte Operationen sorgen dafür, dass kein Programm abstürzt; es kann nur Unsinn liefern — und den sortiert die Selektion aus.

John Koza von der Stanford University beschrieb die Methode 1992 im Buch Genetic Programming und zeigte sie an Dutzenden Aufgaben, von der Steuerung eines Roboters bis zur Suche nach Formeln.

Beispiel — Auswertung des Programmbaums für die Erde

Der Programmbaum a/5 · √a hat in der Wurzel die Multiplikation, links die Division a ÷ 5, rechts √a. Von den Blättern zur Wurzel, a = 149,6 (Millionen km):

linker Ast: a/5 = 149,6/5 = 29,92

rechter Ast: √a = √149,6 ≈ 12,231

Wurzel: 29,92 × 12,231 ≈ 365,95 Tage (tatsächlich 365,26, Abweichung +0,19 %)

def gp(populace, generaci, p_krizeni=0.9, max_hloubka=7):
    for _ in range(generaci):
        dalsi = [nejlepsi(populace)]                  # Elitismus: der eine Beste
        while len(dalsi) < len(populace):
            if random.random() < p_krizeni:           # Kreuzung durch Tausch von Teilbäumen
                a, b = turnaj(populace), turnaj(populace)
                dite = nahrad(a, nahodny_uzel(a), podstrom(b, nahodny_uzel(b)))
            else:                                     # Mutation: Ast → neuer zufälliger
                a = turnaj(populace)
                dite = nahrad(a, nahodny_uzel(a), nahodny_strom(hloubka=2))
            if hloubka(dite) <= max_hloubka:         # zu tiefe Kinder verwerfen wir
                dalsi.append(dite)
        populace = dalsi
    return nejlepsi(populace)        # kleinster Fehler; bei Gleichstand der kleinere Baum

6. Symbolische Regression: das Keplersche Gesetz

Johannes Kepler suchte zehn Jahre lang nach dem Zusammenhang zwischen dem Abstand eines Planeten von der Sonne und seiner Umlaufzeit; das dritte Gesetz veröffentlichte er 1619. Wir geben der genetischen Programmierung dieselbe Aufgabe. Ihr stehen acht Planeten zur Verfügung — die große Halbachse a in Millionen Kilometern und die Umlaufzeit T in Tagen —, die Operationen +, −, ×, ÷ und √, die Variable a und die Ziffern 1 bis 9. Der Fehler eines Programms ist die mittlere relative Abweichung von den tatsächlichen Umlaufzeiten. Die Population hat 300 Programme und 40 Generationen.

Definition — symbolische Regression

Seien (x₁, y₁), …, (x_N, y_N) ∈ X × ℝ Daten (X die Menge der Eingaben, z. B. ℝ^d), 𝓟 die Menge der Programme über den gewählten Funktionen 𝓕 und Terminalen 𝓣 (Definition oben; die Variablen entsprechen den Komponenten der Eingabe) und ℓ : ℝ × ℝ → [0, ∞] eine Verlustfunktion. Die symbolische Regression ist die Optimierungsaufgabe, ein

g* ∈ argmin_{g ∈ 𝓟} ∑_i=1^N ℓ(g(x_i), y_i)

zu finden, wobei g(x_i) der Wert des Programms g für die Eingabe x_i ist. Anders als bei der gewöhnlichen Regression ist also keine Form des Modells mit unbekannten Parametern vorgegeben — gesucht wird der Ausdruck selbst, nur aus den vorgegebenen Bausteinen.

Einfach gesagt

Die lineare Regression aus dem Artikel über Statistik sucht die beste Gerade. Die symbolische Regression sucht nicht Zahlen in einer bekannten Formel, sondern die Formel selbst — und das Ergebnis kann ein Mensch lesen.

Genau ist der Fehler eines Programms g der Mittelwert der absoluten Differenzen der Logarithmen:

E(g) = 1/8 ∑_i=1⁸ | ln g(a_i) − ln T_i |

1/8 ∑: Mittelwert über acht Planeten — der Fehler hängt nicht davon ab, wie viele Daten wir haben, und lässt sich als „typische Abweichung pro Planet“ lesen
| … |: Betrag — eine Vorhersage, die um 1 % zu groß ist, ist genauso schlecht wie eine um 1 % zu kleine, und Fehler verschiedener Vorzeichen heben sich nicht auf
ln g(a_i) − ln T_i: die Differenz der Logarithmen ist ln g(a_i)/T_i, also die relative Abweichung: Für kleine Abweichungen gilt ln(1 + r) ≈ r. Die Umlaufzeiten unterscheiden sich fast um das Tausendfache (88 Tage Merkur, 60 190 Neptun); mit einer gewöhnlichen Differenz würde nur Neptun über den Fehler entscheiden

Die mittlere relative Abweichung, in der Merkur dasselbe Gewicht hat wie Neptun. Ein Programm mit negativem oder unendlichem Ergebnis bekommt den Fehler ∞.

Das beste Programm der anfänglichen, zufälligen Population weicht von den tatsächlichen Umlaufzeiten im Mittel um 32 % ab. In der dritten Generation hat es schon eine Abweichung von 8 % und die richtige Form a^1,5, nur mit der Konstante 0,22. In der fünfzehnten Generation kommt dies:

Bestes Programm in Generation 15 ((a ÷ 5) × √(a))

T = a · √a/5 — also T proportional zu a^3/2, oder T² proportional zu a³. Das ist das dritte Keplersche Gesetz. Die mittlere Abweichung beträgt 0,30 %, und die Konstante 1/5 liegt sehr nahe am wahren Wert 0,1996 für diese Einheiten. Von zwanzig Läufen mit verschiedenen Seeds fanden achtzehn den Exponenten 1,5.

Woher kommt 0,1996? Aus Newtons Gravitationsgesetz folgt für eine Kreisbahn (und für eine Ellipse mit großer Halbachse a, wenn die Masse des Planeten gegenüber der Sonne vernachlässigbar ist) die Form des Gesetzes samt Konstante:

T = 2π/√GM_☉ · a^3/2

T: Umlaufzeit — die Dauer eines Umlaufs
2π: ein Umlauf ist der Winkel 2π; die Formel ergibt sich aus der Winkelgeschwindigkeit ω als T = 2π/ω
√GM_☉: Stärke der Schwerkraft der Sonne (G Gravitationskonstante, M_☉ Masse der Sonne) — stärkere Anziehung bedeutet schnelleren Umlauf, deshalb steht sie im Nenner
a^3/2: Abstand — die Schwerkraft nimmt mit a² ab, und die Bahn ist proportional zu a länger; aus der Gleichheit von Zentripetal- und Gravitationskraft ω²a = GM_☉/a² folgt ω ∝ a^−3/2

Das dritte Keplersche Gesetz, hergeleitet aus Newtons Gravitation; die genetische Programmierung fand die Form a^3/2 und die Konstante aus nur acht Zahlenpaaren.

Beispiel — die Konstante in Millionen km und Tagen

Der Gravitationsparameter der Sonne GM_☉ = 1,327 124 · 10²⁰ m³/s² (Nominalwert der Internationalen Astronomischen Union, Resolution B3 von 2015). Die Längeneinheit ist 10⁹ m, also ist a^3/2 in Metern (10⁹)^3/2 = √10²⁷-mal größer. Die Konstante in Sekunden ist 2π/√GM_☉ · √10²⁷ (Farben nach der Formel oben):

√10²⁷/1,327 124 · 10²⁰ = √7,535 · 10⁶ ≈ 2 745,0 s

2π · 2 745,0 s ≈ 17 247 s

17 247 s/86 400 s/Tag ≈ 0,1996 Tage

Das Programm mit der Konstante 1/5 = 0,2 weicht also um 0,19 % ab — genau so viel wie oben die Abweichung bei der Erde.

7. Aufblähung

Doch die Evolution blieb bei der schönen Formel nicht stehen. Bis Generation 40 „verbesserte“ sie die Abweichung auf 0,23 % hiermit:

Bestes Programm in Generation 40 (((a + ((((2 × 8) − a) ÷ 5) ÷ a)) ÷ 5) × √(a))

Der Baum hat statt sechs Knoten sechzehn, und die hinzugefügten Äste tun nichts anderes, als die Konstante nachzujustieren und Rundungen in den Daten zu umgehen. Physikalisch ist das eine schlechtere Formel — überangepasst an acht Planeten. Die durchschnittliche Programmgröße in der Population wuchs dabei von 9,8 Knoten am Anfang auf 23,8 in der zwanzigsten Generation.

Definition — Aufblähung und Sparsamkeitsdruck

Seien P₀, P₁, … die Populationen von Programmen in aufeinanderfolgenden Generationen, |g| die Größe des Programms g (Anzahl der Knoten des Baums) und F(g) ≥ 0 sein Fehler auf den Daten (kleiner ist besser). Bezeichne s̄_t die durchschnittliche Programmgröße in P_t.

Aufblähung (Bloat) ist das Phänomen, dass s̄_t mit wachsendem t deutlich wächst, ohne dass dem ein Rückgang des Fehlers F entspricht — die Programme bekommen Knoten hinzu, die den Fehler gar nicht oder nur unmerklich senken. (Es handelt sich um ein beobachtetes Phänomen, nicht um einen Begriff mit einer einzigen exakten Grenze, ab der das Wachstum nicht mehr „entsprechend“ ist.)

Sparsamkeitsdruck (Parsimony Pressure) ist eine Anpassung der Selektion, die kleinere Programme bevorzugt. Sei c > 0. Man verwendet zwei Formen:

Strafe für die Größe: Die Selektion vergleicht Programme nach dem angepassten Fehler F′(g) = F(g) + c · |g|;
lexikografischer Vergleich: Ein Programm g ist besser als h genau dann, wenn F(g) < F(h) oder F(g) = F(h) ∧ |g| < |h| — die Größe entscheidet nur bei gleichem Fehler.

Einfach gesagt

Programme setzen Code an, der nichts tut oder eine winzige Korrektur macht — ähnlich wie sich in den Genomen von Lebewesen Abschnitte ohne Funktion anhäufen. Einen großen Baum zerstört die Kreuzung außerdem schwerer, sodass er sich leichter vermehrt. Unser Algorithmus gibt bei gleichem Fehler dem kleineren Baum den Vorzug, aber wenn ein größerer Baum den Fehler um ein Haar senkt, gewinnt er. Dasselbe Dilemma wie bei der Überanpassung eines Modells: Genauigkeit auf den Daten oder Einfachheit, die verallgemeinert?

F′(g) = F(g) + c · |g|

F′(g): angepasster Fehler, nach dem ausgewählt wird — kleiner ist besser
F(g): Fehler des Programms auf den Daten — weiterhin das Wichtigste, was wir senken wollen
c: Preis eines Knotens — sagt, um wie viel sich der Fehler verbessern muss, damit sich ein zusätzlicher Knoten lohnt; man wählt ihn so, dass er nur bei vernachlässigbaren Verbesserungen entscheidet
|g|: Programmgröße, Anzahl der Knoten im Baum — ein Maß für Komplexität, das sich berechnen lässt, ohne das Programm zu verstehen

Ein zusätzlicher Knoten muss dafür bezahlen, indem er den Fehler um mindestens c senkt.

Beispiel — wie groß c das Keplersche Gesetz gerettet hätte

Baum aus Generation 15: Fehler 0,2986 %, 6 Knoten. Baum aus Generation 40: Fehler 0,2312 %, 16 Knoten. Der kleinere Baum gewinnt, wenn

0,002 986 + 6c < 0,002 312 + 16c

10c > 0,000 674 ⇒ c > 0,000 674/10 ≈ 6,7 · 10⁻⁵

(Farben nach der Formel oben: Beide Seiten der Ungleichung sind angepasste Fehler F′.)

Zehn zusätzliche Knoten verbesserten den Fehler um knapp ein Hundertstel Prozent. Mit einem Preis über 0,007 % pro Knoten hätte der Baum aus Generation 40 in der Selektion gegen das lesbare Gesetz aus Generation 15 verloren.

8. Evolutionsstrategien und Programme heute

Evolutionsstrategien statt bestärkenden Lernens. OpenAI zeigte 2017, dass eine einfache Evolutionsstrategie neuronale Netze ähnlich gut darauf trainieren kann, simulierte Roboter zu steuern und Atari-Spiele zu spielen, wie bestärkendes Lernen — und dass sie sich auf Tausende Prozessoren verteilen lässt, die einander nur ein paar Zahlen schicken.
Gesetze aus Daten entdecken. Schmidt und Lipson ließen 2009 symbolische Regression Bewegungs- und Erhaltungsgesetze aus Messungen an Pendeln herleiten. Heutige Bibliotheken wie PySR werden in Physik und Astronomie eingesetzt, wo eine lesbare Formel mehr wert ist als eine Blackbox.
Evolution von Algorithmen des maschinellen Lernens. Das Projekt AutoML-Zero (Google, 2020) ließ die Evolution Lernalgorithmen aus elementaren mathematischen Operationen zusammensetzen und entdeckte dabei zum Beispiel die Backpropagation neu.
Programme mit Sprachmodellen. Die Systeme FunSearch und AlphaEvolve aus dem vorigen Teil sind genetische Programmierung, bei der die Mutation statt eines zufälligen Asts ein Sprachmodell übernimmt.

9. Zusammenfassung

Evolutionsstrategien mutieren reelle Zahlen mit normalverteiltem Rauschen der Schrittweite σ.
Die 1/5-Erfolgsregel und die Selbstadaptation stellen σ automatisch ein; CMA-ES lernt auch die Form der Mutationen.
Auf Kugeln genügt ein Individuum, in zerklüftetem Gelände hilft eine Population: auf der Rastrigin-Funktion 32 Erfolge von 100 gegenüber einem.
Genetische Programmierung züchtet Programme als Bäume; symbolische Regression fand in Planetendaten das dritte Keplersche Gesetz.
Programme neigen dazu, aufzublähen und sich überanzupassen — dagegen hilft Sparsamkeitsdruck.

Willst du es selbst ausprobieren? Lass einen KI-Agenten eine symbolische Regression schreiben und gib ihr eigene Daten — etwa die Schwingungsdauer eines Pendels in Abhängigkeit von der Fadenlänge — und beobachte, ob sie √L findet.

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

Evolutionsstrategien und genetische Programmierung: von der 1/5-Erfolgsregel zum Keplerschen Gesetz

1. Evolution von Zahlen: die (1+1)-ES

2. Die 1/5-Erfolgsregel

3. Population und Selbstadaptation

4. CMA-ES

5. Genetische Programmierung

6. Symbolische Regression: das Keplersche Gesetz

7. Aufblähung

8. Evolutionsstrategien und Programme heute

9. Zusammenfassung

Ein Agent auf deinem Rechner, vom Telefon aus gesteuert