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

Genom und Fitness, Turnierselektion, Ein-Punkt-Kreuzung, Mutation und Elitismus, das Schema-Theorem und vorzeitige Konvergenz — am Rucksackproblem mit bekanntem Optimum, vom Zelt bis zu FunSearch und AlphaEvolve.

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

Serie KI-Grundlagen Teil 27 von 52

1. Landkarte der künstlichen Intelligenz: was was ist und wie alles zusammenpasst
2. Eine kurze Geschichte der künstlichen Intelligenz: von Turing bis zu Sprachmodellen
3. Daten, Modell, Training, Inferenz: die Grundbegriffe an einem einzigen Beispiel
4. Mathematische Notation lesen: Symbole, Indizes, Summen und Quantoren
5. Mengen und Relationen: der Baukasten, aus dem Definitionen in der KI bestehen
6. Funktionen und Abbildungen: warum jedes KI-Modell eine Funktion ist
7. Logik und Beweise: die Regeln, nach denen KI schließt
8. Graphen und Bäume: die Struktur, auf der Suche und neuronale Netze stehen
9. Lineare Algebra für maschinelles Lernen: Vektoren, Matrizen und warum KI vor allem multipliziert
10. Ableitungen, Gradient und Kettenregel: wie ein Modell herausfindet, in welche Richtung es lernen soll
11. Gradientenabstieg: wie ein Modell lernt
12. Was ist Wahrscheinlichkeit: vom Würfelwurf zu den Kolmogorow-Axiomen
13. Bedingte Wahrscheinlichkeit und der Satz von Bayes: wie du deine Einschätzung änderst, wenn du etwas Neues erfährst
14. Zufallsvariable und Verteilungsfunktion: eine Funktion, die alles über eine Verteilung verrät
15. Dichtefunktion und Wahrscheinlichkeitsfunktion: warum eine stetige Zufallsvariable in einem Punkt die Wahrscheinlichkeit null hat
16. Erwartungswert, Varianz und Kovarianz: wo eine Verteilung liegt, wie breit sie ist und was womit zusammenhängt
17. Überblick über Wahrscheinlichkeitsverteilungen: Bernoulli-, Binomial-, Poisson-, Gleich-, Normal- und Exponentialverteilung
18. Gesetz der großen Zahlen und zentraler Grenzwertsatz: Warum sich Durchschnitte so vorhersagbar verhalten
19. Statistik und Parameterschätzung: Maximum Likelihood, MAP und Konfidenzintervalle
20. Informationstheorie: Entropie, Kreuzentropie und KL-Divergenz — woher Verlustfunktionen kommen
21. Zustandsraumsuche: BFS, DFS, UCS und A* mit Animationen
22. Spiele und Gegner: Minimax, Alpha-Beta-Suche und Monte Carlo Tree Search
23. Constraint Satisfaction: Backtracking, Constraint-Propagierung und AC-3 an Sudoku und einer Karte tschechischer Regionen
24. Logik und wissensbasierte Systeme: Vorwärts- und Rückwärtsverkettung, Resolution und Expertensysteme
25. Planung: STRIPS, die Blockwelt, Heuristiken aus Relaxierung und Planung in KI-Agenten
26. Lokale Suche und simulierte Abkühlung: ein Handlungsreisender durch die tschechischen Regionalhauptstädte
27. Genetische Algorithmen: Population, Kreuzung, Mutation und Selektion am Rucksack für die Wanderung
28. Evolutionsstrategien und genetische Programmierung: von der 1/5-Erfolgsregel zum Keplerschen Gesetz
29. Ameisenkolonieoptimierung: wie eine Pheromonspur einen kurzen Weg findet
30. Partikelschwarmoptimierung: Trägheit, eigene Erfahrung und die Erfahrung des Schwarms
31. Neuroevolution: Evolution der Gewichte und der Gestalt neuronaler Netze und der Algorithmus NEAT
32. Fuzzy-Mengen und Zugehörigkeitsfunktionen: wie man „etwas warm“ aufschreibt
33. Fuzzy-Logik und Wahrscheinlichkeit: warum „etwas warm“ nicht „wahrscheinlich warm“ bedeutet
34. Fuzzy-Logik: t-Normen, Implikationen und WENN–DANN-Regeln
35. Fuzzy-Regelung: Mamdani und Sugeno vom Ventilator bis zum Pendel auf dem Wagen
36. Fuzzy-Clustering: der Algorithmus fuzzy c-means und Punkte zwischen den Clustern
37. Neuro-Fuzzy-Systeme (ANFIS): Fuzzy-Regeln, die aus Daten lernen
38. Markow-Ketten: Übergangsmatrix, stationäre Verteilung und PageRank
39. Hidden-Markov-Modelle: der Viterbi-Algorithmus und das unehrliche Kasino
40. Bayessche Netze: warum das Gras nass ist und was das für den Rasensprenger bedeutet
41. Der Kalman-Filter: wie man aus ungenauen Messungen schätzt, wo ein Auto ist und wie schnell es fährt
42. Arten des maschinellen Lernens: überwacht, unüberwacht, halbüberwacht und mehr
43. Prompts, Kontext und RAG: wie man einem Modell die richtigen Informationen gibt
44. Variational Autoencoder (VAE): neue Bilder aus einem stetigen latenten Raum
45. Generative Adversarial Networks (GAN): der Fälscher gegen den Detektiv
46. Diffusionsmodelle: wie aus reinem Rauschen ein Bild wird
47. Markow-Entscheidungsprozesse: Zustände, Aktionen, Belohnungen und Bellman-Gleichungen
48. Q-Learning und DQN: den Wert von Aktionen lernen, von der Tabelle bis zum neuronalen Netz
49. Policy Gradient und PPO: die Strategie direkt lernen
50. Wie ein KI-Agent funktioniert: ein Sprachmodell in einer Schleife mit Werkzeugen
51. Programmieren mit KI-Agenten: Auftrag, Tests und Kontrolle
52. Bewertung und Sicherheit von KI-Systemen: wie man misst und wie man überwacht

Der ganze Lehrplan der Serie 52 von 83 Themen fertig

Die Natur hat keinen Ingenieur, und doch hat sie das Auge, den Flügel und das Gehirn hervorgebracht. Drei Dinge genügten ihr: Individuen unterscheiden sich voneinander, sie geben ihre Eigenschaften an ihre Nachkommen weiter, und die tauglicheren haben mehr Nachkommen. In den Siebzigerjahren zeigte John Holland von der University of Michigan, dass dieselben drei Dinge auch im Computer funktionieren — als allgemeine Methode, gute Lösungen für Aufgaben zu finden, bei denen wir nicht wissen, wie man sie geschickt löst. Ein genetischer Algorithmus braucht keinen Gradienten und keine Formel; er muss nur sagen können, welche von zwei Lösungen die bessere ist.

Er knüpft an den Teil Lokale Suche und simulierte Abkühlung an. Die Abkühlung verbesserte eine einzige Lösung; ein genetischer Algorithmus verbessert eine ganze Population auf einmal.

1. Die Aufgabe: ein Rucksack für die Wanderung

Du bereitest dich auf eine mehrtägige Wanderung vor. Zu Hause hast du 24 Dinge — Zelt, Schlafsack, Kocher, Kamera, Buch… — und jedes wiegt etwas und ist zu etwas gut. Der Rucksack darf höchstens 10 kg wiegen. Was sollst du mitnehmen, damit der Nutzen möglichst groß ist?

Definition — das (0/1-)Rucksackproblem

Gegeben sind n Gegenstände mit Gewichten w_i > 0 und Nutzwerten u_i > 0 sowie eine Tragfähigkeit W. Gesucht ist x ∈ {0, 1}ⁿ, das ∑_i u_ix_i unter der Bedingung ∑_i w_ix_i ≤ W maximiert.

Für ganzzahlige Gewichte lässt sich das Optimum mit dynamischer Programmierung exakt berechnen — bei allen 24 Gegenständen und einer Tragfähigkeit von 1 000 Dekagramm (1 dag = 10 g) sind das 24 000 Schritte. Der beste Rucksack hat 727 Nutzenpunkte und wiegt 9,9 kg; zu Hause bleiben das zusätzliche Essen, die Kamera, das Buch, die Sandalen und die Sonnencreme. Dadurch sehen wir genau, wie nahe die Evolution herankommt. Ein genetischer Algorithmus eignet sich aber vor allem dort, wo es kein solches exaktes Verfahren gibt.

Die dynamische Programmierung füllt eine Tabelle T[i][c] — den besten Nutzen, der sich nur mit den ersten i Gegenständen erreichen lässt, wenn sie höchstens c wiegen dürfen. Jedes Feld wird aus der Zeile darüber berechnet:

T[i][c] = max( T[i − 1][c] , T[i − 1][c − w_i] + u_i )

T[i][c]

der beste Nutzen aus den ersten i Gegenständen bei Tragfähigkeit c; das Feld T[n][W] ist die Antwort auf die ganze Aufgabe

T[i − 1][c]

die Möglichkeit „den i-ten Gegenstand nehme ich nicht“ — dann ist das Beste das, was sich aus den vorherigen Gegenständen mit derselben Tragfähigkeit zusammenstellen ließ

T[i − 1][c − w_i]

die Möglichkeit „ich nehme ihn“ — der Gegenstand belegt w_i, sodass für den Rest nur c − w_i bleibt; die beste Nutzung des Rests steht schon in der Tabelle (nur erlaubt für c ≥ w_i)

u_i

der Nutzen des Gegenstands, den wir in der zweiten Möglichkeit eingepackt haben

Beispiel — die Tabelle für vier Gegenstände und eine Tragfähigkeit von 50 dag

Stirnlampe (10 dag, 25 Punkte), Messer (10 dag, 18), Kocher (40 dag, 30) und Isomatte (50 dag, 45). Alle Gewichte sind Vielfache von zehn, also genügen Spalten in Schritten von 10 dag:

Gegenstände	c = 0	10	20	30	40	50
keiner	0	0	0	0	0	0
+ Stirnlampe	0	25	25	25	25	25
+ Messer	0	25	43	43	43	43
+ Kocher	0	25	43	43	43	55
+ Isomatte	0	25	43	43	43	55

Messer, c = 20: max(T[1][20], T[1][10] + 18) = max(25, 25 + 18) = 43

Kocher, c = 40: max(T[2][40], T[2][0] + 30) = max(43, 0 + 30) = 43 — der Kocher lohnt sich nicht

Kocher, c = 50: max(T[2][50], T[2][10] + 30) = max(43, 25 + 30) = 55 — Kocher und Stirnlampe

Isomatte, c = 50: max(55, T[3][0] + 45) = max(55, 45) = 55

Die gierige Strategie würde die Gegenstände nach Nutzen pro Dekagramm nehmen: die Stirnlampe (2,5 Punkte/dag), das Messer (1,8), danach passten weder die Isomatte (0,9) noch der Kocher (0,75) in die restlichen 30 dag — nur 43 Punkte. In der großen Aufgabe mit 24 Gegenständen endet die gierige Strategie bei 702 Punkten: Sie füllt den Rucksack mit Kleinkram, und für das Zelt (220 dag) bleibt kein Platz mehr.

def batoh(w, u, W):                       # w, u: Gewichte und Nutzwerte, W: Tragfähigkeit
    T = [0] * (W + 1)                     # Zeile für „kein Gegenstand“
    for i in range(len(w)):
        for c in range(W, w[i] - 1, -1):  # rückwärts: T[c − w[i]] ist noch aus Zeile i − 1
            T[c] = max(T[c], T[c - w[i]] + u[i])
    return T[W]                           # n · W Schritte: 24 · 1000 = 24 000

2. Individuum, Genom und Fitness

Definition — Genom, Population, Fitness

Ein Genom (Chromosom) ist eine kodierte Lösung — hier eine Zeichenkette x ∈ {0, 1}²⁴, ein Bit (Gen) pro Gegenstand. Eine Population ist eine Multimenge P von Genomen fester Größe μ.

Die Fitness ist eine Funktion F : {0, 1}ⁿ → ℝ, die der Algorithmus maximiert. Für den Rucksack

F(x) = ∑ u_ix_i, wenn der Rucksack passt, sonst ∑ u_ix_i − 3 · (∑ w_ix_i − W).

F(x) = ∑ u_ix_i − 3 · max(0, ∑ w_ix_i − W)

F(x)

die Fitness des Rucksacks x — die einzige Zahl, nach der die Selektion Individuen vergleicht

∑ u_ix_i

der Nutzen der eingepackten Gegenstände (x_i = 1 zählt den Gegenstand, 0 lässt ihn weg) — das, was wir wirklich maximieren wollen

3

der Preis eines Dekagramms über dem Limit — er ist größer als das beste Verhältnis von Nutzen zu Gewicht (Stirnlampe, 2,5 Punkte/dag), sodass jedes zusätzliche Einpacken in einen schon überladenen Rucksack die Fitness immer senkt

max(0, ∑ w_ix_i − W)

die Überladung in Dekagramm; das Maximum mit null sorgt dafür, dass ein passender Rucksack keine Strafe bekommt und ein leichterer Rucksack nicht bevorzugt wird

Beispiel — die Fitness zweier Rucksäcke

Optimum: Nutzen 727, Gewicht 990 dag ≤ 1 000  ⇒  F = 727 − 3 · 0 = 727

Optimum + Kamera (80 dag, 20 Punkte): Nutzen 747, Gewicht 1 070 dag  ⇒  F = 747 − 3 · 70 = 537

Die Kamera bringt 20 Punkte, aber die Überladung von 70 dag kostet 210 — die Selektion schiebt einen solchen Rucksack zuverlässig beiseite.

3. Selektion

Definition — Turnier- und Rouletteselektion

Turnierselektion der Größe k: Wähle zufällig k Individuen aus der Population und gib das mit der höchsten Fitness zurück.

Rouletteselektion: Wähle das Individuum x mit Wahrscheinlichkeit F(x) / ∑_{y ∈ P} F(y) (erfordert positive Fitness).

Der Selektionsdruck ist ein Maß dafür, wie stark die Selektion tauglichere Individuen bevorzugt; beim Turnier wächst er mit k.

Wie stark ein Turnier ist, lässt sich exakt berechnen. Unser Programm zieht k Individuen mit Zurücklegen (dasselbe Individuum kann zweimal ins Turnier kommen). Ordnen wir die Population vom besten (i = 1) bis zum schlechtesten (i = μ):

P(i-tes gewinnt) = ( (μ − i + 1)^k − (μ − i)^k ) / μ^k

P(i-tes gewinnt)

die Chance, dass genau das i-te beste Individuum Elternteil wird

(μ − i + 1)^k

die Zahl der Turniere, in denen niemand besser ist als das i-te — alle k Ziehungen fallen auf es selbst oder schlechtere

(μ − i)^k

davon ziehen wir die Turniere ab, in denen das i-te gar nicht vorkommt — die würde ein schlechteres gewinnen; die Differenz sind die Turniere, in denen das i-te das beste anwesende ist

μ^k

die Zahl aller möglichen Turniere (k Ziehungen, jede aus μ Individuen) — durch Teilen erhalten wir eine Wahrscheinlichkeit

Beispiel — ein Turnier aus drei unter 40 Rucksäcken

μ^k = 40³ = 64 000. Pro Generation werden 38 Eltern ausgewählt (zwei Plätze belegen die Elite-Individuen):

das beste: (40³ − 39³) / 64 000 = (64 000 − 59 319) / 64 000 ≈ 7,31 %,   erwartet 38 · 0,0731 ≈ 2,78 Auswahlen

das 20.-beste: (21³ − 20³) / 64 000 = (9 261 − 8 000) / 64 000 ≈ 1,97 %,   erwartet ≈ 0,75 Auswahlen

das schlechteste: (1³ − 0³) / 64 000 ≈ 0,0016 %,   erwartet ≈ 0,0006 Auswahlen

Ein durchschnittliches Individuum bekommt 38/40 = 0,95 Auswahlen, das beste fast dreimal so viele. Allgemein bekommt bei einer großen Population das beste ungefähr k-mal so viel wie der Durchschnitt — deshalb wächst der Selektionsdruck mit k.

4. Kreuzung und Mutation

Definition — Ein-Punkt-Kreuzung

Für Eltern a, b ∈ {0, 1}ⁿ wähle zufällig einen Punkt c ∈ {1, …, n − 1}. Die Nachkommen sind

(a₁, …, a_c, b_c+1, …, b_n) und (b₁, …, b_c, a_c+1, …, a_n).

Die Kreuzung wird mit Wahrscheinlichkeit p_c durchgeführt, sonst sind die Nachkommen Kopien der Eltern. Weitere Varianten sind die Zwei-Punkt- und die uniforme Kreuzung (jedes Gen von einem zufälligen Elternteil).

Definition — Bitmutation

Jedes Gen des Nachkommen wird unabhängig mit Wahrscheinlichkeit p_m umgedreht (0 ↔ 1), üblicherweise p_m = 1/n — im Durchschnitt ein Gen pro Individuum.

Beispiel — wie viele Gene die Mutation umdreht

Die Zahl der umgedrehten Gene ist binomialverteilt: P(j Gene) = (n über j) · p_m^j · (1 − p_m)^n−j. Für n = 24 und p_m = 1/24:

erwartete Anzahl: n · p_m = 24 · 1/24 = 1

keine Änderung: (23/24)²⁴ ≈ 0,360   (für großes n nähert es sich 1/e ≈ 0,368)

genau ein Gen: 24 · (1/24) · (23/24)²³ ≈ 0,376

Grob ein Drittel der Nachkommen bleibt also unverändert, ein Drittel unterscheidet sich in einem Gen und der Rest in zwei oder mehr.

Die Eltern sind die zwei besten Rucksäcke der Anfangspopulation (423 und 398 Punkte), der Schnitt liegt hinter dem zwölften Gegenstand. Keiner der Nachkommen ist besser als der bessere Elternteil — sie haben 403 und 418 Punkte. Die Kreuzung garantiert keine Verbesserung; sie bietet nur neue Kombinationen an, und die Selektion entscheidet dann, welche überleben. Beim ersten Nachkommen hat die Mutation einen Wasserfilter eingepackt (15 dag, 32 Punkte), und er hat auf einmal 435 Punkte — mehr als beide Eltern.

Beispiel — die Kreuzung aus der Abbildung nachgerechnet

Der Nutzen addiert sich genweise, also genügt es, den Nutzen des Anfangs (Gegenstände 1–12) und des Endes (Gegenstände 13–24) getrennt zu addieren:

Elternteil 1: 310 + 113 = 423,   Elternteil 2: 305 + 93 = 398

Nachkomme 1 = Anfang von Elternteil 1 + Ende von Elternteil 2: 310 + 93 = 403

Nachkomme 2 = Anfang von Elternteil 2 + Ende von Elternteil 1: 305 + 113 = 418

die Mutation packt den Wasserfilter ein: 403 + 32 = 435

Elternteil 1 ist in beiden Hälften besser (310 > 305 und 113 > 93), also kann ihn bei diesem Schnitt kein Nachkomme übertreffen — die Kreuzung hat nichts, woraus sie ein besseres Ganzes zusammensetzen könnte. Die Verbesserung brachte erst die Mutation.

5. Der ganze Algorithmus

Algorithmus — genetischer Algorithmus

1. Erzeuge eine zufällige Anfangspopulation aus μ Individuen und bewerte sie.
2. Kopiere die e besten Individuen unverändert in die neue Generation (Elitismus).
3. Solange die neue Generation nicht μ Individuen hat: Wähle zwei Eltern aus, kreuze sie mit Wahrscheinlichkeit p_c, mutiere die Nachkommen und füge sie hinzu.
4. Bewerte die neue Generation und fahre mit Schritt 2 fort, bis die Zahl der Generationen erreicht ist.

import random

def evoluce(zdatnost, n, velikost=40, generaci=60, p_krizeni=0.9, elita=2):
    pop = [[int(random.random() < 0.3) for _ in range(n)] for _ in range(velikost)]
    for _ in range(generaci):
        pop.sort(key=zdatnost, reverse=True)
        dalsi = [g[:] for g in pop[:elita]]            # Elitismus
        while len(dalsi) < velikost:
            a, b = turnaj(pop, zdatnost), turnaj(pop, zdatnost)
            if random.random() < p_krizeni:
                bod = random.randrange(1, n)
                a, b = a[:bod] + b[bod:], b[:bod] + a[bod:]
            dalsi += [mutuj(a), mutuj(b)]
        pop = dalsi[:velikost]
    return max(pop, key=zdatnost)

def turnaj(pop, zdatnost, k=3):
    return max(random.choices(pop, k=k), key=zdatnost)   # k Ziehungen mit Zurücklegen

def mutuj(g):
    return [1 - x if random.random() < 1 / len(g) else x for x in g]

Die Kosten des Algorithmus messen wir an der Zahl der Fitnessbewertungen — bei echten Aufgaben (Simulationen, Messungen) ist das der teuerste Schritt. Bewertet wird die Anfangspopulation und dann jede Generation: μ + G · μ = 40 + 60 · 40 = 2 440 Bewertungen für μ = 40 Individuen und G = 60 Generationen. Die Elite-Individuen werden erneut bewertet, obwohl sie sich nicht verändert haben; ein klügeres Programm würde sich ihre Fitness merken.

6. Die Evolution des Rucksacks

Lassen wir den Algorithmus laufen: 40 Rucksäcke, 60 Generationen, Turnier aus drei, Kreuzung mit Wahrscheinlichkeit 0,9, Mutation 1/24 und zwei Elite-Individuen. Die Abbildung zeigt die Population in den Generationen 0, 5, 15, 30 und 60 — jede Zeile ist ein Rucksack, jede Spalte ein Gegenstand, oben zum Vergleich das Optimum:

Am Anfang ist die Population bunt, und die Rucksäcke sind eher halb leer: Jeder Gegenstand kam mit Wahrscheinlichkeit 0,3 hinein, also wiegen sie um die vier Kilo (das erwartete Gewicht ist 0,3 · ∑ w_i = 0,3 · 12,75 kg ≈ 3,8 kg). Der beste hat 423 Punkte, der Durchschnitt 231. Nach fünf Generationen tragen 36 von 40 Rucksäcken das Zelt, 35 die Wasserflasche, und der beste Rucksack hat 634 Punkte. Um die fünfzehnte Generation stößt die Population an die Tragfähigkeit — 12 Rucksäcke sind überladen — und beginnt zu lernen, was sie opfern soll: Das zusätzliche Essen und die Sandalen sind fast verschwunden, die Kamera tragen aber noch 39 Rucksäcke. Das Optimum, 727 Punkte, findet der Algorithmus zum ersten Mal in Generation 26; in Generation 30 ist die Kamera nur noch in einem Rucksack übrig. Die Population verschmilzt aber nie zu einer einzigen Lösung — die Mutation probiert immer wieder kleine Abweichungen aus.

Der Algorithmus hat dafür 2 440 Rucksäcke bewertet — knapp zwei Hundertstel Prozent aller 16 777 216 Möglichkeiten. Eine Zufallssuche mit derselben Zahl von Versuchen fand das Optimum in hundert Wiederholungen kein einziges Mal und endete im Durchschnitt bei 574 Punkten.

Beispiel — warum die Zufallssuche das Optimum nicht findet

Ein zufälliger Rucksack nimmt jeden Gegenstand unabhängig mit Wahrscheinlichkeit 0,3. Das Optimum enthält 19 Gegenstände und lässt 5 weg, also

P(zufälliger Rucksack = Optimum) = 0,3¹⁹ · 0,7⁵ ≈ 1,16 · 10⁻¹⁰ · 0,168 ≈ 1,95 · 10⁻¹¹

erwartete Zahl der Treffer in 2 440 Versuchen: 2 440 · 1,95 · 10⁻¹¹ ≈ 4,8 · 10⁻⁸

Selbst wenn gleichmäßig gezogen würde (jeder Gegenstand mit Wahrscheinlichkeit 1/2), stünde die Chance bei eins zu 16 777 216 pro Versuch. Ein genetischer Algorithmus zieht das Optimum nicht auf einmal — er setzt es Stück für Stück aus Rucksäcken zusammen, die schon gut sind.

7. Wozu Kreuzung und wozu Mutation

Die orange Linie im Diagramm ist derselbe Lauf mit ausgeschalteter Mutation. Nach elf Generationen bleibt sie bei 573 Punkten stecken und bewegt sich nicht mehr. Warum, zeigt ein Vergleich aus hundert Läufen mit verschiedenen Seeds:

Ohne Mutation verliert die Population ihre Vielfalt: Wenn ein Gen in keinem Individuum vorkommt, kann die Kreuzung es nicht erzeugen, und die Selektion verdrängt zudem schnell alles außer den besten. Man nennt das vorzeitige Konvergenz. Ohne Kreuzung funktioniert der Algorithmus — er ist im Grunde eine Population von Bergsteigern mit Selektion —, aber er ist langsamer. Die Kreuzung hilft, gute Stücke zusammenzusetzen, die in verschiedenen Individuen entstanden sind.

Satz — Hollands Schema-Theorem

Ein Schema H ist ein Muster über {0, 1, ∗}, wobei ∗ „beliebig“ bedeutet; seine Ordnung o(H) ist die Zahl der festen Positionen und seine definierende Länge δ(H) der Abstand zwischen der ersten und der letzten festen Position. Für m(H, t) Individuen, die in Generation t zu H passen, und Rouletteselektion gilt

E[m(H, t + 1)] ≥ m(H, t) · F(H) / F̄ · [1 − p_c · δ(H) / (n − 1) − o(H) · p_m],

wobei F(H) die durchschnittliche Fitness der Individuen des Schemas und F̄ der Durchschnitt der Population ist.

E[m(H, t + 1)] ≥ m(H, t) · F(H) / F̄ · [1 − p_c · δ(H) / (n − 1) − o(H) · p_m]

m(H, t)

wie viele Individuen den Baustein jetzt tragen — die nächste Generation geht von ihnen aus, deshalb wird damit multipliziert

F(H) / F̄

um wie viel die Träger des Schemas tauglicher sind als der Durchschnitt — das Roulette gibt ihnen proportional mehr Nachkommen; über 1 vermehrt sich das Schema, unter 1 stirbt es aus

p_c · δ(H) / (n − 1)

die Chance, dass die Kreuzung das Schema zerschneidet: Die Kreuzung findet mit p_c statt, und der Schnittpunkt fällt mit Wahrscheinlichkeit δ/(n − 1) zwischen die festen Positionen — deshalb schaden lange Schemata

o(H) · p_m

die Chance (nach oben abgeschätzt), dass die Mutation eine der o(H) festen Positionen umdreht — deshalb schaden Schemata hoher Ordnung

Beispiel — ein kurzes und ein langes Schema beim Rucksack

Die eckige Klammer für die Einstellungen unseres Laufs (p_c = 0,9, n = 24, p_m = 1/24). Beide Schemata haben Ordnung 2:

„Zelt und Schlafsack“ (Gene 1 und 2, δ = 1): 1 − 0,9 · 1/23 − 2/24 ≈ 1 − 0,039 − 0,083 = 0,878

„Zelt und Ersatzsocken“ (Gene 1 und 24, δ = 23): 1 − 0,9 · 23/23 − 2/24 ≈ 1 − 0,9 − 0,083 = 0,017

Beim kurzen Schema genügt es, dass seine Träger um 14 % tauglicher sind als der Durchschnitt (1/0,878 ≈ 1,14), und laut Satz breitet es sich bereits aus. Das lange Schema müsste sechzigmal tauglicher sein — der Satz verspricht darüber im Grunde nichts. Unser Algorithmus verwendet ein Turnier, kein Roulette, also gilt für ihn nur die eckige Klammer; die ersten beiden Faktoren würden anders berechnet.

8. Genetische Algorithmen in der Praxis

• Formentwurf. Die Antenne der NASA-Satelliten ST5 (gestartet 2006) wurde von einem evolutionären Algorithmus entworfen: ein seltsam verbogenes Drahtstück, auf das kein Ingenieur gekommen wäre, das die Vorgaben aber mindestens so gut erfüllte wie eine von Hand entworfene Antenne (in späteren Versuchen sogar besser).
• Pläne und Logistik. Stundenpläne, Schichtpläne oder die Anordnung eines Lagers — Aufgaben mit vielen Bedingungen, bei denen sich die Fitness berechnen lässt, ein exakter Algorithmus aber ewig laufen würde.
• Maschinelles Lernen. Die Evolution stimmt Hyperparameter von Modellen ab und in der Neuroevolution, der der Lehrplan einen eigenen Teil widmet, auch Gewichte und Architekturen neuronaler Netze.
• Evolution mit Sprachmodellen. Systeme wie FunSearch (2023) und AlphaEvolve (2025) von Google DeepMind halten eine Population von Programmen und verwenden als Mutation ein Sprachmodell, das ein Programm abändert. Die Selektion übernimmt eine automatische Bewertung. So ließen sich neue mathematische Konstruktionen und schnellere Algorithmen finden.

9. Zusammenfassung

• Ein genetischer Algorithmus verbessert eine ganze Population von Lösungen: durch Selektion der tauglichen, durch Kreuzung und durch Mutation.
• Die Fitness ist das Einzige, was er über die Aufgabe wissen muss; verletzte Bedingungen lassen sich mit einer Strafe behandeln.
• Die Turnierselektion hält den Selektionsdruck aufrecht, der Elitismus lässt die beste Lösung nicht verloren gehen.
• Bei einem Rucksack mit 16,7 Millionen Möglichkeiten fand er das Optimum in 88 von 100 Läufen nach der Bewertung von 2 440 Rucksäcken; die Zufallssuche mit demselben Budget kein einziges Mal.
• Die Mutation liefert Vielfalt — ohne sie konvergiert die Population vorzeitig. Die Kreuzung setzt gute Bausteine zusammen und beschleunigt die Evolution.

Willst du es selbst ausprobieren? Lass einen KI-Agenten einen genetischen Algorithmus für deinen eigenen Wanderrucksack schreiben — und versuche dann, die Mutation auszuschalten, das Turnier zu vergrößern oder die Population zu verkleinern, und beobachte, was mit der Vielfalt geschieht.

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