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.

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, die als Migration bezeichnet wird. Die Zeit zwischen einem Austausch 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:

• 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.

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. Im einfachsten Fall ist dies die im Bild dargestellte Ringstruktur. 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. 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. 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. Das Ergebnis ist eine selbstadaptierende Balance zwischen Breiten- und Tiefensuche. Tiefensuche findet in den Nischen statt und die Breitensuche an den Nischengrenzen und durch die Entwicklung der unterschiedlichen Nischen der gesamten Population.

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

Eine Alternative zur eindimensionalen Ringstruktur ist die zweidimensionale Torusstruktur, auf der eine geschlossene Gitterstruktur aufgebracht ist, siehe rechte Seite des Bildes. Ein darauf basierender EA wird auch zellulärer EA (cEA) oder wenn ein genetischer Algorithmus zu Grunde liegt, zellulärer genetischer Algorithmus (cGA) genannt. Links im 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 z. B. noch ein senkrechtes oder diagonales Kreuz oder auch unsymmetrische Demes. 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. 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, der Evolutionsstrategie und anderen EAs in der Regel das Risiko vorzeitiger Konvergenz und führt insgesamt zuverlässiger und schneller zu besseren Ergebnissen 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 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.

Parallelität

Da beide Populationsmodelle eine Partitionierung der Population implizieren, eignen sie sich gut als Grundlage für die Parallelisierung eines EA. 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. 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. 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. Zur Parallelisierung können nicht nur vergleichsweise teure Computercluster, sondern auch preiswerte Grafikkarten (GPUs) oder die Computer eines Grids 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.

Einzelnachweise

1. 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. 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 978-1-55860-299-1, 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. 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. Martina Gorges-Schleuter: Explicit parallelism of genetic algorithms through population structures. In: Hans-Paul Schwefel, Reinhard Männer (Hrsg.): Parallel Problem Solving from Nature. Band 496. Springer-Verlag, Berlin/Heidelberg 1991, ISBN 978-3-540-54148-6, S. 150–159, doi:10.1007/bfb0029746 (springer.com [abgerufen am 31. Januar 2023]). 
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]). 
9. Erick Cantú-Paz: Topologies, Migration Rates, and Multi-Population Parallel Genetic Algorithms. In: Proc. of the 1st Annual Conf. on Genetic and Evolutionary Computation (GECCO). 1999, S. 91–98 (acm.org [PDF]). 
10. K. Belkadi, M. Gourgand, M. Benyettou: Parallel genetic algorithms with migration for the hybrid flow shop scheduling problem. In: Journal of Applied Mathematics and Decision Sciences. Band 2006, 8. November 2006, ISSN 1173-9126, S. 1–17, doi:10.1155/JAMDS/2006/65746 (hindawi.com [abgerufen am 16. Februar 2023]). 
11. N. Adar, G. Kuvat: Parallel Genetic Algorithms with Dynamic Topology using Cluster Computing. In: Advances in Electrical and Computer Engineering. Band 16, Nr. 3, 2016, ISSN 1582-7445, S. 73–80, doi:10.4316/AECE.2016.03011 (aece.ro [abgerufen am 16. Februar 2023]). 
12. Joachim Sprave: Linear Neighborhood Evolution Strategy. In: Conf. Proc. of the 3rd Annual Conference on Evolutionary Programming. World Scientific, Singapore 1994, S. 42–51 (tu-dortmund.de [PDF]). 
13. Vahl Scott Gordon, Keith Mathias, Darrell Whitley: Cellular Genetic Algorithms as Function Optimizers: Locality Effects. In: Conf. Proc. ACM Symposium on Applied Computing (SAC’ 94). 1994, S. 237–241, doi:10.1145/326619.326732 (acm.org). 
14. Dudy Lim, Yew-Soon Ong, Yaochu Jin, Bernhard Sendhoff, Bu-Sung Lee: Efficient Hierarchical Parallel Genetic Algorithms using Grid computing. In: Future Generation Computer Systems. Band 23, Nr. 4, Mai 2007, S. 658–670, doi:10.1016/j.future.2006.10.008 (researchgate.net [abgerufen am 17. Februar 2023]). 
15. Enrique Alba: Cellular genetic algorithms. Springer, Berlin 2008, ISBN 978-0-387-77610-1 (springer.com [abgerufen am 16. Februar 2023]). 
16. M. Giacobini, M. Tomassini, A.G.B. Tettamanzi, E. Alba: Selection Intensity in Cellular Evolutionary Algorithms for Regular Lattices. In: IEEE Transactions on Evolutionary Computation. Band 9, Nr. 5, Oktober 2005, ISSN 1089-778X, S. 489–505, doi:10.1109/TEVC.2005.850298 (researchgate.net [abgerufen am 16. Februar 2023]). 
17. Enrique Alba, José Ma Troya: Cellular Evolutionary Algorithms: Evaluating the Influence of Ratio. In: Parallel Problem Solving from Nature PPSN VI. Band 1917. Springer, Berlin, Heidelberg 2000, ISBN 978-3-540-41056-0, S. 29–38, doi:10.1007/3-540-45356-3_3 (springer.com [abgerufen am 16. Februar 2023]). 
18. Enrique Alba, Bernabè Dorronsoro: Introduction to Cellular Genetic Algorithms. In: Cellular Genetic Algorithms. Band 42. Springer US, Boston, MA 2008, ISBN 978-0-387-77609-5, S. 3–20, doi:10.1007/978-0-387-77610-1_1 (springer.com [abgerufen am 31. Januar 2023]). 
19. Jayshree Sarma, Kenneth De Jong: An analysis of the effects of neighborhood size and shape on local selection algorithms. In: Parallel Problem Solving from Nature — PPSN IV. Band 1141. Springer, Berlin, Heidelberg 1996, ISBN 978-3-540-61723-5, S. 236–244, doi:10.1007/3-540-61723-x_988 (researchgate.net [abgerufen am 17. Februar 2023]). 
20. Martina Gorges-Schleuter: A comparative study of global and local selection in evolution strategies. In: Parallel Problem Solving from Nature — PPSN V. Band 1498. Springer Berlin Heidelberg, Berlin, Heidelberg 1998, ISBN 3-540-65078-4, S. 367–377, doi:10.1007/bfb0056879. 
21. Martina Gorges-Schleuter, Ingo Sieber, Wilfried Jakob: Local Interaction Evolution Strategies for Design Optimization. In: Conf. Proc. Congress on Evolutionary Computation (CEC 99). IEEE press, Piscataway, N.J., USA 1999, S. 2167–2174 (ieee.org [PDF]). 
22. Christian Blume, Wilfried Jakob: GLEAM - General Learning Evolutionary Algorithm and Method: Ein Evolutionärer Algorithmus und seine Anwendungen. In: Schriftenreihe des Instituts für Angewandte Informatik – Automatisierungstechnik. Band, Nr. 32. KIT Scientific Publishing, Karlsruhe 2009, ISBN 978-3-86644-436-2, doi:10.5445/KSP/1000013553. 
23. Enrique Alba Torres, Bernabé Dorronsoro, Hugo Alfonso: Cellular Memetic Algorithms. In: Journal of Computer Science and Technology. Band 5, Nr. 4, 2005, S. 257–263 (edu.ar). 
24. Wilfried Jakob, Martina Gorges-Schleuter, Christian Blume: Application of Genetic Algorithms to Task Planning and Learning. In: Reinhard Männer, Bernard Manderick (Hrsg.): Parallel Problem Solving from Nature 2, PPSN-II. North Holland, Amsterdam 1992, S. 291–300, S. 292 (researchgate.net). 
25. Wen-Yang Lin, Tzung-Pei Hong, Shu-Min Liu: On adapting migration parameters for multi-population genetic algorithms. In: 2004 IEEE International Conference on Systems, Man and Cybernetics (IEEE Cat. No.04CH37583). Band 6. IEEE, The Hague, Netherlands 2004, ISBN 978-0-7803-8567-2, S. 5731–5735, doi:10.1109/ICSMC.2004.1401108 (ieee.org [abgerufen am 16. Februar 2023]). 
26. Tzung-Pei Hong, Wen-Yang Lin, Shu-Min Liu, Jiann-Horng Lin: Dynamically Adjusting Migration Rates for Multi-Population Genetic Algorithms. In: Journal of Advanced Computational Intelligence and Intelligent Informatics. Band 11, Nr. 4, 20. April 2007, ISSN 1883-8014, S. 410–415, doi:10.20965/jaciii.2007.p0410 (fujipress.jp [abgerufen am 16. Februar 2023]). 
27. Gabriel Luque, Enrique Alba: Parallel Genetic Algorithms (= Studies in Computational Intelligence. Nr. 367). Springer, Berlin, Heidelberg 2011, ISBN 978-3-642-22083-8, doi:10.1007/978-3-642-22084-5 (springer.com [abgerufen am 17. Februar 2023]). 
28. Gabriel Luque, Enrique Alba, Bernabé Dorronsoro: An asynchronous parallel implementation of a cellular genetic algorithm for combinatorial optimization. In: Proceedings of the 11th Annual conference on Genetic and evolutionary computation. ACM, Montreal Québec Canada 2009, ISBN 978-1-60558-325-9, S. 1395–1402, doi:10.1145/1569901.1570088 (acm.org [abgerufen am 17. Februar 2023]). 
29. Zhongwen Luo, Hongzhi Liu: Cellular Genetic Algorithms and Local Search for 3-SAT problem on Graphic Hardware. In: 2006 IEEE International Conference on Evolutionary Computation. IEEE, Vancouver, BC, Canada 2006, ISBN 978-0-7803-9487-2, S. 2988–2992, doi:10.1109/CEC.2006.1688685 (ieee.org [abgerufen am 17. Februar 2023]). 
30. S. Cahon, N. Melab, E.-G. Talbi: ParadisEO: A Framework for the Reusable Design of Parallel and Distributed Metaheuristics. In: Journal of Heuristics. Band 10, Nr. 3, Mai 2004, ISSN 1381-1231, S. 357–380, doi:10.1023/B:HEUR.0000026900.92269.ec (springer.com [abgerufen am 17. Februar 2023]). 
31. Paul Jähne: Overview of the current state of research on parallelisation of evolutionary algorithms on graphic cards. In: H.C. Mayr, M. Pinzger (Hrsg.): Informatik 2016 Tagung vom 26. - 30. September 2016. Gesellschaft für Informatik, Bonn 2016, ISBN 978-3-88579-653-4 (emis.de [PDF; abgerufen am 17. Februar 2023]). 
32. Raúl García-Calvo, Jl Guisado, Fernando Diaz-del-Rio, Antonio Córdoba, Francisco Jiménez-Morales: Graphics Processing Unit–Enhanced Genetic Algorithms for Solving the Temporal Dynamics of Gene Regulatory Networks. In: Evolutionary Bioinformatics. Band 14, Januar 2018, ISSN 1176-9343, S. 117693431876788, doi:10.1177/1176934318767889, PMID 29662297 (sagepub.com [abgerufen am 17. Februar 2023]).