Populationsmodell (evolutionärer Algorithmus)

Das Populationsmodell eines evolutionären Algorithmus (EA) beschreibt die strukturellen Eigenschaften seiner Population. Eine Population ist die Menge aller in einer Iteration betrachteten Lösungsvorschläge eines EAs, die nach dem biologischen Vorbild auch als Individuen bezeichnet werden. Die Individuen einer Population können mit Hilfe der genetischen Operatoren des Verfahrens weitere Individuen als Nachkommen erzeugen.

Das einfachste und vielfach bei EAs verwendete Populationsmodell ist das globale oder panmiktische Modell, das einer unstrukturierten Population entspricht.^[1][2] Es erlaubt jedem Individuum, ein beliebiges anderes Individuum der Population als Partner für die Erzeugung von Nachkommen zu wählen, wobei die Details der Auswahl für die nachfolgende Betrachtung irrelevant sind, solange die Fitness der Individuen eine bedeutende Rolle spielt. Auf Grund der globalen Partnerwahl können sich bereits geringfügig bessere Individuen nach wenigen Generationen (Iteration eines EAs) in einer Population durchsetzen, sofern in dieser Phase keine besseren entstanden sind. Wenn die so gefundene Lösung nicht das gesuchte Optimum ist, spricht man von vorzeitiger Konvergenz.^[3] Dieser Effekt kann in panmiktischen Populationen öfter beobachtet werden.^[4]

In der Natur sind globale Paarungspools kaum zu finden, vielmehr herrscht eine gewisse und begrenzte Isolierung durch räumliche Distanz vor. Die so entstehenden lokalen Nachbarschaften entwickeln sich zunächst unabhängig voneinander weiter und Mutanten haben eine höhere Chance sich über mehrere Generationen hinweg zu behaupten. Dadurch wird die genotypische Diversität im Genpool länger bewahrt als in einer panmiktischen Population.

Es liegt daher nahe, Unterstrukturen in die zuvor globale Population eines EAs einzuführen. Dazu wurden zwei grundlegende Modelle eingeführt, die Inselmodelle, die auf einer Aufteilung der Population in feste Untermengen beruhen, welche von Zeit zu Zeit Individuen austauschen,^[1][5] und die Nachbarschaftsmodelle, die die Individuen sich überlappenden Nachbarschaften zuordnen.^[4][6] Die damit einhergehende Aufteilung der Population legt auch eine Parallelisierung des Verfahrens nahe. Daher wird das Thema Populationsmodelle in der Literatur auch häufig im Zusammenhang mit der Parallelisierung von EAs behandelt.^{[1][2][4][7][8]}

Inselmodelle

Beispiel eines Inselmodells bestehend aus acht Inseln mit ringförmiger Nachbarschaftsstruktur

Beim Inselmodell, auch Migrationsmodell oder coarse grained model genannt, findet die Evolution in den streng aufgeteilten Teilpopulationen statt. Diese können panmiktisch organisiert sein, müssen es aber nicht. Von Zeit zu Zeit findet ein Austausch von Individuen statt, der als Migration bezeichnet wird.^[2] Die Zeit zwischen zwei Migrationen wird Epoche genannt und ihr Ende kann durch verschiedene Kriterien ausgelöst werden: Nach einer vorgegebenen Zeit oder vorgegebenen Anzahl ausgeführter Generationen oder nach dem Auftreten von Stagnation. Stagnation kann z. B. dadurch festgestellt werden, dass seit einer vorgegebenen Anzahl von Generationen keine Fitnessverbesserung in der Insel mehr festgestellt werden konnte. Inselmodelle führen eine Vielzahl neuer Strategieparameter ein:^{[5][9][10][11]}

• Anzahl der Subpopulationen
• Größe der Subpopulationen
• Die Nachbarschaftsrelationen zwischen den Inseln bestimmen, welche Inseln als benachbart gelten und somit Individuen austauschen können, siehe Bild einer unidirektionalen (schwarze Pfeile) und einer bidirektionalen Ringstruktur (schwarze und grüne Pfeile).
• Kriterien für die Beendigung einer Epoche
• Migrationsrate: Anzahl oder Anteil der an der Migration beteiligten Individuen
• Migrantenauswahl: Hierzu gibt es viele Alternativen. Z. B. können die besten Individuen die schlechtesten oder zufällig gewählte ersetzen. Je nach der Migrationsrate kann das jeweils ein oder mehrere Individuen betreffen.

Mit diesen Parametern kann der Selektionsdruck in erheblichem Maße beeinflusst werden. Er steigt zum Beispiel mit der Vernetzung der Inseln und sinkt mit der Anzahl der Teilpopulationen oder der Epochenlänge.

Nachbarschaftsmodelle oder zelluläre evolutionäre Algorithmen

Zwei Beispiele für sich überlappende Nachbarschaften (Demes) des eindimensionalen ringförmigen Nachbarschaftsmodells der Population eines Evolutionären Algorithmus

Das Nachbarschaftsmodell, auch Diffusionsmodell oder fine grained model genannt, definiert eine topologische Nachbarschaftsrelation zwischen den Individuen einer Population, die unabhängig von ihren phänotypischen Eigenschaften ist.^[1] Im einfachsten Fall ist dies die im Bild dargestellte Ringstruktur.^[6][12] Jedes Individuum hat eine Nachbarschaft (im Englischen deme genannt) von Individuen. Im Bild rechts sind dies beispielsweise die jeweils zwei Nachbarn zur Rechten und zur Linken des Individuums X. Zusammen mit X bilden sie das Deme von X. Jedes Deme repräsentiert eine panmiktische Teilpopulation, innerhalb derer die Partnerwahl und die Annahme von Nachkommen durch Ersetzen des Elters X erfolgt. Die Regeln für die Annahme von Nachkommen sind lokaler Natur und basieren auf der Nachbarschaft: Es kann beispielsweise festgelegt werden, dass der beste Nachkomme besser sein muss als das zu ersetzende Elter oder, weniger streng, nur besser als das schlechteste Individuum im Deme. Die erste Regel ist elitär und erzeugt einen höheren Selektionsdruck als die zweite nicht elitäre.^[4][6] Bei elitären EAs überlebt das beste Individuum einer Population immer. Sie weichen insofern vom biologischen Vorbild ab.

Die Nachbarschaften der Individuen überlappen sich, wie im Bild beispielhaft für je zwei Nachbarschaften bestehend aus jeweils vier Nachbarn dargestellt ist. Die Demes der Individuen X und Y überlappen sich nur minimal, da beide Individuen auf dem Ring weiter voneinander entfernt sind als die Individuen A und B mit maximaler Überlappung. Dies bezeichnet man auch als Isolatation durch Distanz.^[13][6] Die Überschneidung der Nachbarschaften bewirkt eine meist langsame Ausbreitung der genetischen Information über die Nachbarschaftsgrenzen hinweg, daher auch der Name Diffusionsmodell. Ein besserer Nachkomme braucht nun mehr Generationen als bei Panmixie, um sich in der Population auszubreiten. Dadurch wird die Herausbildung lokaler Nischen gefördert, die sich unabhängig von den Nachbarschaftsgrenzen entwickeln und ausbreiten können, bis sie auf konkurrierende Nischen mit mindestens vergleichbarer Fitness stoßen. Die genotypische Diversität der Gesamtpopulation wird so über einen längeren Zeitraum bewahrt.^[6][12][14] Das Ergebnis ist eine selbstadaptierende Balance zwischen Breiten- und Tiefensuche.^[4] Tiefensuche findet in den Nischen statt und die Breitensuche an den Nischengrenzen und durch die Entwicklung der unterschiedlichen Nischen der gesamten Population.^[15]

Beispiel für eine überlappende Nachbarschaft (Deme) des zweidimensionalen torusförmigen Nachbarschaftsmodells der Population eines evolutionären Algorithmus

Beispiele für Nachbarschaften in zweidimensionalen zellulären EAs: linear (L), kompakt (C), rautenförmig (D) oder ... irgendwas anderes.

Eine Alternative zur eindimensionalen Ringstruktur ist die zweidimensionale Torusstruktur, auf der eine geschlossene Gitterstruktur aufgebracht ist, siehe rechte Seite des linken Bildes. Ein darauf basierender EA wird auch zellulärer EA (cEA)^[16][17] oder wenn ein genetischer Algorithmus zu Grunde liegt, zellulärer genetischer Algorithmus (cGA)^[13][18] genannt. Links im linken Bild sind zwei sich nur gering überlappende blockförmige Nachbarschaften der Individuen A und B mit jeweils acht Nachbarn dargestellt. Beim Gitter sind mehr Nachbarschaftsfiguren möglich als beim Ring. So gibt es neben dem bereits behandelten Block z. B. noch eine rautenförmige Variante oder ein senkrechtes oder diagonales Kreuz oder auch unsymmetrische Demes.^[18][19] Das Bild auf der rechten Seite zeigt einige Beispiele. Die Ausbreitung der genetischen Information ist bei jeweils gleichen Nachbarschaftsgrößen bei langgestreckten Figuren wie einem Kreuz größer als beim Block und nochmals deutlich größer als beim Ring.^[20] Beim Ring ist also der Selektionsdruck geringer als beim Torus. Das bedeutet, dass Ringnachbarschaften gut für die Erreichung einer hohen Ergebnisqualität geeignet sind, wobei vergleichsweise lange Laufzeiten in Kauf genommen werden müssen. Ist man hingegen vor allem an schnellen und guten aber möglicherweise suboptimalen Ergebnissen interessiert, so sind die Netztopologien besser geeignet.

Vergleich

Die Aufteilung einer Gesamtpopulation in Teilpopulationen verringert bei der Anwendung beider Modelle bei genetischen Algorithmen^[5][4][6], der Evolutionsstrategie^[12][20][21] und anderen EAs^[22][23] in der Regel das Risiko vorzeitiger Konvergenz und führt insgesamt zuverlässiger und schneller zu besseren Ergebnissen^{[1][2][6][24]} als dies bei panmiktischen EAs zu erwarten wäre.

Inselmodelle haben gegenüber den Nachbarschaftsmodellen den Nachteil, dass sie eine Vielzahl neuer Strategieparameter einführen. Trotz der in der Literatur vorhandenen Untersuchungen zu diesem Thema^[9][25][26] bleibt für den Anwender ein gewisses Risiko ungünstiger Einstellungen. Bei den Nachbarschaftsmodellen ist hingegen lediglich die Größe der Nachbarschaft vorzugeben und beim zweidimensionalen Modell kommt noch die Wahl der Nachbarschaftsfigur hinzu. Auch dazu gibt es umfangreiche Studien.^{[15][17][19][20]}

Parallelität

Da beide Populationsmodelle eine Partitionierung der Population implizieren, eignen sie sich gut als Grundlage für die Parallelisierung eines EA.^[5][8][27] Dies gilt umso mehr für zelluläre EAs, da sie nur auf lokal verfügbare Informationen über die Mitglieder ihrer jeweiligen Demes angewiesen sind. Dadurch kann im Extremfall jedem einzelnen Individuum ein unabhängiger Ausführungsthread zugewiesen werden, so dass der gesamte EA auf einer parallelen Hardwareplattform laufen kann.^{[6][24][28][29]} Das Inselmodell unterstützt die Parallelisierung, z. B. durch Zuweisung eines Prozessors zu jeder Insel. Wenn die Teilpopulationen der Inseln panmiktisch organisiert sind, können alle Auswertungen der Nachkommen einer Generation zusätzlich parallelisiert werden.^[7][11][30] Es ist zu beachten, dass bei realen Anwendungen die Auswertungen in der Regel den weitaus zeitaufwändigsten Teil darstellen. Natürlich ist es auch möglich, die Insel-Teilpopulationen als cEAs zu konzipieren, so dass die zuvor gemachten Aussagen zur Parallelisierung von cEAs gelten. Auf diese Weise können hierarchische Populationsstrukturen mit entsprechenden Parallelisierungen geschaffen werden.^[7] Zur Parallelisierung können nicht nur vergleichsweise teure Computercluster, sondern auch preiswerte Grafikkarten (GPUs)^[31][32] oder die Computer eines Grids^[14] verwendet werden.

Es ist jedoch wichtig zu betonen, dass cEAs oder EAs mit einer über Inseln verteilten Population ein Suchmodell darstellen, das sich, wie dargestellt, in vielerlei Hinsicht von traditionellen EAs unterscheidet. Außerdem können sie sowohl auf sequenziellen als auch auf parallelen Plattformen laufen, was die Tatsache unterstreicht, dass Modell und Implementierung zwei unterschiedliche Konzepte sind.

Literatur

• Erick Cantú-Paz: Efficient and Accurate Parallel Genetic Algorithms (Dissertation, University of Illinois, Urbana-Champaign, USA). Springer, New York, 2001, ISBN 978-1-4613-6964-6 doi:10.1007/978-1-4615-4369-5
• Martina Gorges-Schleuter: Genetic Algorithms and Population Structures - A Massively Parallel Algorithm. Dissertation, Universität Dortmund, Fakultät für Informatik, 1990.
• Enrique Alba, Bernabé Dorronsoro: Cellular Genetic Algorithms. Springer, New York, 2008, ISBN 978-0-387-77609-5 doi:10.1007/978-0-387-77610-1
• Dirk Sudholt: Parallel Evolutionary Algorithms. In: Janusz Kacprzyk, Witold Pedrycz (Hrsg.): Parallel Evolutionary Algorithms. Springer, Berlin, Heidelberg, S. 929–959, 2015, ISBN 978-3-662-43504-5 doi:10.1007/978-3-662-43505-2_46
• Gabriel Luque, Enrique Alba: Parallel Genetic Algorithms. Springer, Berlin Heidelberg, 2011, ISBN 978-3-642-22083-8 doi:10.1007/978-3-642-22084-5