Genetische Algorithmen (GA) sind heurisitsche Optimierungsverfahren. Sie werden vor allem für Probleme eingesetzt, für die keine geschlossene Lösung vorliegt und stehen in Konkurrenz zu klassischen Suchstrategieen wie A-Star-Suche, TABU-Suche oder Gradientenabstiegsverfahren.
Die Grundidee ist, ähnlich der biologischen Evolution eine Anzahl Lösungskandidaten (Individuen) zufällig zu erzeugen und diejenigen auszuwählen, die einem bestimmten Gütekriterium am besten entsprechen. Deren Eigenschaften (Parameterwerte) werden dann leicht verändert und miteinander kombiniert, um eine neue Lösungskandidaten (eine neue Generation) zu erzeugen.
Der typische GA umfasst die folgenden Schritte:
- Erzeugen (engl. "generate") einer ausreichend großen Menge unterschiedlicher "Individuen" (Lösungsvarianten).
- Für jede einzelne Lösung wird aufgrund einer Zielfunktion ein Wert bestimmt.
- Auswahl derjenigen Lösungen, die die besten Zielfunktionswerte haben.
- Zufällige Veränderung der Wertekombinationen der Gewinner (Mutation) und Rekombination (die Werte verschiedener Individuen werden gemischt).
- Die veränderten Nachfolger der Gewinner der ursprünglichen Menge bilden nun die Menge der neuen Individuen und der Algorithmus wird ab Schritt 2 wiederholt.
Im Allgemeinen unterscheidet man zwei Typen von genetischen Algorithmen,
- die Evolutionsstrategie (ES) nach Rechenberg, I. und Schwefel, H.P. und
- den Genetic Algorithm (GenA) nach Holland, J.H. und Goldberg, D.E.
siehe auch: Algorithmus