Optimierung

4 Optimierung

Kodierungsprobleme

Die Interpretation der Bits als Dualzahl kann im Falle der GP einige Gefahren bergen. Da der Gencode eines Individuums nur mit geringer Wahrscheinlichkeit mutiert wird, werden sich demnach auch nur wenige Bits durch Mutation verändern. Wie man aber deutlich sehen kann, muss man für die Änderung der Kombination von Zeichen ‚d'(011) zu Zeichen ‚e'(100) drei Bits verändern, obwohl man in der Tabelle nur um einen Platz nach unten rückt. Das macht es fast unmöglich, dass durch Mutation eine kleine Änderung im Phänotyp, also im resultierenden Turing-Programm, hervorgerufen wird. Die Anzahl der sich ändernden Bits von einer Bitkombination auf eine andere nennt man Hamming-Klippe. Im Beispiel von d nach e beträgt sie drei bits. Je länger die Bitketten werden, desto mehr fällt dieser Effekt ins Gewicht und beeinflusst die Lauffreudigkeit des GA negativ.

Gray-Code

Messgeräte, die mit binärer Codierung arbeiten, haben ebenfalls ein großes Problem damit, Änderungen von mehr als einem Bit auf einem Messstreifen zu registrieren. Daher wurde einst der Gray- Code entwickelt.(Frank Gray, Patent: 1947)
Er besitzt die Eigenschaft, dass er zwar auch eine binäre Darstellung natürlicher Zahlen ist, jedoch ändert sich beim Sprung von einem Wert auf den nächsten grundsätzlich nur ein Bit.
Man geht dazu von dualer Codierung aus und übersetzt diese in Graycode, indem man immer zwei Bit mittels XOR vergleicht und das Ergebnis des Vergleichs als neues Gray-Bit setzt. Das erste Bit wird immer als erstes Gray-Zeichen übernommen. Im Nachhinein wird die Bitkette noch invertiert, um die Gray-typische Darstellung herzustellen. Bsp: (Gray to Bin):
$ g_i \\\\rightarrow b_j$
0. 1 $ \\\\rightarrow $ $ \\\\left(b_0=b_0=1\\\\right)$
1. 0 $ \\\\rightarrow $ $ \\\\left(b_1=\\\\left( 0 \\\\;XOR \\\\;1\\\\right)=1\\\\right)$
2. 1 $ \\\\rightarrow $ $ \\\\left(b_2=\\\\left( 1 \\\\;XOR \\\\;1\\\\right)=0\\\\right)$
3. 1 $ \\\\rightarrow $ $ \\\\left(b_3=\\\\left( 1 \\\\;XOR \\\\;0\\\\right)=1\\\\right)$
4. 0 $ \\\\rightarrow $ $ \\\\left(b_4=\\\\left( 0 \\\\;XOR \\\\;1\\\\right)=1\\\\right)$

$ invert\\\\left( Gray\\\\right)\\\\Rightarrow Bin\\\’ar : 11011\\\\newline$
Bei der Umwandlung von Gray- nach Binär-Code wird nicht innerhalb der Gray-Bitkette, sondern immer das aktuelle Gray-Bit mit dem zuletzt erzeugten Binär-Bit mittels XOR verglichen. Vorher muss der Gray-Code invertiert werden, um die umgekehrte Anordnung der Bits einfach zu realisieren.

Einführung verschiedener Spezies

In der Natur kann man ein grundsätzliches Vorgehen beobachten: jede Tier- und Pflanzenart hat ihren Zweck. Betrachtet man die Überlebensstrategien von Ameisen, die sich Läuse „halten\\\’\\\‘ um sich von deren zuckerhaltigen Ausscheidungen zu ernähren, dann wird klar, dass jede Spezies eine eigene Aufgabe hat und diese als hochspezialisierter Profi erfüllt.
Um dieses System auf GP zu übertragen, ist es sinnvoll, eine art „Welt\\\’\\\‘ zu programmieren, die unterschiedlichsten Spezies und deren Untergattungen Platz bietet. Dazu werden für jede Spezies u Unterpopulationen erstellt. Individuen zweier Unterpopulationen können sich nicht direkt durchmischen, d.h. ihre Entwicklung läuft getrennt ab. Weiterhin bedarf es einer Elite-Population, die die besten Individuen aller Unterpopulationen enthält. Führt man den GA auch auf dieser Elite-Population aus, sollte sich dort die beste, globale Lösung finden. Alle Versuche mit dem GP-System haben die Wirksamkeit dieses Systems belegt.

Kindergarten-Schema

Um die Konvergenzgeschwindigkeit des GA weiter zu erhöhen, wird ein sog. Kindergarten-Pool eingeführt. In jeder Generation werden k Individuen in den KiGa-Pool kopiert. Diese werden p Generationen lang darin aufbewahrt, ohne dass sie am Selektionsprozess teilnehmen dürfen. In jeder Generation wird versucht, die gespeicherten „Kinder\\\’\\\‘ durch Mutation zu verbessern. Sollte sich eine Verbesserung einstellen, wird ein schlechtes Individuum in der „richtigen\\\’\\\‘ Population durch das mutierte Kind ersetzt. Es befinden sich demnach stets p*k Individuen im Kindergarten.

Seniorenunterkunfts-Schema

Wie im richtigen Leben sollte es Älteren, aber fitten Individuen erlaubt sein, etwas länger am Selektionsprozess teilnehmen zu dürfen. Dazu wird ein Pool, ähnlich dem Kindergarten erstellt, in den in jeder Generation die m besten Individuen eingefügt werden. Diese werden über n Generationen aufbewahrt und dürfen in jedem Evolutions-Schritt am Selektionsprozess teilnehmen. Somit befinden sich stets m*n Individuen im Pool. Die Praxis zeigt auch hier, das ein solcher Pool die Konvergenzgeschwindigkeit erhöht, jedoch erwies sich die Implemetierung von Kindergarten und Seniorenunterkunft als fehlerträchtig und wurde deshalb in der Endversion nicht eingebunden.

Lokale Suche

Unter Lokaler Suche versteht man bzgl Genetischer Algorithmen die Modifizierung von Individuen während Ihres Lebenszyklus.

Die einfachste Methode, Optimierungen auszuführen stellt die Mutation dar.

Das Vorgehen ist dabei immer gleich:

Das Individuum wird einer Fitnessbewertung unterworfen und zwischengespeichert. Eine Kopie des Originalindivuduums wird über seine Gesamte Lebenszeit Mutationen unterzogen und seine Fitness nach jeder Mutation neu bewertet. Wird durch eine Mutation eine bessere Fitness hervorgerufen, wird das originale Individuum mit dem neuen ersetzt.

Der Einsatz dieser Methode muss, genau wie die Nutzung einer Eliteselektion, mit Vorsicht genossen werden, da hierbei ebenfalls die Gefahr der Verarmung des Genpools droht. So kann ich nur empfehlen, die Anzahl der Individuen, die lokaler Optimierung unterzogen werden, zu variieren, bis eine für den Problemtyp optimale Lernkurve entsteht.

Eine erfolgreiche Population entsteht eben immer nur durch Vielfalt.

Neuerdings werden Genetische Algorithmen, die diese oder andere lokale Optimierungsmethoden auch als Memetische Algorithmen bezeichnet

2 Gedanken zu “Optimierung

  1. Ui Danke für diese gute Seite. Sehr ansprechend (verständlich)geschrieben bis auf die Formatierungsfehler.

    Gruß sim

  2. Gern geschehen! Sobald ich wieder Zeit hab, nehme ich die Formatierungen in Angriff. Die sind nicht optimal, da geb ich dir Recht.

    Am Ende der Seite findet Ihr einen Downloadlink für die PDF-Version, die korrekte Formatierungen enthält

    Gruß,
    Nico

Schreibe einen Kommentar