Information Technology Reference
In-Depth Information
Der
genetische Code
speichert die Eigenschaften der Verarbeitungseinheit. Wie beim
natürlichen Vorbild kann eine Aufteilung in mehrere Chromosomen vorgenommen wer-
den, jedoch ist dies in der Regel nicht unbedingt erforderlich. Auf dem Chromosom sind
die einzelnen Gene lokalisiert, wobei in vereinfachender Weise eine Eins-zu-Eins Kor-
respondenz zwischen Genen und Eigenschaften (Phänen) gesetzt wird. Eine Eigenschaft
kann verschiedene Ausprägungen haben, die durch verschiedene Werte (Allele) eines
Gens kodiert werden. So wie der natürliche genetische Code aus Basenpaaren aufgebaut
ist, so muss auch für den simulierten genetischen Code eine Repräsentation - gewisserma-
ßen ein Alphabet - gewählt werden. Im klassischen genetischen Algorithmus ist dies ein
Bit-String, also einfach eine Kette, bestehend aus Nullen und Einsen. In den evolutionären
Strategien wird hingegen mit reellen Zahlen gearbeitet, in der genetischen Programmie-
rung lassen sich auch komplexe Regeln oder Regelbäume verwenden. Im Prinzip sind
beliebige Datenstrukturen als genetischer Code denkbar. Wichtig ist nur, dass die geneti-
schen Operatoren auf diese Datenstruktur zugeschnitten sind, und dass die Bewertungs-
funktion diesen genetischen Code auslesen kann. Der Vorteil einer komplexen Kodierung
liegt darin, dass die Struktur des Problems direkter und damit besser abgebildet werden
kann, als würde man eine Transformation auf eine einfache Repräsentation, wie beispiels-
weise einen Bitstring, durchführen. Andererseits hat die traditionelle Bit-String-Kodie-
rung den Vorteil, dass keine speziellen Crossover- und Mutationsoperatoren entwickelt
werden müssen, der genetische Algorithmus somit allgemeiner verwendet werden kann.
Die
Selektionsstrategie
legt fest, wie die Verarbeitungseinheiten einer Population aus-
gewählt werden, um daraus neue Verarbeitungseinheiten für die nächste Generation zu
erzeugen. Anstrebenswert ist, dass Verarbeitungseinheiten mit höheren Fitnesswerten sich
stärker fortpflanzen, als Verarbeitungseinheiten mit niedrigen Fitnesswerten. Auf der an-
deren Seite sollte keine Verarbeitungseinheit so dominant sein, dass es zu einer vorzeiti-
gen Konvergenz innerhalb der Gesamtpopulation kommt. Dadurch würde die Suche auf
einen Teilbereich des Suchraumes beschränkt, was selten zu optimalen Lösungen führen
wird. Es soll also einerseits der Suchraum möglichst umfangreich durchmustert werden,
andererseits soll bei der Suche die in den guten Verarbeitungseinheiten gespeicherte Infor-
mation möglichst gut ausgenutzt werden. Diese beiden Ziele stehen in gewissem Gegen-
satz zueinander, der in der Literatur und in diesem Buch bereits mit dem Begriffspaar
Exploration
vs.
Exploitation
zum Ausdruck gebracht wird.
Die klassische Selektionsstrategie der genetischen Algorithmen ist die der Roulette-
Auswahl. Dabei wird jede Verarbeitungseinheit mit einer Wahrscheinlichkeit proportional
zu seiner Fitness ausgewählt. Die Bezeichnung Roulette-Auswahl rührt daher, dass man
sich die Fitnesswerte aller Verarbeitungseinheiten auf einem Kreis aufgetragen denken
kann. Die Summe aller Fitnesswerte ist gleich dem Umfang des Kreises. Wählt man jetzt
zufällig eine Zahl zwischen 0 und der Gesamtfitness (= Einbringen der Roulett-Kugel),
so besitzt jede Verarbeitungseinheit eine Trefferwahrscheinlichkeit, die proportional zu
seinem Fitnesswert ist. Bei der Roulette- Auswahl kann eine Verarbeitungseinheit mit
überdurchschnittlich hohem Fitnesswert so stark in die Reproduktion einfließen, dass die
Population sehr schnell konvergiert. Es besteht dann keine Möglichkeit, den Suchraum
