Der Genetische Algorithmus verständlich erklärt

Statt eine einzelne Lösung Schritt für Schritt zu verbessern, hält der Genetische Algorithmus eine ganze Gruppe von Lösungen und lässt sie über viele Runden besser werden: durch Auswahl, Kreuzung und Mutation. Diese Seite erklärt zuerst ohne Formeln, was jeder der drei Bausteine beiträgt und wo die Gruppe hängen bleibt, danach für Fachleute mit Modell, Formeln, Messwerten und Grenzen. Die zugehörige Demo lässt sich ausprobieren.

Zuletzt aktualisiert: 28. Oktober 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Eine Gruppe statt einer einzelnen Lösung

Stellen Sie sich einen Lieferwagen vor, der von einem Depot aus viele Kundinnen und Kunden beliefern soll. Gesucht ist die Reihenfolge, in der er sie anfährt, damit die Fahrt möglichst kurz wird. Mit jedem weiteren Stopp wächst die Zahl der möglichen Reihenfolgen so schnell, dass sich bei vielen Stopps nicht mehr alle durchprobieren lassen.

Der naheliegende Weg ist, eine Reihenfolge zu nehmen und sie in kleinen Schritten zu verbessern. Der Genetische Algorithmus geht anders vor. Er hält gleichzeitig eine ganze Gruppe von Reihenfolgen, die Population, und verbessert diese Gruppe in vielen Runden. Jede Runde heißt Generation. Das Vorbild ist die Evolution, aber nur als Anleihe: Es gibt keine Biologie, nur Lösungen, die sich bewerten lassen. Niedrigere Kosten, hier also eine kürzere Tour, sind besser.

Drei Bausteine, die in jeder Runde zusammenarbeiten

Erster Baustein ist die Auswahl (Selektion). Einige Mitglieder der Gruppe treten gegeneinander an, und die Lösung mit den geringsten Kosten gewinnt und wird Elternteil. Bessere Lösungen werden so öfter Eltern, aber auch mittelmäßige haben eine Chance, denn nur ein Teil der Gruppe tritt jeweils an.

Zweiter Baustein ist die Kreuzung (Crossover). Zwei Eltern ergeben ein Kind, das Merkmale beider mischt. Bei der Lieferroute übernimmt das Kind ein zusammenhängendes Stück der Route des einen Elternteils und füllt den Rest in der Reihenfolge des anderen auf. So bleibt jeder Kunde genau einmal in der Route.

Dritter Baustein ist die Mutation: Mit kleiner Wahrscheinlichkeit wird ein Kind zufällig verändert, bei der Route etwa durch das Vertauschen zweier Stopps. Dazu kommt der Elitismus: Die besten Mitglieder wandern unverändert in die nächste Generation, damit ein guter Fund nicht durch Zufall verloren geht.

Was jeder Baustein beiträgt

Die Auswahl gibt der Suche eine Richtung: Gute Merkmale verbreiten sich in der Gruppe. Die Kreuzung kombiniert, was verschiedene Lösungen jeweils schon gut können, zu neuen Lösungen, die keiner der Eltern allein hatte. Die Mutation bringt Neues hinein, das in der Gruppe noch gar nicht vorkam. Ohne sie bleibt die Gruppe auf das beschränkt, was sie am Anfang zufällig mitbekommen hat.

Die Demo prüft das mit kleinen Gruppen und wenigen Runden. Nur dann zeigen sich die Unterschiede, denn bei viel Rechenzeit gleicht sich vieles aus. Ganz ohne Mutation, also ganz ohne zufällige Veränderung der Kinder, schneidet die Gruppe in der Demo am schlechtesten ab. Gibt es überhaupt Mutation, spielt es in der Demo kaum eine Rolle, wie oft sie vorkommt. Ganz ohne Kreuzung, wenn also jedes Kind nur eine veränderte Kopie eines Elternteils ist, ist das Ergebnis dort ebenfalls schlechter als bei ständiger Kreuzung, wenn also jedes Kind aus zwei gemischten Eltern entsteht. Nicht jedes Kind ist besser als seine Eltern, doch zusammen verbessern die drei Bausteine in der Demo eine zufällig erzeugte Startgruppe spürbar. Wie stark, steht im Fachteil.

Wo die Gruppe hängen bleibt

Die Demo zeigt das Verfahren auch an einer zweiten Aufgabe, die ganz anders aussieht: Wo soll ein Verteilzentrum stehen? Hier sucht die Gruppe keine Reihenfolge, sondern Orte auf einer Karte, und jeder Ort hat Kosten. An mehreren Orten sind die Kosten günstiger als in ihrer Umgebung, aber nur ein Ort ist insgesamt der günstigste. Die übrigen heißen lokale Minima: Von dort aus sieht jeder kleine Schritt nach schlechter aus, obwohl an anderer Stelle der Karte eine bessere Lösung liegt.

Ist die Gruppe klein, werden ihre Mitglieder einander schnell ähnlich. Sie haben dann ihre Vielfalt verloren, bevor sie den günstigsten Ort gefunden haben, und sammeln sich an einem schlechteren. Fachleute sprechen von vorzeitiger Konvergenz. Eine größere Gruppe probiert mehrere Orte gleichzeitig aus, bevor sie sich festlegt. Die Demo lässt das Verfahren mehrfach mit neuem Zufall laufen: Eine größere Gruppe findet den günstigsten Ort dabei öfter als eine kleine; die Anteile stehen im Fachteil.

Wie ernst ist das Modell zu nehmen?

Die Demo ist ein stark vereinfachtes Beispiel: Die Stopps und die Standortkosten sind zufällig erzeugte Werte, keine echten Daten, und die Raten der Bausteine stellt man von Hand ein, das Verfahren lernt sie nicht aus dem Verlauf. Sie zeigt, wie die Bausteine zusammenwirken, nicht wie gut ein Genetischer Algorithmus auf einer bestimmten echten Aufgabe wäre.

Für eine Entscheidung nehmen Sie mit: Ein Genetischer Algorithmus ist in der Demo deutlich besser als reines Raten, aber es gibt keine Garantie, wie nah er am Besten liegt. Er kommt in Frage, wenn es sehr viele mögliche Lösungen gibt und sich eine Lösung zwar bewerten, die beste aber nicht ausrechnen lässt. Lässt sich die Aufgabe dagegen vollständig durchrechnen, wie in der Demo bei wenigen Stopps, ist ein Verfahren vorzuziehen, das alle Möglichkeiten prüft, denn es findet das Beste sicher. Ob die Gruppe zu klein ist, zeigt in der Demo die Vielfalt am Ende: Sinkt sie schon lange vor der letzten Runde auf fast null, wurde die Suche zu früh eingeengt. Dann hilft eine größere Gruppe; auch Mutation hält die Gruppe vielfältiger.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er fasst die formale Beschreibung der Demo zusammen; die vollständige Fassung steht im Expander „📐 Mathematische Formulierung“ der Demo.

• Lieferroute (diskret): ein Depot in der Mitte und \(n\) Kundenstopps in einem 100 × 100-km-Gebiet, euklidische Entfernungen, eine Rundtour. Jedes Stopp-Paar hat einen unabhängig gezogenen CO2-Faktor (0,6–3,4) für die Kante zwischen beiden; die Kosten sind eine gewichtete Summe aus Distanz und CO2 (Gewicht 0 = reine Distanz). Kodierung als Permutation, Order Crossover und Tausch-Mutation.
• Standortwahl (kontinuierlich): Lage \((x, y)\) eines Verteilzentrums im selben Gebiet. Die Kosten sind eine Summe mehrerer Gauß-Mulden unterschiedlicher Tiefe und Breite; nur die tiefste ist die global günstigste Lage, die übrigen sind lokale Minima. Kodierung reellwertig, BLX-α-Crossover und Gauß-Mutation.
• Gemeinsam: Turnierselektion (\(k\) Kandidaten, der beste gewinnt), Elitismus (die besten \(e\) Individuen überleben unverändert), Crossover mit Wahrscheinlichkeit \(p_c\), Mutation mit Wahrscheinlichkeit \(p_m\) je Kind (Route) bzw. je Koordinate (Standort). Die Raten sind feste, von Hand gewählte Regler.
• Referenz: Brute-Force über alle Touren bis 8 Stopps plus Depot (8! = 40 320 Touren); bei der Standortwahl ein Gitter mit 1-km-Schritten. Bei mehr als 8 Lieferstopps gibt es keine schnell berechenbare exakte Referenz, dann misst die Demo nur die Verbesserung gegenüber der Startpopulation.

Die Formeln

Die Population in Generation \(t\) ist \(P_t = \{x_1, \dots, x_{\mu}\}\); bei der Lieferroute ist \(x_i\) eine Permutation der \(N\) Knoten, bei der Standortwahl \(x_i \in [0, A]^2\). Die Fitness der Route ist die Tourlänge, also die Summe der Entfernungen \(d\) zwischen aufeinanderfolgenden Knoten \(\pi(k)\) und \(\pi(k+1)\) der Tour; niedriger ist besser:

\[f(x) = \sum_k d_{\pi(k)\,\pi(k+1)}\]

Mit CO2 als zweitem Ziel ergibt sich aus Distanzkosten \(f_{\text{dist}}\) und CO2-Kosten \(f_{\text{CO2}}\) bei Gewicht \(w\) die gewichtete Summe. Sie kann nur den konvexen Teil der Pareto-Front erreichen, wie fein man \(w\) auch durchfährt:

\[f_w(x) = (1-w) \cdot f_{\text{dist}}(x) + w \cdot f_{\text{CO2}}(x)\]

Die Kosten der Standortwahl sind eine Summe von \(K\) Gauß-Mulden der Tiefe \(A_j\) und der Breite \(\sigma_j\) um die Mittelpunkte \(c_j\), mit \(C = \sum_j A_j\):

\[f(x, y) = C - \sum_{j=1}^{K} A_j \exp\!\left(-\frac{(x - c_{j,x})^2 + (y - c_{j,y})^2}{2\sigma_j^2}\right)\]

Der Crossover der Standortwahl zieht jede Koordinate \(c\) des Kindes gleichverteilt aus dem Intervall zwischen den entsprechenden Koordinaten \(x_1, x_2\) der Eltern, um den Faktor \(\alpha\) über beide hinaus gedehnt, und kappt auf die Gebietsgrenzen (BLX-α):

\[c \sim \mathcal{U}(\min(x_1, x_2) - \alpha\,|x_1 - x_2|,\; \max(x_1, x_2) + \alpha\,|x_1 - x_2|)\]

Order Crossover übernimmt zu zwei Positionen \(i < j\) das Stück \(x_1[i{:}j]\) wörtlich und füllt die übrigen Positionen in der Reihenfolge von \(x_2\) mit den fehlenden Knoten auf; das Ergebnis ist stets eine gültige Permutation. Die Mutation vertauscht bei der Route mit Wahrscheinlichkeit \(p_m\) zwei Positionen, beim Standort addiert sie je Koordinate mit Wahrscheinlichkeit \(p_m\) einen normalverteilten Wert mit fester Streuung. Als Vielfaltsmaß dient bei der Route der Anteil verschiedener Kanten über Paare der Population (0 = identische Touren), beim Standort der mittlere Abstand vom Populationsschwerpunkt.

Befunde

Alle Zahlen stammen aus den Messungen der Demo (jede steht in deren Tests, tests/test_claims.py). Die Voraussetzungen stehen jeweils dabei. Die Verbesserung gegenüber der Startpopulation (erste Zeile) ist keine Aussage über den Abstand zum Optimum, den es bei 30 Stopps nicht zu messen gibt.

Frage	Befund
Verbessert der GA die Startpopulation deutlich?	Standardfall (30 Stopps, Population 60, 150 Generationen): beste Tour 1434 km → 733 km (48,9 % kürzer).
Verliert eine kleine Population zu früh an Vielfalt?	Standortwahl, je 20 GA-Läufe: Bei Populationsgröße 10 landen 55 % der Läufe im globalen Trichter, bei Populationsgröße 100 sind es 95 %.
Trifft eine feste Gewichtung die Pareto-Front?	Bei 8 Stopps hat die Brute-Force-Front 8 Punkte; über 8 verschiedene Gewichte (je 5 GA-Seeds) werden nur 4 von 8 getroffen.
Wie stark schadet Mutationsrate 0?	Standortwahl, knappes Budget (Population 20, 25 Generationen), Mittel über 20 GA-Seeds: Mutationsrate 0 hat die höchsten Kosten (das schlechteste Ergebnis); jede positive Rate liefert deutlich niedrigere Kosten, und die positiven Raten unterscheiden sich untereinander kaum. Crossover-Rate 0 hat höhere Kosten als Crossover-Rate 1,0.
Hilft eine höhere CO2-Gewichtung?	Gewicht 0,4 senkt die CO2-Kosten der gefundenen Tour um 24 % gegenüber reiner Distanzminimierung; bei dieser Instanz bleibt die Distanz nahezu gleich.

Die Demo hat drei Experimente auf Abruf (vorzeitige Konvergenz, gewichtete Summe gegen Pareto-Front, Operator-Sensitivität); die Zeilen zwei bis vier stammen aus ihnen. Für die Crossover-Raten zwischen 0 und 1,0 behauptet die Demo keinen festen Verlauf; belegt ist nur der Vergleich der beiden Enden.

Grenzen

• Keine exakte Referenz oberhalb von 8 Lieferstopps: Der Abstand zum Optimum lässt sich bei der Standardinstanz (30 Stopps) nicht direkt messen, nur die Verbesserung gegenüber der Startpopulation.
• Feste, von Hand eingestellte Operatorraten: Der GA lernt nicht aus dem Verlauf, welche Rate gerade sinnvoll ist. Das behebt CMA-ES.
• Eine gewichtete Summe für mehrere Ziele: Sie erreicht nur den konvexen Teil der Pareto-Front. Das behebt NSGA-II.
• Keine gerichtete Bewegung: Jedes Individuum wird unabhängig behandelt, anders als bei der Partikelschwarm-Optimierung (Geschwindigkeit) oder dem Ameisenalgorithmus (Pheromonspur).
• Instanzen: Die Befunde gelten für die zufällig erzeugten Instanzen der Demo (Lieferroute und Standortlandschaft), nicht für beliebige Aufgaben. Wie oft die Standortwahl im globalen Trichter landet, hängt von der Landschaft ab.
• Nicht enthalten: weitere Kodierungen (etwa Baum oder Graph), adaptive Operatorraten und ein Export. Die Nachfolger der Konzepte-Reihe bringen eigene Kodierungen und Mechanismen mit.

Quellen

• Holland, J. H. (1975): Adaptation in Natural and Artificial Systems. University of Michigan Press.
• Goldberg, D. E. (1989): Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley.
• Davis, L. (1985): Applying Adaptive Algorithms to Epistatic Domains. Proceedings of the International Joint Conference on Artificial Intelligence (Order Crossover).
• Eshelman, L. J.; Schaffer, J. D. (1993): Real-Coded Genetic Algorithms and Interval-Schemata. In: Foundations of Genetic Algorithms 2 (BLX-α-Crossover).
• Quelltext, Messungen und Tests der Demo: github.com/sebastian-hanisch/genetic-algorithm-demo.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen und stehen nicht in der README der Demo.