Vorzeitige Konvergenz

Bei evolutionären Algorithmen (EA) bedeutet der Begriff der vorzeitigen Konvergenz, dass die Individuen (= Lösungen eines Optimierungsproblems) einer Population zu einem Suboptimum konvergiert sind und sich somit alle Individuen im Suchraum am Suboptimum oder in seiner Nähe befinden. In einer solchen Situation sind die elterlichen Lösungen nicht mehr in der Lage, mit Hilfe der genetischen Operatoren Nachkommen zu erzeugen, die ihre Eltern übertreffen. Vorzeitige Konvergenz ist ein häufiges Problem bei evolutionären Algorithmen^[1] und geht mit dem Verlust einer großen Anzahl von Allelen einher. Ein Allel gilt als verloren, wenn in einer Population alle Individuen das gleiche Allel für ein Gen aufweisen. Demgegenüber wird ein Allel nach der etwas schwächeren Definition von De Jong als konvergentes Allel angesehen, wenn 95 % einer Population den gleichen Wert für ein bestimmtes Gen aufweisen.^[2] Trifft dies auf alle oder die meisten Chromosomen und ihre Gene in einer Population zu, kann der Rekombinationsoperator nicht mehr wirken, da die elterlichen Gene vollständig oder nahezu identisch sind. Änderungen sind dann nur noch durch Mutationsoperatoren möglich. Im Laufe einer solchen vorzeitigen Konvergenz wird es somit immer schwieriger, verloren gegangene und nützliche Allelwert wieder zu finden.^[3][4]

Konvergenz und Diversität einer Population

Grundsätzlich kann Konvergenz im Such- und/oder im Problemraum betrachtet werden. Im ersten Fall tritt sie als eine Verringerung der Unterschiede der Genotypen in Erscheinung, was als Abnahme der genotypischen Diversität bezeichnet wird. Im zweiten Fall nähern sich die Phänotypen immer stärker an, was im einfachsten Fall als Annäherung der Fitnesswerte aller Individuen wahrgenommen werden kann. Dies kann durch die Bestimmung der Differenz zwischen den durchschnittlichen und maximalen Fitnesswerten gemessen werden, wie von Patnaik & Srinivas vorgeschlagen.^[5]

Es ist jedoch schwer feststellbar, ob beobachtete Konvergenzerscheinungen ein Suboptimum betreffen und damit als vorzeitig zu betrachten sind, oder ob sich die Population dem gesuchten globalen Optimum nähert.^[4][3]

Vorzeitige Konvergenz kann auch als Stagnation in der Entwicklung der Population aufgefasst werden. Dazu gibt es ein einfach umzusetzendes Messverfahren, das darin besteht, die Generationen zu zählen, bei denen ohne Unterbrechung keine Verbesserung des besten Individuums auftritt. Je nach Selektionsverfahren können auch (zusätzlich) die Generationen gezählt werden, in denen hintereinander keine Nachkommen in der Nachfolgegeneration vorkommen. Nach Erreichen eines Limits gilt dann die Population als konvergiert und die Evolution kann abgebrochen werden.^[6]

Aufwändiger ist hingegen die Bestimmung der genotypischen Diversität in einer Population, wozu verschiedene Verfahren für unterschiedliche Genomarten entwickelt und erprobt wurden.^[7][8][9] Ginley et al. verwenden zum Beispiel ein standard population diversity genanntes Maß, bei dem ein ideelles Referenzchromosom als Durchschnitt aller Allelwerte bestimmt wird, das dann als Vergleichswert für alle Individuen der Population dient. Daraus berechnen sie eine standardisierte Größe als Maß für die Diversität.^[10]

Strategien zur Vermeidung von vorzeitiger Konvergenz

Es gibt eine Reihe von Maßnahmen, um vorzeitiger Konvergenz entgegenzuwirken. Sie alle zielen darauf ab, die genotypische Diversität einer Population länger zu bewahren und so die Breitensuche zu stärken.^[1]

Vergrößerung der Population

Eine Vergrößerung der Population senkt den Selektionsdruck und verstärkt die Breitensuche, zumindest in den frühen Phasen der Evolution. Generell gilt die Populationsgröße als ein wichtiger Strategieparameter von EAs, wobei günstige Werte vom Umfang und der Struktur des Suchraums und damit von der konkreten Anwendung abhängen. Zu kleine Populationen erhöhen das Risiko vorzeitiger Konvergenz und können zu hohem Aufwand in Form vieler Fitnessberechnungen führen, während zu große häufig einen unnötig hohen Aufwand mit sich bringen.^[11]

Verwendung strukturierter Populationen

Die meisten EAs verwenden unstrukturierte oder panmiktische Populationen, bei denen grundsätzlich jedes Individuum der Population für die Partnerwahl basierend auf der Fitness in Frage kommt.^[12][13] So kann sich die genetische Information eines nur geringfügig besseren Individuums innerhalb weniger Generationen in einer Population verbreiten, vorausgesetzt, dass in dieser Zeit keine besseren Nachkommen erzeugt werden. Insbesondere in vergleichsweise kleinen Populationen kann dies schnell zu einem Verlust an genotypischer Vielfalt und damit zu einer vorzeitigen Konvergenz führen.^[3] Eine bekannte Gegenmaßnahme ist der Wechsel zu alternativen Populationsmodellen, die Substrukturen in die Population einführen,^[14][15] welche die genotypische Diversität über einen längeren Zeitraum erhalten und damit der Tendenz zur vorzeitigen Konvergenz entgegenwirken. Dies ist für verschiedene EAs wie genetische Algorithmen,^[14] die Evolutionsstrategie,^[16] andere EAs^[17] oder memetische Algorithmen gezeigt worden.^[17][18]

Anpassung von Selektion, Mutation und Rekombination

Bei der Feststellung von Stagnation und/oder fortgeschrittener Konvergenz wird häufig mit einer Anpassung von Strategieparametern,^[19] angepassten Operatorvarianten^[20] oder der Operatorenauswahl^[7] versucht, einer vorzeitigen Konvergenz entgegenzuwirken. Dies betrifft häufig

• eine angepasste Parametrierung von Selektionsverfahren, um der schnellen Ausbreitung von (etwas) besseren Individuen entgegenzuwirken, wodurch die genotypische Diversität länger erhalten bleibt.^[8][10] Auch entsprechend angepasste Selektionsverfahren kommen zum Einsatz.^[21][22]
• eine Erhöhung der Mutationsrate, um die verlorene Vielfalt wieder herzustellen.^[9][10]
• eine abnehmende Wirksamkeit der Rekombination bei immer ähnlicher werdenden oder gar identischen Eltern. Dem kann beispielsweise durch eine Erhöhung der Crossoverrate bei größerer Unterschiedlichkeit der Eltern Rechnung getragen werden.^[9][10] Oder es werden entsprechend angepasste Operatoren^[20] oder solche verwendet, die die elterlichen Gene stärker mischen, wie z. B. Uniform Crossover anstelle von Crossover an wenigen Punkten.^[10][23]

Crowding

Das von de Jong als Erweiterung genetischer Algorithmen vorgestellte Verfahren zielt direkt auf eine längeren Bewahrung der genotypischen Diversität ab und besteht aus zwei Phasen: Paarung und Ersetzung.^[2] In der Paarungsphase werden die Individuen der Nachkommenschaft mit den Individuen der aktuellen Population anhand einer Ähnlichkeitsmetrik gepaart. In der Ersetzungsphase wird für jedes Paar entschieden, welches der beiden Individuen in der Population verbleiben soll. Eine Übersicht über Crowding-Ansätze kann in ^[24] gefunden werden und in ^[25] eine verallgemeinerte Form des Verfahrens.

Inzestvermeidung

Die übliche fitness-basierte Auswahl der Eltern kann vor allem in späteren Phasen der Evolution dazu führen, dass ähnliche oder sogar identische Individuen zur Nachkommenserzeugung ausgewählt werden. Dem kann durch eine Paarungsstrategie namens Inzestvermeidung^[20][26] entgegengewirkt werden, welche auf dem Hamming-Abstand der Chromosomen der potentiellen Eltern beruht. Die Berechnung des Hamming-Abstands ist für Chromosome ohne bedeutungstragende Reihenfolge der Gene relativ einfach und wird für solche mit relevanter Genreihenfolge oder gar unterschiedlicher Länge aufwändiger.^[27]

Fitness Sharing

Fitness Sharing ist eine Art von Nischenbildung, bei dem die Fitness jedes Individuums auf der Grundlage seiner Nähe zu anderen im Suchraum skaliert wird. Das bedeutet, dass gute Lösungen in dicht besiedelten Regionen des Suchraums einen niedrigeren Fitnesswert erhalten als vergleichbar gute Lösungen in dünn besiedelten Regionen.^[28] Die Auswahltechnik des Verfahrens legt also weniger Gewicht auf hochwertige Lösungen bei hoher Dichte. Der Abstand kann entweder auf der Grundlage der Werte im Entscheidungsraum (Genotyp), im Lösungsraum (Phänotyp) oder auf der Grundlage beider Werte berechnet werden.^[29] Der genotypische Abstand wird in der Regel als Hamming-Abstand gemessen, während der phänotypische üblicherweise durch den Euklidischen Abstand definiert wird. Vorteile und Risiken der Methode werden in ^[30] behandelt.