Optimierungsmethoden - Genetische Algorithmen

Author: Hans Lohninger

Verschiedenste Versuche wurden gestartet, um die Vorteile von deterministischen Methoden und Zufallssuchmethoden zu kombinieren. Ein besonderer Ansatz dazu, der in den vergangenen Jahren untersucht wurde, sind genetische Algorithmen.

Diese Methode nützt die Prinzipien der Genetik für die Optimierungstheorie aus. Zuerst wird eine Grundbestand von "Kundschaftern" kreiert. Diese "Kundschafter" werden zufällig im Suchraum (= Phasenraum) positioniert. Jeder Kundschafter (in der Terminologie des genetischen Algorithmus: Individuum) stellt den Wert der Response-Funktion an seinem eigenen Platz fest und gibt ihn an eine Wertungsfunktion weiter. Die Wertungsfunktion ist so angelegt, dass sie maximiert wird, sobald das Ziel der Suche erreicht ist. Abhängig vom Wert der Wertungsfunktion werden verschiedene Basisoperationen durchgeführt:

Selektion	Selektion der k besten Kundschafter des Grundbestands. Diese ausgewählten Kundschafter werden weiter bearbeitet.
Kombination	Die ausgewählten Kundschafter werden mit anderen Individuen des Grundbestands gekreuzt. Die Auswahlstrategie der Kreuzungspartner kann von Implementierung zu Implementierung variieren. Die Nachkommen der Paare ersetzen die Individuen des Grundbestands, die am schlechtesten gearbeitet haben (in Bezug auf die Wertungsfunktion).
Crossover	Crossover bedeutet Austausch von genetischer Information zwischen zwei gekreuzten Individuen. Dahinter steht die Idee, ein "Kind" zu schaffen, das bessere Eigenschaften (bezüglich der Wertungsfunktion) als die Eltern aufweist. Wenn beide Eltern einem Optimum nahe sind, tendiert diese Strategie dazu, ein Hill-Climbing auszuführen.
Mutation	Mutation bedeutet, dass zur Position des Kundschafters im Phasenraum zufällige Fluktuationen hinzugefügt werden. Das Ergebnis daraus ist, dass zufällige Sprünge zu anderen Positionen mit einer gewissen niedrigen Wahrscheinlichkeit möglich werden.

Diese Schritte werden wiederholt, bis ein bestimmtes Abbruchkriterium erfüllt ist (z.B. der beste Kundschafter hat einen festgelegten Grenzwert der Wertungsfunktion erreicht) oder eine festgelegte Zahl an Generationen berechnet wurde. Letzteres wird oft angewendet, wenn keine Information über das globale Optimum vorhanden ist.

Der bedeutendste Vorteil der genetischen Algorithmen ist ihre Fähigkeit, ein Optimum in einem riesigen Suchraum zu finden. Tatsächlich sind genetische Algorithmen nur in Systemen mit sehr großen Suchräumen effizient. Ein Nachteil der genetischen Algorithmen ist ihr hoher Anspruch an die Rechenleistung. Als Konsequenz der hohen Anzahl an notwendigen Auswertungen der Wertungsfunktion muss jede einzelne Berechnung "billig" sein (im Sinne des Aufwands, die zu optimierende Größe für eine bestimmte Position zu erhalten).