Zum Inhalt springen
Zurück zu den Suchergebnissen

Genetischer Algorithmus — Evolutionäre Optimierung

Eingeführt von
John Henry Holland
Jahr
1975
Typ
Population-based metaheuristic

Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen

Schriftgröße

Was leistet sie?

Ein Genetischer Algorithmus (GA) ist eine populationsbasierte metaheuristische Optimierungsmethode, die 1975 von John Henry Holland eingeführt wurde und die Prinzipien der natürlichen Selektion nachahmt.

Er unterhält eine Population von Kandidatenlösungen und verbessert diese iterativ durch Selektions-, Kreuzungs- und Mutationsoperatoren, was ihn besonders leistungsfähig in diskontinuierlichen, nicht-konvexen und multimodalen Suchräumen macht, in denen klassische gradientenbasierte Methoden versagen.

Die Intuition hinter der Methode

Stellen Sie sich vor, Sie haben Tausende möglicher Antworten auf ein schwieriges Problem und keine Formel, um die beste zu finden. Ein Genetischer Algorithmus behandelt jede Kandidatenantwort als Individuum in einer Population. In jeder Generation behält er die fittesten Individuen, züchtet sie miteinander, um ihre guten Eigenschaften zu mischen, und mutiert gelegentlich Nachkommen, um Neuheit einzubringen. Über viele Generationen hinweg driftet die Population zu immer besseren Lösungen – nicht indem sie einem Gradienten folgt, sondern indem sie nachahmt, wie die Evolution Organismen im Laufe der Zeit formt.

Geschichte

Der Genetische Algorithmus wurde von John Henry Holland in seinem Buch 'Adaptation in Natural and Artificial Systems' (1975) eingeführt, das die Vorstellung eines Schemas (Bausteins) formalisierte und die grundlegende theoretische Analyse lieferte, warum Kreuzung und Selektion die Suche in Richtung fittester Regionen treiben. Hollands Studenten – insbesondere David Goldberg – popularisierten GAs in den 1980er Jahren durch Ingenieuranwendungen. Kalyanmoy Deb erweiterte später den Rahmen auf multiobjektive Einstellungen, was im weit verbreiteten NSGA-II-Algorithmus (2002) gipfelte. Heute bleiben GAs ein Standardwerkzeug in der evolutionären Berechnung, mit aktiver Forschung an hybriden Methoden, die evolutionäre Suche mit lokaler Verfeinerung kombinieren.

Wann wird sie eingesetzt?

Genetische Algorithmen sind geeignet, wenn der Suchraum groß, diskontinuierlich, nicht differenzierbar oder hoch multimodal ist – Bedingungen, unter denen gradientenbasierte Löser nicht operieren können oder in lokalen Optima stecken bleiben. Sie sind anwendbar auf kontinuierliche, kategoriale, binäre und ordinale Variablentypen und stellen keine Normalitäts- oder Verteilungsannahmen auf. Die einzige Anforderung ist eine berechenbare Fitnessfunktion. Für Probleme, bei denen eine analytische oder konvexe Formulierung existiert, sind klassische Methoden (lineare Programmierung, Gradientenabstieg) schneller und sollten bevorzugt werden. Ausreichende Iterationen (typischerweise weit über 1.000 Generationen) sind für eine sinnvolle Konvergenz erforderlich; zu wenige Generationen laufen zu lassen, ist die häufigste Fehlerquelle.

Grenzen und Hinweise

  • Keine Garantie der Konvergenz zum globalen Optimum; Ergebnisse können zwischen Läufen variieren.
  • Rechenintensiv: Jede Generation erfordert die Auswertung der gesamten Population, was prohibitiv ist, wenn die Fitnessfunktion langsam ist.
  • Die Leistung ist empfindlich gegenüber Hyperparameter-Wahlen – Populationsgröße, Kreuzungswahrscheinlichkeit und Mutationsrate –, die oft eine problem-spezifische Abstimmung erfordern.
  • Für glatte, konvexe oder gut strukturierte Probleme sind klassische gradientenbasierte oder lineare Methoden schneller und zuverlässiger.

Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.

Stärken

  • Funktioniert auf diskontinuierlichen, nicht differenzierbaren und multimodalen Ziellandschaften, in denen gradientenbasierte Methoden versagen.
  • Stellt keine Verteilungsannahmen auf – die einzige erforderliche Eingabe ist eine berechenbare Fitnessfunktion.
  • Behandelt natürlich eine breite Palette von Variablentypen: kontinuierlich, binär, kategorial und ordinal.
  • Populationsdiversität ermöglicht die gleichzeitige Exploration mehrerer Regionen des Suchraums und reduziert das Risiko einer vorzeitigen lokalen Optimum-Falle.
  • Hochgradig erweiterbar: domänenspezifische Kreuzungs- und Mutationsoperatoren, Handhabung von Nebenbedingungen und multiobjektive Varianten (z. B. NSGA-II) sind in der Literatur gut etabliert.

Anwendungen

  • Optimierung im Ingenieurwesen: Finden optimaler Parameterkonfigurationen für Strukturen, Schaltungen oder mechanische Systeme.
  • Planungs- und Routenprobleme: Job-Shop-Scheduling, Fahrzeugrouting und Stundenplanerstellung, bei denen der kombinatorische Suchraum für eine erschöpfende Suche zu groß ist.
  • Maschinelles Lernen: Hyperparameter-Tuning, neuronale Architektursuche und Merkmalsauswahl.
  • Operations Research: Optimierung von Lieferketten, Portfolioallokation und Ressourcenzuweisung unter komplexen Nebenbedingungen.
  • Bioinformatik: Sequenzabgleich, Vorhersage von Proteinstrukturen und Inferenz von Genregulationsnetzwerken.

So funktioniert es

So funktioniert es

1

Eine Population von Kandidatenlösungen (Individuen) wird erstellt, typischerweise zufällig innerhalb des Suchraums. Jedes Individuum kodiert eine potenzielle Lösung – zum Beispiel als Binärstring, reellwertigen Vektor oder Permutation – und die Populationsgröße ist ein wichtiger Parameter, der bestimmt, wie breit der Suchraum von Anfang an abgetastet wird.

2

Jedes Individuum in der Population wird durch eine Fitnessfunktion bewertet, die quantifiziert, wie gut diese Lösung im Verhältnis zum Problemziel ist. Die Fitnessfunktion ist die einzige domänenspezifische Komponente, die der Benutzer bereitstellen muss; sie kann jedes berechenbare Maß sein – eine Simulationsausgabe, eine Kostenformel oder eine Modellfehlermetrik.

3

Individuen mit höherer Fitness werden bevorzugt ausgewählt, um Eltern für die nächste Generation zu werden. Gängige Selektionsmechanismen umfassen Turnierselektion, Roulette-Rad- (fitnessproportionale) Selektion und rangbasierte Selektion. Der Selektionsdruck steuert den Kompromiss zwischen der Ausnutzung hochwertiger Lösungen und der Aufrechterhaltung der Populationsdiversität.

4

Ausgewählte Eltern produzieren Nachkommen durch Kreuzung (Rekombination), bei der Segmente von zwei Elternkodierungen kombiniert werden, um ein neues Individuum zu bilden, und durch Mutation, bei der kleine zufällige Änderungen an einzelnen Genen vorgenommen werden. Die Kreuzungswahrscheinlichkeit und die Mutationsrate sind kritische Tuning-Parameter: zu wenig Mutation führt zu vorzeitiger Konvergenz, zu viel verwandelt die Suche in einen Zufallslauf.

5

Die Schleife aus Bewerten → Auswählen → Reproduzieren wird für eine festgelegte Anzahl von Generationen fortgesetzt oder bis ein Konvergenzkriterium erfüllt ist (z. B. keine Verbesserung über ein Fenster von Generationen). Das beste Individuum, das über alle Generationen gefunden wurde, wird als Lösung zurückgegeben. Da die Konvergenz zum globalen Optimum nicht garantiert ist, werden für kritische Probleme mehrere unabhängige Läufe empfohlen.

Häufige Fallstricke

  • Zu wenige Generationen laufen zu lassen, ist der häufigste Fehler: Bei unzureichenden Generationen konvergiert der Algorithmus nicht, daher sollten analytische oder gradientenbasierte Methoden bevorzugt werden, wenn nur ein kleines Iterationsbudget zur Verfügung steht.
  • Vorzeitige Konvergenz – der Verlust der Populationsdiversität zu früh – führt zu einem lokal optimalen, aber global suboptimalen Ergebnis; halten Sie eine angemessene Populationsgröße und Mutationsrate aufrecht, um dem entgegenzuwirken.
  • Die Verwendung einer schlecht definierten oder falsch spezifizierten Fitnessfunktion liefert irreführende Ergebnisse, unabhängig von der algorithmischen Korrektheit; validieren Sie die Fitnessfunktion unabhängig, bevor Sie den GA ausführen.
  • Die Anwendung eines GA auf ein glattes, konvexes Problem, bei dem Gradientenabstieg oder lineare Programmierung ausreichen würden, verschwendet Rechenressourcen und führt unnötige Stochastizität ein.
  • Die Berichterstattung über einen einzelnen Lauf als Lösung ohne Überprüfung der Reproduzierbarkeit; für kritische Anwendungen führen Sie den Algorithmus mehrmals aus und berichten Sie über die Verteilung der Ergebnisse.

Häufig gestellte Fragen

Wie unterscheidet sich ein Genetischer Algorithmus vom Gradientenabstieg?

Der Gradientenabstieg erfordert ein differenzierbares Ziel und folgt dem lokalen Gradienten abwärts. Ein Genetischer Algorithmus erfordert nur, dass die Fitness für jede Kandidatenlösung berechnet werden kann; er sucht durch die Entwicklung einer Population, anstatt einem Gradienten zu folgen, sodass er diskontinuierliche, nicht differenzierbare und multimodale Landschaften handhaben kann, in denen der Gradientenabstieg versagt oder stecken bleibt.

Wie viele Generationen und wie groß eine Population benötige ich?

Es gibt keine universellen Regeln; beides hängt von der Komplexität des Suchraums ab. Eine zu kleine Population oder ein zu kurzer Lauf birgt die Gefahr einer vorzeitigen Konvergenz. Als praktischer Ausgangspunkt sind Populationsgrößen von 50–200 und Generationszahlen von 100–1.000 in der Literatur üblich, aber anspruchsvolle Probleme erfordern routinemäßig mehr. Untersuchen Sie immer Konvergenzkurven, anstatt willkürliche Stoppkriterien festzulegen.

Ist ein Genetischer Algorithmus garantiert, das globale Optimum zu finden?

Nein. GAs sind Heuristiken und bieten keine Konvergenzgarantie zum globalen Optimum in endlicher Zeit. Für deterministische Garantien benötigen Sie exakte Methoden wie Integer-Programmierungs-Solver. Für kritische Entscheidungen führen Sie den GA mehrmals aus, berichten Sie über die Verteilung der Ergebnisse und vergleichen Sie die beste Lösung mit bekannten Grenzen.

Wann sollte ich einen GA einem simulierten Annealing oder einer Partikelschwarmoptimierung vorziehen?

GAs werden tendenziell bevorzugt, wenn die Lösung natürlich als kombinatorische Struktur (Permutationen, Binärstrings) kodiert ist oder wenn multiobjektive Erweiterungen benötigt werden. Die Partikelschwarmoptimierung ist oft schneller bei kontinuierlichen unimodalen Problemen. Simuliertes Annealing ist einfacher zu implementieren für kombinatorische Probleme mit einer gut definierten Nachbarschaft. In der Praxis ist es ratsam, zwei oder drei Methoden an einer kleinen Probleminstanz zu benchmarken, bevor man sich für eine entscheidet.

Verwandte Methoden

Quellen

  1. Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.

    Publikationsreferenz öffnen
    Kopiert.
  2. Deb, K. (2001). Multi-Objective Optimization using Evolutionary Algorithms. Wiley.

    ISBN: 9780471873396
    Kopiert.