Proportionale Selection (Roulette-Rad) in Genetischen Algorithmen

Einige Leser hier wissen dass ich PGApack, ein Paket für Genetische Algorithmen, zusammen mit PGApy einer Python Bibliothek pflege (maintaine). Vor kurzem kam die Frage auf, warum PGApack wenn eine Selektionsmethode verwendet wird die proportional zur Fitness selektiert (Fitness Proportionate Selection), im englischen auch als Roulette-Rad Selektion bezeichnet, mit einem Fehler aussteigt weil es einen Fitness-Wert nicht normalisieren kann. Im folgenden werde ich kurz von proportionaler Selektion schreiben.

In PGApack definieren wir als Anwenderin eine Reelle Bewertungsfunktion (die für jedes Individuum aufgerufen wird). Ausserdem definieren wir ob diese Bewertung minimiert oder maximiert wird (wir legen die Optimierungsrichtung fest).

Bei proportionaler Selektion muss diese Bewertung auf positive Werte abgebildet werden so dass jeder Bewertung ein Teil des Roulette-Rades zugewiesen wird. Wenn minimiert wird sind kleine Werte besser und müssen einen größeren Bereich des Roulette-Rades bekommen so dass die Wahrscheinlichkeit der Selektion höher ist. Wir müssen also die Bewertungsfunktion auf eine nicht-negative monoton steigende Fitness abbilden. Bei einem Minimierungsproblem berechnen wir die maximale (schlechteste) Bewertung und bilden dann die Differenz dieses Maximums mit der Bewertung des Individuums (nach einer Skalierung des Maximums so dass kein Fitnesswert negativ wird):

wobei \(F\) die Fitness des aktuellen Individuums ist, \(E_{max}\) das Maximum aller Bewertungen der aktuellen Generation und \(E\) die Bewertung des Individuums.

Wenn sich nun die Bewertungen um mehrere Größenordnungen unterscheiden kann es vorkommen, dass die Fitness zu \(E_{max}\) wird, für viele (unterschiedliche) Individuen. Ich nenne das einen Überlauf (overflow), vielleicht nicht der beste Name dafür.

Der Überlauf passiert wenn \(E_{max}\) groß ist verglichen mit der aktuellen Bewertung \(E\) so dass die obige Differenz \(E_{max}\) wird (die Subtraktion von \(E\) also keine Wirkung hat) Im Code checken wir diese Bedingung:

if (cmax == cmax - evalue && evalue != 0)

Die Bedingung ist erfüllt wenn die Subtraktion von \(E\) von \(E_{max}\) \(E_{max}\) nicht verändert obwohl \(E\) ungleich Null ist. \(E\) ist so klein gegenüber \(E_{max}\) dass der Datentyp double den Unterschied nicht repräsentieren kann. Das passiert wenn die Einheit der letzten Stelle (units in the last place von Goldberg (nicht dem Goldberg der das Genetische Algorithmen Buch geschrieben hat soweit ich weiss) auch ulps genannt) der Mantisse größer ist als der Wert der subtrahiert wird [1].

In unserem Beispiel \(E_{max} = 1.077688 * 10^{22}\) und die Bewertung bei der das schiefging war \(E = 10000\). Ein IEEE 754 Fließkomma-Wert doppelter Genauigkeit (double) hat 53 bit Mantisse die damit Zahlen bis \(2^{54} - 1 = 18014398509481983\) darstellen kann, also etwa \(1.8 * 10^{16}\). Man sieht dass die Zahl 10000 gerade unterhalb des oben erwähnten ulps ist. Wir können das in Python ausprobieren (das für Fließkommazahlen double verwendet):

>>> 1.077688e22 - 10000 == 1.077688e22
True

Warum machen wir diesen Check im Programm? Würde die Suche bei einem solchen Überlauf (oder wie auch immer wir das nennen wollen) weiterlaufen, würde der Algorithmus viele verschiedene Bewertungen auf die gleiche Fitness abbilden. Der Genetische Algorithmus könnte also diese Individuen nicht unterscheiden.

Was können wir tun wenn dieser Fehler auftritt?

Die kurze Antwort: Einen anderen Selektionsmechanismus verwenden. Es gibt einen Grund, warum proportionale Selektion nicht die Standardeinstellung in PGApack ist.

Proportionale Selektion (Fitness proportionate selection) hat noch andere Probleme. Sie hat zu großen Selektionsdruck am Anfang zu wenig gegen Ende der Optimierung (auch erwähnt im obigen Wikipedia Artikel, aber Vorsicht, ich habe Teile davon geschrieben).

Blickle and Thiele [2] haben eine mathematische Analyse von unterschiedlichen Selektions-Algorithmen publiziert und gezeigt dass proportionale Selektion typischerweise keine gute Idee ist (proportionale Selektion war historisch der erste Selektionsmechanismus in der Literatur und war ausführlich in Goldbergs (der andere Goldberg) Buch [3] beschrieben und ist vielleicht deshalb heute noch manchmal in Verwendung). Es sei darauf hingewiese dass Blickle und Thiele in einem früheren Report [4] direkter waren was die Beurteilung von proportionaler Selektion betrifft (meine Übersetzung): "Alle unerwünschten Eigenschaften zusammen führten uns zu dem Schluss dass proportionale Selektion ein sehr ungeeigneter Selektionsmechanismus ist. Informell könnten wir sagen dass der einzige Vorteil von proportionaler Selektion ist, dass es so schwierig ist die Nachteile zu beweisen" ([4], S. 42), in der Endfassung im veröffentlichten Artikel waren sie dann nicht mehr so deutlich :-)

Wir sehen in obigem Beispiel: Wir haben sehr große Unterschiede zwischen guten und schlechten Bewertungen (eben so groß dass die Fitness nicht eindeutig berechnet werden kann, s.o.). Wenn man dafür proportionale Selektion verwendet, werden sehr gute Individuen mit zu großer Wahrscheinlichkeit selektiert was zu verfrühter Konvergenz (premature convergence) führt.

Zum Schluss all dieser Ausführungen: Wenn wir Optimierungen mit Fließkomma-Repräsentationen durchführen (diese werden durch double Datentypen in PGApack repräsentiert) sollten wir Differential Evolution ausprobieren [5], [6], [7]. Zumindest in meinen Experimenten mit Antennen-Optimierung [8] sind die Resultate damit deutlich besser als mit standard Genetischen Algorithmen was auch von verschiedenen Praktikern bestätigt wird [7]. Beispiele dazu finden sich in examples/deb/optimize.c oder examples/mgh/testprogde.c in PGApack.

Der Parameter PGASetDECrossoverProb ist kritisch. Für Probleme wo die Dimensionen nicht einzeln optimierbar sind, sollte der Wert nahe bei, aber nicht gleich 1 sein.