Genetische Algorithmen (GA)


(Contents)(Previous)(Next)

Genetische Algorithmen nehmen zunächst die biologische Unterscheidung Genotyp Phänotyp ernst. Dabei repräsentiert üblicherweise ein Bitstring den Genotyp eines Individuums. Im Bitstring können verschiedenartigste Objekte codiert sein. Diese Codierung entspricht dem Übergang von Genotyp zum Phänotyp. Bei der Parameteroptimierung kann ein Ort im Parameterraum auf unterschiedlichste Art und Weise in einen Bitstring codiert werden.

Übungsaufgabe: Schlage verschiedene Codierungen von reellen Vektoren in Bitstrings vor und überlege mögliche Konsequenzen.

Im Prinzip produziert ein GA Bitstrings. Diese werden decodiert und bewertet, d.h. sie erhalten einen Fitnesswert. Der GA verwendet dann die Fitnessinformation wie bei EA üblich. Decodierung und Bewertung sind anwendungsspezifisch. Im folgenden betrachten wir die einzelnen Schritte eines GA etwas genauer.

Zuerst muss eine Population von n Individuen initialisiert werden, d.h., es werden mit Zufallsgeneratoren n Bitstrings erzeugt. Die Länge l der Bitstrings ist anwendungsspezifisch, hat aber normalerweise einen festen Wert. Gehört die Decodierung nicht zum GA, sondern zum Anwendungsprogramm, so "weiss" der GA nichts über die Bedeutung der einzelnen Bits, alle Bits sind für ihn also völlig gleichwertig. Der GA übergibt die Bitstrings dem Anwendungsprogramm zur Bewertung. Er erhält lediglich einen Fitnesswert für jeden Bitstring zurück.

Nun gibt es verschiedene Fortsetzungsmöglichkeiten. Üblicherweise wird eine neue Generation von Individuen erzeugt, indem Elternpaare selektioniert werden. Pro Elternpaar werden meist zwei Kinder mittels "Crossover" erzeugt. Mit einer meist recht kleinen Wahrscheinlichkeit werden die Kinder mutiert, d.h. einzelne ihrer Bits werden invertiert. Die Kinder bilden die neue Generation und die alte Generation wird vollständig gelöscht.

Übungsaufgabe: Schlage verschiedene Varianten zur Bildung einer neuen Generation vor und überlege deren Vor- und Nachteile. Warum ist wohl die oben ausgeführte Variante besonders beliebt?

Wie bei allen EA, gibt es verschiedene Selektionsmethoden. Wichtig ist, dass erfolgreiche Eltern (mit hoher Fitness) bevorzugt werden, dass dies aber nicht zu strikt gehandhabt wird, da sonst die Diversität der Population zu rasch abnimmt.

Übungsaufgabe: Was passiert, wenn beispielsweise das dritte Bit in den Bitstrings aller Individuen einer Generation denselben Wert hat? Was kann daraus geschlossen werden?

Wird die alte Generation vollständig gelöscht, so findet man oft, dass die maximale Fitness von einer zur nächsten Generation abnimmt. Um dies zu verhindern, lässt man zumindest das beste Individuum überleben. Dies wird Elitismus genannt.

Übungsaufgabe: Überlege verschiedene Varianten von Elitismus.

Beim Erzeugen von Kindern zweier Eltern (A und B) werden im Prinzip einzelne Bits von A und B ausgetauscht, was zu den Kindern A' und B' führt. Auch hier gibt es verschiedene Varianten. Am einfachsten wird ein Schnittpunkt innerhalb der Bitstrings rein zufällig bestimmt. Die l1 Bits vor dem Schnittpunkt werden von A auf A' und von B auf B' übertragen, während die l2 Bits nach dem Schnittpunkt von A auf B' und von B auf A' übertragen werden. Da die beiden Längen meist unterschiedlich sind, ist jeweils ein Kind einem der Eltern ähnlicher als dem andern. Zuverlässigere Aussagen kann man hier aber nur machen, wenn die Bedeutung der einzelnen Bits, d.h. die Codierung bekannt ist.

Elter A: 11100110 Elter B: 00111000

Crossover nach Bit 3

Kind A' : 11111000 Kind B': 00100110

Figur: Crossover mit einem Schnittpunkt

Übungsaufgabe: Statt einem einzigen Schnittpunkt kann man natürlich mehrere Schnittpunkte definieren und damit die Bitstrings in mehrere Segmente unterteilen. Im Extremfall erhält man sogenannten "uniform crossover" mit l Segmenten der Länge 1. Überlege Vor- und Nachteile der verschiedenen Varianten.

GA Mutationsoperatoren sind trivial. Dabei wird mit einem Zufallsgenerator die Position des zu invertierenden Bits ausgewählt. Fast immer erweisen sich recht niedrige Mutationsraten als erfolgreich. Trotzdem sollte auf die Mutation nicht gänzlich verzichtet werden, da sonst die Gefahr besteht, dass sich die gesamte Population auf ein lokales Optimum konzentriert und davon nicht mehr loskommt. Da grössere Mutationsraten diese Gefahr bannen, aber gleichzeitig den Suchvorgang verlangsamen, kann man die Mutationsrate im Suchverlauf dynamisch ändern, was im Prinzip einer Teperaturanpassung bei SA entspricht. Dabei ist es nötig, Kriterien für die Änderung der Mutationsrate zu finden. Ein einfaches Kriterium ergibt sich beispielsweise aus dem Quotienten q=(mittlere Fitness)/(maximale Fitness) einer Population. Ist q nahe bei 1, so haben die meisten Individuen eine ähnlich grosse Fitness und es besteht die Gefahr, dass sie sich auf ein lokales Optimum konzentrieren. Die Mutationsrate ist also vermutlich zu erhöhen.

Übungsaufgabe: Selbst wenn alle Individuen einer Population nahezu dieselbe Fitness haben kann die Diversität einer Population gross sein und damit kein Anlass zur Erhöhung der Mutationsrate gegeben sein. Schlage bessere Kriterien zur Anpassung der Mutationsrate vor. Was sind deren Vor- und Nachteile?

Ist die Population gross und die Fitnessberechnung aufwendig, so dauert es relativ lange bis der GA einigermassen brauchbare Individuen erzeugt hat. Bei Ingenieurproblemen möchte man darum lieber mit recht kleinen Populationen arbeiten. Diese bieten aber bei komplizierten Problemen die Gefahr dass unbrauchbare, lokale Optima angepeilt werden. Abhilfe können sogenannte Mikro-GAs schaffen, welche mit kleinen Populationen arbeiten, welche nach wenigen Generationen jeweils neu gestartet werden.

Übungsaufgabe: Schlage verschiedene Varianten von Mikro-GAs vor.

Bei Parameteroptimierungsproblemen in hochdimensionalen Räumen werden die Bitstrings insbesondere dann sehr lange, wenn eine hohe Genauigkeit erforderlich ist. Das führt zu verschiedenen Problemen welche durch Übergang von Bitstrings zu Zahlenarrays oder komplizierteren Objekten zumindest gemildert werden können. Dadurch kann die Codierung vereinfacht werden und es ergibt sich eine natürlichere Zuordnung des Genotyps zum Phänotyp. Ausserdem wird beispielsweise die Initialisierung schneller, da übliche Zufallsgeneratoren reelle Zahlen im Intervall 0…1 erzeugen.

Übungsaufgabe: Vergleiche drei GA Varianten für die Parameteroptimierung, welche 1) mit Bitstrings, 2) mit Integer Arrays, 3) mit Arrays von reellen Zahlen arbeiten.

Übungsaufgabe: Wie verändert sich wohl das Suchverhalten eines GA, wenn mit mehr als zwei Eltern gearbeitet wird?

Übungsaufgabe: Überlege weitere Verallgemeinerungen des Standard GA sowie Möglichkeiten einen GA mit deterministischen Suchalgorithmen zu kombinieren.


(Contents)(Previous)(Next)