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

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.

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.

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.

Aufwändiger ist hingegen die Bestimmung der genotypischen Diversität in einer Population, wozu verschiedene Verfahren für unterschiedliche Genomarten entwickelt und erprobt wurden. 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.

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.

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.

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. 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. Eine bekannte Gegenmaßnahme ist der Wechsel zu alternativen Populationsmodellen, die Substrukturen in die Population einführen, 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, die Evolutionsstrategie, andere EAs oder memetische Algorithmen gezeigt worden.

Anpassung von Selektion, Mutation und Rekombination

Bei der Feststellung von Stagnation und/oder fortgeschrittener Konvergenz wird häufig mit einer Anpassung von Strategieparametern, angepassten Operatorvarianten oder der Operatorenauswahl 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. Auch entsprechend angepasste Selektionsverfahren kommen zum Einsatz.
• eine Erhöhung der Mutationsrate, um die verlorene Vielfalt wieder herzustellen.
• 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. Oder es werden entsprechend angepasste Operatoren oder solche verwendet, die die elterlichen Gene stärker mischen, wie z. B. Uniform Crossover anstelle von Crossover an wenigen Punkten.

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. 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 gefunden werden und in 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 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.

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

Einzelnachweise

1. A.E. Eiben, J.E. Smith: Introduction to Evolutionary Computing (= Natural Computing Series). 2. Auflage. Springer, Berlin, Heidelberg 2015, ISBN 978-3-662-44873-1, Multimodal Problems, Selection, and the Need for Diversity, S. 91–98, doi:10.1007/978-3-662-44874-8. 
2. Kenneth A. De Jong: Analysis of the behavior of a class of genetic adaptive systems. Dissertation. University of Michigan, Ann Arbor, MI, USA 1975 (handle.net). 
3. Yee Leung, Yong Gao, Zong-Ben Xu: Degree of population diversity - a perspective on premature convergence in genetic algorithms and its Markov chain analysis. In: IEEE Transactions on Neural Networks. Band 8, Nr. 5, September 1997, ISSN 1045-9227, S. 1165–1176, doi:10.1109/72.623217 (ieee.org [abgerufen am 25. Oktober 2023]). 
4. James E. Baker: Adaptive Selection Methods for GeneticAlgorithms. In: John J. Grefenstette (Hrsg.): Proceedings of the First International Conference on Genetic Algorithms and their Applications (ICGA). L. Erlbaum, Hillsdale, NJ, USA 1985, ISBN 978-0-8058-0426-3, S. 101–111. 
5. M. Srinivas, L.M. Patnaik: Adaptive probabilities of crossover and mutation in genetic algorithms. In: IEEE Transactions on Systems, Man, and Cybernetics. Band 24, Nr. 4, April 1994, S. 656–667, doi:10.1109/21.286385. 
6. Christian Blume, Wilfried Jakob: GLEAM - General Learning Evolutionary Algorithm and Method : ein Evolutionärer Algorithmus und seine Anwendungen. KIT Scientific Publishing, Karlsruhe, FRG 2009, ISBN 978-3-86644-436-2, Stagnationsorientierte Abbruchkriterien, S. 51, doi:10.5445/ksp/1000013553. 
7. Rasmus K. Ursem: Diversity-Guided Evolutionary Algorithms. In: J.J. Merelo Guervós et al. (Hrsg.): Parallel Problem Solving from Nature — PPSN VII. LNCS 2439. Springer, Berlin, Heidelberg 2002, ISBN 978-3-540-44139-7, S. 462–471, doi:10.1007/3-540-45712-7_45. 
8. H. Shimodaira: A diversity-control-oriented genetic algorithm (DCGA): performance in function optimization. In: Proceedings of the 2001 Congress on Evolutionary Computation (CEC 2001). Band 1. IEEE, 2001, ISBN 978-0-7803-6657-2, S. 44–51, doi:10.1109/CEC.2001.934369. 
9. K.Q. Zhu: A diversity-controlling adaptive genetic algorithm for the vehicle routing problem with time windows. In: Conf. Proc. of the 15th IEEE International Conference on Tools with Artificial Intelligence. IEEE Comput. Soc, 2003, ISBN 978-0-7695-2038-4, S. 176–183, doi:10.1109/TAI.2003.1250187. 
10. Brian McGinley, John Maher, Colm O'Riordan, Fearghal Morgan: Maintaining Healthy Population Diversity Using Adaptive Crossover, Mutation, and Selection. In: IEEE Transactions on Evolutionary Computation. Band 15, Nr. 5, Oktober 2011, ISSN 1089-778X, S. 692–714, doi:10.1109/TEVC.2010.2046173. 
11. Wilfried Jakob: Applying Evolutionary Algorithms Successfully: A Guide Gained from Real-world Applications. In: KIT Scientific Working Papers. Nr. 170. KIT Scientific Publishing, 2021, ISSN 2194-1629, Handling Strategy Parameters and the Population Size in Particular, S. 20–21, doi:10.5445/ir/1000135763, arxiv:2107.11300 (kit.edu [abgerufen am 27. Oktober 2023]). 
12. V. Scott Gordon, Darrell Whitley: Serial and Parallel Genetic Algorithms as Function Optimizers. In: Stephanie Forrest (Hrsg.): Proceedings of the Fifth International Conference on Genetic Algorithms (ICGA). Morgan Kaufmann, San Francisco, CA, USA 1993, ISBN 978-1-55860-299-1, S. 177–183 (colostate.edu [PDF]). 
13. Erick Cantú-Paz: A survey of parallel genetic algorithms. In: Calculateurs Paralleles. Band 10, Nr. 2, 1998, S. 141–171 (uma.es [PDF]). 
14. V. Scott Gordon, Keith Mathias, Darrell Whitley: Cellular genetic algorithms as function optimizers: locality effects. ACM Press, 1994, ISBN 978-0-89791-647-9, S. 237–241, doi:10.1145/326619.326732 (acm.org [abgerufen am 26. Oktober 2023]). 
15. Erick Cantú-Paz: Efficient and Accurate Parallel Genetic Algorithms. Dissertation, University of Illinois, Urbana-Champaign, USA (= Genetic Algorithms and Evolutionary Computation. Band 1). Springer US, Boston, MA 2001, ISBN 978-1-4613-6964-6, doi:10.1007/978-1-4615-4369-5 (springer.com [abgerufen am 26. Oktober 2023]). 
16. Martina Gorges-Schleuter: A comparative study of global and local selection in evolution strategies. In: Parallel Problem Solving from Nature — PPSN V. LNCS 1498. Springer, Berlin, Heidelberg 1998, ISBN 978-3-540-65078-2, S. 367–377, doi:10.1007/bfb0056879 (springer.com [abgerufen am 26. Oktober 2023]). 
17. Wilfried Jakob: A general cost-benefit-based adaptation framework for multimeme algorithms. In: Memetic Computing. Band 2, Nr. 3, September 2010, ISSN 1865-9284, S. 201–218, doi:10.1007/s12293-010-0040-9. 
18. Enrique Alba, Bernabé Dorronsoro, Hugo Alfonso: Cellular Memetic Algorithms. In: Journal of Computer Science and Technology. Band 5, Nr. 4, 1. Dezember 2005, ISSN 1666-6038, S. 257–263 (edu.ar). 
19. A.E. Eiben, R. Hinterding, Z. Michalewicz: Parameter control in evolutionary algorithms. In: IEEE Transactions on Evolutionary Computation. Band 3, Nr. 2, Juli 1999, S. 124–141, doi:10.1109/4235.771166. 
20. Larry J. Eshelman, J. David Schaffer: Preventing Premature Convergence in Genetic Algorithms by Preventing Incest. In: Richard K. Belew, Lashon, B. Booker (Hrsg.): Conf. Proc of the Fourth Int. Conf. on Genetic Algorithms. Morgan Kaufmann, San Mateo, CA, USA 1991, ISBN 1-55860-208-9, S. 115–122 (researchgate.net). 
21. A.E. Eiben, J.E. Smith: Introduction to Evolutionary Computing (= Natural Computing Series). 2. Auflage. Springer, Berlin, Heidelberg 2015, ISBN 978-3-662-44873-1, Automatic Speciation Using Mating Restrictions, S. 95, doi:10.1007/978-3-662-44874-8. 
22. Cheng Chen, Zhenyu Yang, Yuejin Tan, Renjie He: Diversity Controlling Genetic Algorithm for Order Acceptance and Scheduling Problem. In: Mathematical Problems in Engineering. Band 2014, 2014, ISSN 1024-123X, S. 1–11, doi:10.1155/2014/367152. 
23. Farhad Nadi, Ahamad Tajudin Khader: Adaptation of Parametric Uniform Crossover in Genetic Algorithm. Academy & Industry Research Collaboration Center (AIRCC), 2013, ISBN 978-1-921987-00-7, S. 443–450, doi:10.5121/csit.2013.3650 (airccj.org [PDF; abgerufen am 13. November 2023]). 
24. Ole J. Mengshoel, David E. Goldberg: The Crowding Approach to Niching in Genetic Algorithms. In: Evolutionary Computation. Band 16, Nr. 3, September 2008, ISSN 1063-6560, S. 315–354, doi:10.1162/evco.2008.16.3.315 (mit.edu [abgerufen am 29. Oktober 2023]). 
25. Severino F. Galan, Ole J. Mengshoel: Generalized crowding for genetic algorithms. In: Annual Conference on Genetic and Evolutionary Computation. ACM, 2010, ISBN 978-1-4503-0072-8, S. 775–782, doi:10.1145/1830483.1830620. 
26. Zbigniew Michalewicz: Genetic algorithms + data structures = evolution programs. 3. überarbeitete Auflage. Springer, Berlin, Paris 1996, ISBN 978-3-540-60676-5, S. 58. 
27. Wilfried Jakob: Eine neue Methodik zur Erhöhung der Leistungsfähigkeit Evolutionärer Algorithmen durch die Integration lokaler Suchverfahren. Dissertation. In: Forschungszentrum Karlsruhe GmbH (Hrsg.): Wissenschaftliche Berichte. FZKA 6965, 2004, ISSN 0947-8620, Stagnationsindikator Genetische Varianz, S. 50–55 (researchgate.net [PDF]). 
28. B. Sareni, L. Krahenbuhl: Fitness sharing and niching methods revisited. In: IEEE Transactions on Evolutionary Computation. Band 2, Nr. 3, September 1998, S. 97–106, doi:10.1109/4235.735432 (ieee.org [abgerufen am 29. Oktober 2023]). 
29. David E. Goldberg, Jon Richardson: Genetic algorithms with sharing for multimodal function optimization. In: John J. Grefenstette (Hrsg.): Genetic Algorithms and their Applications: Conf. Proc. of the 2nd Int. Conf. on Genetic Algorithms (ICGA). Lawrence Erlbaum Associates, Hillsdale, NJ, USA 1987, ISBN 0-8058-0159-6, S. 41–49. 
30. Pietro S. Oliveto, Dirk Sudholt, Christine Zarges: On the benefits and risks of using fitness sharing for multimodal optimisation. In: Theoretical Computer Science. Band 773, Juni 2019, S. 53–70, doi:10.1016/j.tcs.2018.07.007 (elsevier.com [abgerufen am 29. Oktober 2023]).