Populationsmodell (evolutionärer Algorithmus)

Unter der Population eines evolutionären Algorithmus (EA) versteht man die Menge aller in einer Iteration betrachteten Lösungsvorschläge des Verfahrens, welche entsprechend dem biologischen Vorbild auch Individuen genannt werden. Das Populationsmodell beschreibt die Strukturen, denen die Individuen innerhalb der Population unterliegen.

Das einfachste und vielfach bei EAs verwendete Populationsmodell ist das globale oder panmiktische Modell, das einer unstrukturierten Population entspricht. 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 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. Dieser Effekt kann in panmiktischen Populationen öfter beobachtet werden.

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 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, und die Nachbarschaftsmodelle, die die Individuen sich überlappenden Nachbarschaften zuordnen. 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.