Notizen zur Vorzeitigen Konvergenz in Genetischen Algorithmen

Ralf Schlatterbeck

Auch verfügbar in:

English

Dieser Beitrag beschäftigt sich wieder mit PGAPack und PGApy, sowie anderen Implementierungen von Genetischen Algorithmen (GA).

Bei der Suche von Lösungen mit einem GA passiert es, dass eine sub-optimale Lösung gefunden wird, weil die Population frühzeitig in einem Bereich des Suchraumes konvergiert wo keine besseren Lösungen mehr gefunden werden. Dieser Effekt heisst vorzeitige Konvergenz.

Es ist normalerweise schwierig, vorzeitige Konvergenz zu entdecken. Eine gute Metrik ist die mittlere Hamming Distanz zwischen Individuen. In PGAPack kann man Auswertungen der Hamming Distanz über die Option PGA_REPORT_HAMMING der Funktion PGASetPrintOptions aktivieren. In PGApy geht das mit dem Konstruktor Parameter print_options. Leider ist dies nur für den binären Datentyp implementiert.

Ein möglicher Grund für das Auftreten von vorzeitiger Konvergenz ist die Verwendung von proportionaler Selektion wie in einem früheren Artikel in diesem Blog [1] ausgeführt. Wenn während der Frühphase der Suche ein Individuum gefunden wird das viel besser ist als alles bisherige, so ist die Chance groß, dass dieses Individuum die Population übernimmt wenn proportionale Selektion verwendet wird, wodurch ein weiterer Fortschritt des Algorithmus verhindert wird. Der Grund dafür ist, dass ein Individuum das wesentlich besser ist als alle anderen einen unangemessen hohen Anteil des (gedachten) Roulette-Rades einnimmt wenn Individuen für die nächste Generation ausgewählt werden, was dazu führt, dass alles andere genetische Material nur eine geringe Chance hat, in die nächste Generation zu kommen.

Ein anderer Grund für vorzeitige Konvergenz kann eine zu kleine Populationsgröße sein. Goldberg et. al. [9] geben Abschätzungen der Populationsgröße für einen klassischen GA mit kleinem Alphabet (mögliche verschiedene Allele, also 0 und 1 für einen binären GA) der Kardinalität \(\chi\) an. Dabei wird eine maximale Länge einer Symbolfolge (Building Block) angenommen die irreführende Symbolfolgen (deception) überwindet mit \(k \ll n\) wobei \(k\) die Symbolfolgen-Länge (ein Maß für die Schwierigkeit des Problems) und \(n\) die Gen-Länge ist. Es wird gezeigt, dass die Populationsgröße \(O(m\chi^k)\) sein sollte mit \(m=n/k\) so dass mit einer vorgegebenen Schwierigkeit \(k\) die Populationsgröße proportional zur Gen-Länge \(n\) ist. Dieses Ergebnis kann aber nicht auf Probleme mit einem sehr großen Alphabet wie Fließkomma-Genen wie dem real Datentyp von PGAPack verallgemeinert werden. Für Fließkomma Darstellungen kann man die Schwierigkeit üblicherweise einschätzen wenn man die Multimodalität, also die Anzahl der Gipfel oder Täler (jenachdem ob es sich um ein Maximierungs- oder Minimierungsproblem handelt) der Zielfunktion betrachtet.

Wenn mit einer angemessenen Populationsgröße und einem sinnvollen Selektionsmechanismus noch immer vorzeitige Konvergenz auftritt, können einige andere Mechanismen zur Anwendung kommen.

Vermeidung von Duplikaten

PGAPack implementiert einen Mechanismus zur Vermeidung von doppelt vorkommenden Genen (Individuen). In früheren Implementierungen war der Aufwand dafür quadratisch in der Populationsgröße \(N\), also \(O(N^2)\) (es wurde jedes neue Individuum mit allen Mitgliedern der aktuellen Population verglichen). In der aktuellen Version wird eine Hashfunktion verwendet um Duplikate zu entdecken, was den Aufwand auf \(O(N)\) reduziert, also einen kleinen konstanten Aufwand für jedes neue Individuum.

Für benutzerdefinierte Datentypen bedeutet das, dass eine Hash Funktion für den Datentyp gebraucht wird, zusätzlich zu einer Gen-Vergleichsfunktion. Für die eingebauten Datentypen (binary, integer, real) sind diese Funktionen automatisch verfügbar.

Die Vermeidung von Duplikaten funktioniert gut für Integer und Binäre Datentypen, besonders wenn die verwendeten genetischen Operatoren mit hoher Wahrscheinlichkeit Duplikate erzeugen können. Es funktioniert nicht so gut mit dem real Datentyp weil Individuen normalerweise unterschiedlich sind, auch wenn sie genetisch sehr nah beieinanderliegen.

Restricted Tournament Replacement

Ein Algorithmus der ursprünglich von Harik [2], [3] Restricted Tournament Selection genannt wurde und später von Pelikan [4] mit Restricted Tournament Replacement (RTR) bezeichnet wurde, verwendet die alte und die neue Population um zu entscheiden, ob ein Kandidat in die neue Population aufgenommen wird. Der Algorithmus wählt eine Anzahl von Individuen der alten Population (das sogenannte Selektionsfenster) zufällig aus und vergleicht die Bewertung des Indivuums welches genetisch dem Kandidaten-Individuum am nächsten ist. Nur wenn das Kandidaten-Individuum besser ist als das genetisch ähnlichste aus dem Selektionsfenster wird es in die neue Generation übernommen.

Die Standardeinstellung für die Anzahl der Individuen im Selektionsfenster ist \(\min (n, \frac{N}{20})\) [4] wobei \(n\) die Genlänge und \(N\) die Populationsgröße ist. Dies kann vom Benutzer geändert werden durch Aufruf der Funktion PGASetRTRWindowSize für PGAPack bzw. mit dem Konstruktor-Parameter rtr_window_size für PGApy.

Der RTR-Algorithmus braucht eine Ähnlichkeitsmetrik um zu entscheiden, wie ähnlich ein Individuum einem anderen ist. Die Vorgabe ist die Manhattan Distanz (für binäre Gene identisch mit der Hamming Distanz), also die Summe aller einzelnen Allele-Differenzen. Dies kann auf die Euclidsche Distanz geändert werden durch Setzen einer benutzerdefinierten Funktion für die genetische Distanz. Die Verwendung einer Euclidschen Ähnlichkeitsmetrik sieht man im Beispiel: Magisches Quadrat in PGApy wo man die Euclidsche Metrik über eine Kommandozeilenoption auswählen kann.

Restricted Tournament Replacement funktioniert nicht nur für binäre und Integer Gene gut sondern auch für den real Datentyp. Man kann diesen Ersetzungsmechanismus mit anderen Einstellungen des GA kombinieren.

Die Auswirkung von RTR auf ein Problem das zu vorzeitiger Konvergenz tendiert kann man im Test-Programm examples/mgh/testprog.f sehen. Dieses Programm implementiert einige Testfunktionen aus einem alten Benchmark für nichtlineare Optimierungsalgorithmen [5]. Die Testfunktion mit Tendenz zu vorzeitiger Konvergenz ist was die Autoren eine "gausssche Funktion" nennen, beschrieben im Beispiel (9) im Artikel [5] und implementiert als Funktion 3 in examples/mgh/objfcn77.f. Diese Funktion wird angegeben als

\begin{equation*} f(x) = x_1 \cdot e^{\frac{x_2(t_i - x_3)^2}{2}} - y_i \end{equation*}

mit

\begin{equation*} t_i = (8 - i) / 2 \end{equation*}

Und tabellierten Werten für \(y_i\) im Artikel bzw. der Implementierung in examples/mgh/objfcn77.f. Das Minimierungsproblem aus diesen Gleichungen ist

\begin{equation*} f (x) = \sum_{i=1}^{m} f_i^2(x) \end{equation*}

mit \(m=15\) für dieses Testproblem. Die Autoren [5] geben den Vektor \(x_0 = (0.4, 1, 0)\) für das Minimum \(f(x_0) = 1.12793 \cdot 10^{-8}\) an. Die Original Fortran-Implementierung in examples/mgh/testprog.f verwendet eine Populationsgröße von 10000 mit den Standardeinstellungen für den real Datentyp von PGAPack. Die große Populationsgröße wird gewählt weil das Problem sonst vorzeitig konvergiert. Nach 100 Generationen wird die Lösung \(x_0=(0.3983801, 0.9978369, 0.009918243)\) mit einem Evaluationswert von \(f(x_0)=2.849966\cdot 10^{-5}\) gefunden. Die Anzahl der Funktionaufrufe der Zielfunktion waren 105459 (etwas weniger als \(10000 + 100 \cdot 1000\) also Bewertung der initialen Population plus etwa 10% der Population in jeder Generation, die Wahrscheinlichkeit für Crossover und Mutation ist nicht 100%, daher kommt es vor dass keiner der Operatoren angewandt wird und die Evaluationsfunktion daher nicht aufgerufen wird)

Ich habe das gleiche Problem mit Differential Evolution [6], [7], [8] in examples/mgh/testprogde.c implementiert (das Treiberprogramm ist in C geschrieben weil ich nicht wirklich Fortran spreche, verwendet aber die gleichen Funktionen wie das Fortran Treiberprogramm und linkt Fortran und C Code in einem gemeinsamen ausführbaren Programm). Es verwendet eine Populationsgröße von 2000 (was für Differential Evolution groß ist wieder aus Gründen von vorzeitiger Konvergenz) und findet die Lösung \(x_0=(0.3992372, 0.9990791, -0.0007697923)\) mit einer Bewertungsfunktion von \(f(x_0)=7.393123\cdot 10^{-7}\) in nur 30 Generationen. Dies entspricht 62000 Funktionsaufrufen der Zielfunktion (Differential Evolution berechnet eine komplette Generation und entscheidet dann welche Individuen in die neue Generation übernommen werden).

Wenn man RTR für dieses Problem verwendet wie in examples/mgh/testprogdertr.c, kann die Populationsgröße auf 250 reduziert werden und sogar nach 100 Generationen konvergiert die Suche nicht vorzeitig auf eine suboptimale Lösung. Nach 100 Generationen finden wir \(x_0=(0.398975, 1.000074, -6.719886 \cdot 10^{-5})\) und \(f(x_0)=1.339766\cdot 10^{-8}\) (allerdings mit ein paar anderen Einstellungen für den Differential Evolution Algorithmus). Dies entspricht 25250 Funktionsaufrufen der Zielfunktion.

Restart

Das letzte Mittel wenn die obigen Mechanismen versagen ist ein regelmässiger Restart des GA wann immer die Population zu stark konvergiert. Der Restart-Mechanismus in PGAPack verwendet das beste Individuum der Population um eine neue Population mit durch Mutation erzeugten Varianten dieses Individuums zu initialisieren. Restarts kann man mit PGASetRestartFlag in PGAPack oder dem restart Konstruktor Parameter in PGApy einschalten. Die Frequenz der Restarts (Standard ist alle 50 Generationen) kann mit PGASetRestartFrequencyValue in PGAPack und dem restart_frequency Konstruktor Parameter in PGApy gesetzt werden.