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:

1. Initialisierung: Erzeugen (engl. "generate") einer ausreichend großen Menge unterschiedlicher "Individuen" (Lösungskandidaten).
2. Evaluation: Für jeden einzelnen Lösungskandidat wird anhand einer Zielfunktion (auch Fitness-Funktion genannt) ein Wert bestimmt.
3. Selektion: Zufällige Auswahl von Lösungskandidaten aus der vorhandenen Lösungskandidatenmenge. Dabei werden Lösungskandidaten mit besseren Zielfunktionswerten mit einer höheren Wahrscheinlichkeit ausgewählt.
4. Rekombination: die Genome verschiedener Individuen werden gemischt und aus den neuen Parametern eine neue Generation von Individuen erzeugt (Vermehrung)
5. Mutation: Zufällige Veränderung der Wertekombinationen der Individuen der neuen Generation.
6. Nach einem bestimmten Verfahren wird die Menge der neuen Individuen aus der Menge der alten Individuen und der Menge der mutierten Nachfolger der Gewinner der Menge der alten Individuen gebildet. Der Algorithmus wird anschließend ab Schritt 2 wiederholt, oder nach einem Abbruch-Kriterium beendet und der beste verfügbare Lösungskandidat als Lösung definiert.

Im Allgemeinen unterscheidet man zwei Typen von genetischen Algorithmen,

1. die Evolutionsstrategie (ES) nach Rechenberg, I. und Schwefel, H.P. und
2. den Genetic Algorithm (GenA) nach Holland, J.H. und Goldberg, D.E.

Eine theoretische Untersuchung des Konvergenzverhaltens liefert der Schemasatz von Holland, J.H..

Siehe auch: Algorithmus

Beispiele

Beispiel 1

"Festlegungen" eines konkreten genetischen Algorithmus':

• Sei eine Fitness-Funktion, die wie folgt definiert ist:
• Als Genom eines Individuums nehmen wir (hier) einfach die Variablen der Fitness-Funktion, also die Liste
• Ziel ist es, die Fitness-Funktion f zu minimieren, also eine Eingabe zu finden, sodass die Funktion einen möglichst niedrigen Wert zurückliefert.
• Als Rekombination wählen wir ein einfaches Crossover mit 2 Eltern-Genomen, wobei die Eltern aus der alten Population zufällig gewählt werden:
  • Wir wählen (zufällig) eine Position .
  • Das Kind-Genom wird zusammengesetzt aus den beiden Eltern-Genomen, indem p viele vordere Allele des Genoms des einen Elternteils und 5 - p viele hintere Allele des Genoms des anderen Elternteils kopiert werden.
  • Sind Beispielsweise die Eltern-Genome und sowie p = 2, dann ist das Kind-Genom .
• Als Mutation wählen wir für jede Position im Genom eine einfache Addition an dieser Position um eine Zahl . Diese Mutation komme mit einer Wahrscheinlichkeit von 1% pro Generationswechsel und Position vor.
• Die Selektion sei wie folgt: Von der gemeinsamen Population von Eltern und Kindern werden die entsprechend der Fitness-Funktion besten ausgewählt, und zwar so viele, wie es Individuen in der ursprünglichen Eltern-Population gab.
• Startpopulation:
  • Sie bestehe aus 50 Individuen.
  • Jedes Individuum bekommt für jedes seiner Gene eine zufällige Zahl aus zugeordnet.
• Abbruchkriterium: Wir brechen das Berechnen der Generationenfolge ab, wenn sich über die letzten 10 Generationen der Durchschnitt der Fitness aller Individuen der jeweiligen Population nicht geändert hat.
• Ausgabe des genetischen Algorithmus ist das Genom eines besten Individuums in der letzten Population (die Population zu der Zeit, wann abgebrochen wurde).

Lässt man diesen genetischen Algorithmus laufen, so wird man nach etwa 70 Generationen ein Ergebnis haben, für das gilt: a = b = c = d = e. Dieses Ergebnis ist in diesem konkreten Fall optimal. Man sieht, dass es viele gleichwertige Ergebnisse geben kann, so z.B. oder .

Weblinks

• http://math.hws.edu/xJava/GA/ Automatische Programmierung von Herbivoren in einer virtuellen Pflanzen-Umgebung
• FH Augsburg: Einführung in Genetische Algorithmen (http://www.fh-augsburg.de/informatik/projekte/emiel/GenAlg/Inhalt.html)