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. 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. 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, die zuvor globale Population eines EAs durch Unterstrukturen zu segmentieren. 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.

1. 1 2 3 Erick Cantú-Paz: A survey of parallel genetic algorithms. In: Calculateurs Paralleles. Band 10, Nr. 2, 1998, S. 141–171 (uma.es [PDF; abgerufen am 20. Juli 2022]). 
2. 1 2 V. Scott Gordon, Darrell Whitley: Serial and Parallel Genetic Algorithms as Function Optimizers. In: S. Forrest (Hrsg.): Conf. Proc of the Fifth International Conference on Genetic Algorithms (ICGA). Morgan Kaufmann, San Mateo, CA 1993, ISBN 1-55860-299-2, S. 177–183 (colostate.edu [PDF]). 
3. ↑ Yee Leung, Yong Gao, Zong-Ben Xu: Degree of population diversity – A perspective on premature convergence in genetic algorithms and its markov chain. In: IEEE Transactions on Neural Networks. Band 8, Nr. 5, 1997, ISSN 1045-9227, S. 1165–1176, doi:10.1109/72.623217 (ieee.org). 
4. 1 2 3 Martina Gorges-Schleuter: Genetic Algorithms and Population Structures - A Massively Parallel Algorithm. PhD thesis, Universität Dortmund, Fakultät für Informatik, 1990. 
5. ↑ Erick Cantú-Paz: Efficient and Accurate Parallel Genetic Algorithms. Genetic Algorithms and Evolutionary Computation, Nr. 1. Springer US, Boston, MA 2001, ISBN 1-4613-6964-9, doi:10.1007/978-1-4615-4369-5 (englisch). 
6. ↑
7. ↑ Hatem Khalloof, Mohammad Mohammad, Shadi Shahoud, Clemens Duepmeier, Veit Hagenmeyer: A Generic Flexible and Scalable Framework for Hierarchical Parallelization of Population-Based Metaheuristics. In: Conf. Proc of the 12th Int. Conf. on Management of Digital EcoSystems (MEDES’20). 2020, S. 124–131, doi:10.1145/3415958.3433041. 
8. ↑ Dirk Sudholt: Parallel Evolutionary Algorithms. In: Janusz Kacprzyk, Witold Pedrycz (Hrsg.): Springer Handbook of Computational Intelligence. Springer, Berlin, Heidelberg 2015, ISBN 978-3-662-43504-5, S. 929–959, doi:10.1007/978-3-662-43505-2_46 (shef.ac.uk [PDF]).