Was ist ein Genetischer Algorithmus?
Ein Genetischer Algorithmus (GA) ist eine Metaheuristik, die Lösungen nach dem Vorbild der natürlichen Evolution entwickelt: Eine Population von Kandidatenlösungen wird über Generationen hinweg durch Selektion, Kreuzung und Mutation verbessert. Der Grundstein wurde 1975 von John Holland in „Adaptation in Natural and Artificial Systems" gelegt; verbreitet wurde die Idee durch David Goldberg und die Forschungsgruppe um die Evolutionären Algorithmen ab den 1980er-Jahren.
Wie funktioniert er?
Jede Kandidatenlösung wird als Chromosom kodiert – typischerweise als Bitstring, als Permutation oder als Vektor reeller Zahlen. Die einzelnen Stellen heißen Gene. Eine Fitnessfunktion bewertet, wie gut eine Lösung das Problem löst. Der Ablauf pro Generation:
- Selektion: Lösungen werden nach ihrer Fitness ausgewählt – etwa per Roulette-Rad (Wahrscheinlichkeit proportional zur Fitness), Turnier-Selektion oder Ranking. Die besten Individuen werden oft per Elitismus unverändert übernommen.
- Crossover (Rekombination): Zwei Eltern tauschen Genmaterial (Ein-Punkt-, Zwei-Punkt- oder uniformes Crossover) und erzeugen Nachkommen.
- Mutation: Gene werden mit kleiner Wahrscheinlichkeit zufällig verändert – typisch etwa 1 % pro Gen. Sie sichert die genetische Vielfalt und verhindert zu frühe Konvergenz.
Die neue Generation ersetzt die alte, bis eine Abbruchbedingung erreicht ist (maximale Generationszahl, ausreichende Fitness oder Konvergenz der Population). Typische Parameter: Populationsgröße 50–500, Crossover-Rate etwa 0,7–0,9, Mutationsrate etwa 1/Genlänge.
Wofür wird er eingesetzt?
Genetische Algorithmen eignen sich für große, raue Suchräume ohne analytisch nutzbare Struktur: Näherungslösungen für das Handelsreisendenproblem (TSP), Job-Shop-Scheduling, Hyperparameter-Tuning im maschinellen Lernen, Feature-Selection und Neuroevolution. Sie liefern keine Garantie für das globale Optimum – die Komplexität bleibt praktisch abhängig von Fitness-Evaluierung und Populationsgröße (vergleiche Big-O-Notation). Als probabilistische Heuristik findet er sehr gute Lösungen, wo exakte Verfahren an NP-vollständigen Problemen scheitern.
Abgrenzung zu verwandten Verfahren
Anders als Simulated Annealing (Einzel-Lösung mit Abkühlplan) oder die Tabu-Suche (Einzel-Lösung mit Gedächtnis) arbeitet der GA mit einer ganzen Population parallel. Er ist damit robuster gegen lokale Optima, aber auch rechenintensiver. Einfache lokale Suche (Hill-Climbing) und klassische Greedy-Algorithmen haben kein solches Explorationsverhalten. Grundlegende Konzepte dazu: Algorithmus und Backtracking.