Genetischer Algorithmus
Genetische Algorithmen (GA) sind heuristische Optimierungsverfahren und gehören zu den Evolutionären Algorithmen. Sie werden vor allem für Probleme eingesetzt, für die keine geschlossene Lösung vorliegt und stehen in Konkurrenz zu klassischen Suchstrategien wie A*-Suche, TABU-Suche oder Gradientenabstiegsverfahren.Im Gegensatz zur Genetischen Programmierung ist das Verfahren der Genetischen Algorithmen recht unflexibel. Es werden im Normalfall lediglich die Parameter einer Gleichung, Formel oder eines in anderer Form vorgegebenen strukturierten Lösungsansatzes optimiert.
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:
- Initialisierung: Erzeugen (engl. "generate") einer ausreichend großen Menge unterschiedlicher "Individuen" (Lösungsvarianten).
- Evaluation: Für jede einzelne Lösung wird anhand einer Zielfunktion (auch Fitness-Funktion) ein Wert bestimmt.
- Selektion: Zufällige Auswahl von Lösungen aus der vorhandenen Lösungsmenge. Dabei werden Lösungen mit besseren Zielfunktionswerten mit einer höheren Wahrscheinlichkeit ausgewählt.
- Rekombination: die Werte verschiedener Individuen werden gemischt und aus den neuen Parametern eine neue Generation von Individuen erzeugt (Vermehrung)
- Mutation: Zufällige Veränderung der Wertekombinationen der Individuen der neuen Generation.
- 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.
- 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