Memetischer Algorithmus

Memetische Algorithmen (MA) sind eine Erweiterung von global suchenden populationsbasierten Metaheuristiken um Verfahren zur lokalen Suche, des maschinellen Lernens oder anderer Verbesserungs- oder Optimierungsverfahren. Typische Vertreter erweitern einen Evolutionären Algorithmus (EA) als global suchendes Verfahren um ein oder mehrere lokale Suchverfahren oder Heuristiken, die als Mem bezeichnet werden. Sie können problemspezifisch sein, müssen es aber nicht.[1]

Häufig werden die Mems bei der Nachkommenerzeugung eines EA eingesetzt, etwa indem sie auf alle oder einen Teil der Nachkommen einer Generation mit dem Ziel einer Qualitätsverbesserung angewandt werden. Eine weitere Möglichkeit besteht darin, sie zur Erzeugung von Nachkommen ausgehend von einem Elternteil einzusetzen.

Einführung

Die Grundidee der memetischen Algorithmen besteht darin, global- und lokalsuchende Verfahren vorteilhaft miteinander zu kombinieren. Von Metaheuristiken wie den EA ist bekannt, dass sie gut im Auffinden vielversprechender Regionen im Suchraum sind, aber schlecht bei der Konvergenz zu einem Optimum und sei es auch nur ein lokales. Bei lokalen Verfahren ist es genau anders herum: Sie bleiben auf eine Umgebung ihres Startpunktes beschränkt, finden aber vergleichsweise schnell ein sich darin befindliches (Sub)Optimum. Das Ziel der Kombination beider Verfahrensklassen ist eine Reduktion des meist in Fitnessberechnungen gemessenen Aufwands und eine Erhöhung der Zuverlässigkeit, das Optimum zu finden. Darüber hinaus wurde auch beobachtet, dass der Bereich geeigneter und für einen Erfolg erforderlicher Populationsgrößen deutlich sinkt.[2]

Memetische Algorithmen wurden bereits auf eine Vielzahl realer Problemstellungen angewandt, zum Beispiel zur Lösung von Routingproblemen,[3] zur Vorhersage von Proteinstrukturen,[3] zur Lösung von Schedulingproblemen mit Nebenbedingungen[4] oder von Workflows zu heterogenen Ressourcen,[5] zur Bearbeitung von Designproblemen[6] oder für die Erstellung von Flugplänen.[7]

Die Memetik ist eine Forschungsrichtung, in der evolutionäre Prozesse untersucht werden, die bei der Verbreitung und Veränderung von Ideen und anderen kulturellen Konzepten auftreten. Diese Prozesse können als natürliches Vorbild für die beschriebenen Algorithmen aufgefasst werden, daher die Bezeichnung memetisch.

MAs werden in der Literatur auch häufig als Baldwinian EAs, Lamarckian EAs, cultural algorithms oder genetic local search bezeichnet.

Theoretische Grundlage

Die No-free-Lunch-Theoreme der Optimierung[8] und der Suche[9] besagen, dass alle Optimierungsstrategien bezogen auf die Menge aller Optimierungsprobleme gleich effektiv sind. Im Umkehrschluss bedeutet dies, dass man folgendes erwarten kann: Je effizienter ein Algorithmus ein Problem oder eine Problemklasse löst, desto weniger ist er allgemein anwendbar und auf desto mehr problemspezifischem Wissen baut er auf. Diese Erkenntnis führt unmittelbar zu der Empfehlung, allgemein anwendbare Metaheuristiken um anwendungsspezifische Verfahren zu ergänzen[10] und damit zum Konzept der MAs.

Gestaltungsmöglichkeiten Memetischer Algorithmen

In diesem Abschnitt wird ohne Beschränkung der Allgemeinheit der sprachlichen Einfachheit halber von der Erweiterung eines EA zu einem MA mit lokaler Suche ausgegangen.

Beim Design eines MA sind im Wesentlichen die folgenden fünf Fragen zu klären:[11][12][4]

  1. Welches lokale Verfahren soll genutzt werden?
  2. Soll durch eine gefundene Verbesserung das Genom angepasst werden?
  3. Wie werden die Nachkommen für die lokale Verbesserung ausgewählt?
  4. Wie oft soll eine lokale Verbesserung versucht werden?
  5. Wie intensiv soll die lokale Suche sein?

Eine geeignete Beantwortung vor allem der ersten beiden Fragen kann entscheidend für den Erfolg eines MA im Vergleich zu seinem Basis-EA sein.

Bei Metaheuristiken wie den EA spielt das Verhältnis zwischen Breiten- und Tiefensuche eine entscheidende Rolle und die Hinzunahme eines lokalen Verfahrens verschiebt die Gewichte zu Gunsten der Tiefensuche. In welchem Ausmaß dies geschieht, kann vor allem durch die Antwort auf die letzten beiden Fragen gesteuert werden.

Die genannten Gestaltungsmöglichkeiten können entweder ganz oder teilweise fest in den MA implementiert werden oder als Strategieparameter einer nachträglichen Änderung zugänglich gemacht werden.

Welches lokale Verfahren soll genutzt werden?

Die richtige Auswahl eines für die aktuelle Anwendung geeigneten lokalen Verfahrens ist wesentlich für den Erfolg.[12][13] Geeignete Verfahren sollten in der Lage sein, vorgegebene Lösungen des Problems zu verbessern. Sie können, müssen aber nicht auf die aktuelle Aufgabenstellung zugeschnitten sein. Verwendet man z. B. allgemein anwendbare lokale Suchverfahren, wie das Gauß-Seidel-Verfahren,[14] den Complex-Algorithmus[15] oder das Rosenbrock-Verfahren,[16] so wird die generelle Anwendbarkeit des EAs lediglich auf die den lokalen Verfahren zugänglichen Probleme der kontinuierlichen oder gemischt-ganzzahligen Optimierung beschränkt.[2] Bei einer diskreten oder gemischt-ganzzahligen Optimierung werden die Werte an der Schnittstelle zwischen EA und Mem bei Bedarf gerundet.

Die oben zitierten No-free-Lunch-Theoreme empfehlen bekanntlich, anwendungsspezifische lokale Suchverfahren oder Heuristiken als Mem zu verwenden. Trotzdem sollte man gegebenenfalls prüfen, ob sie im konkreten Fall tatsächlich eine größere Verbesserung bewirken als allgemein anwendbare.

Soll durch eine gefundene Verbesserung das Genom angepasst werden?

Entweder wirkt eine gefundene Verbesserung nur durch die bessere Fitness (Baldwin-Evolution) oder es wird auch das Genom entsprechend angepasst (Lamarcksche Evolution). Diese Frage wurde bereits in den 1990er Jahren kontrovers in der Literatur diskutiert, wobei festgestellt wurde, dass der konkrete Anwendungsfall eine wesentliche Rolle spielt.[17][18][19] Der Hintergrund der Debatte besteht darin, dass eine Anpassung des Genoms eine vorzeitige Konvergenz fördern kann. Dieses Risiko kann durch andere Maßnahmen zur besseren Ausgewogenheit zwischen Breiten- und Tiefensuche, wie der Verwendung strukturierter Populationen, wirksam verringert werden.[4]

Wie werden die Nachkommen für die lokale Verbesserung ausgewählt?

Die Auswahl kann zufällig oder fitnessbasiert erfolgen. Dabei kann die gesamte Nachkommenschaft einer Generation zur Grundlage der Auswahl gemacht werden[13] oder jeweils nur die Nachkommen einer Paarung.[4] Bei Mems mit geringem Rechenaufwand kann es auch sinnvoll sein, es auf alle Nachkommen anzuwenden.[20]

Wie oft soll eine lokale Verbesserung versucht werden?

Eine wesentliche Frage ist, wie oft eine Verbesserung durch ein Mem versucht werden soll. Zum Beispiel bei jeder Paarung oder nur bei einem Teil? Dieser Parameter wird auch als local search frequency bezeichnet und er beeinflusst das Suchverhalten signifikant.

Wie intensiv soll die lokale Suche sein?

Heuristiken und lokale Suchverfahren arbeiten in der Regel iterativ und brechen beim Absinken der Verbesserungen unter ein vorgegebenes Limit ab.[14][15][16] Über die Vorgabe der Abbruchschranke und/oder eines Iterationslimits kann die Intensität der lokalen Suche kontrolliert werden. Dieser Parameter ist auch als local search intensity bekannt.

Mit Hilfe der Strategieparameter local search frequency und intensity kann die Verteilung der verfügbaren Rechenleistung zwischen globaler und lokaler Suche gesteuert werden und damit auch das Verhältnis von Breiten- zu Tiefensuche. Insbesondere eine Erhöhung der Intensität der lokalen Suche vergrößert die Tiefensuche. Die Bedeutung beider Parameter wurde bereits früh beschrieben[12] und von Land für den Bereich der kombinatorischen Optimierung untersucht.[21]

Multimem Algorithmen

Da die Auswahl eines geeigneten Mems von entscheidender Bedeutung für den Erfolg ist, bietet es sich an, mehrere geeignet erscheinende Mems zu verwenden und zu erfassen, wie häufig die durch jedes Mem bearbeiteten Individuen in die Nachfolgegeneration übernommen werden. Vor einem Ausschluss oder einer zu starken Selektion sollte man aber beachten, dass das beste Mem während des Verlaufs der Evolution zumindest bei kombinatorischen Aufgabenstellungen wechseln kann.[22] Dies wurde von Ong und Keane auch für kontinuierliche Probleme bestätigt, die eine adaptive Auswahl der Mems aus einer vorgegebenen Menge entsprechend ihrem Erfolg untersucht haben.[13] Ähnlich geht ein Kosten-Nutzen-basierter Ansatz zur adaptiven Kontrolle der oben genannten Strategieparameter vor. Er basierend auf dem Nutzen, berechnet durch den kumulierten Fitnessgewinn, und den Kosten, berechnet durch die Anzahl der dazu erforderlichen Bewertungen, die pro Strategieparameter aus den Einstellungen resultieren. Es konnte für eine Reihe von Testfunktionen und eine Schedulingaufgabe mit Nebenbedingungen gezeigt werden, dass damit Lösungen von hoher Qualität bei deutlich geringerem Aufwand als dem Basis-EA erreicht werden können.[4] Ein Überblick über selbst-adaptive und koevolutionäre Multimem Algorithmen kann im Handbook of Memetic Algorithms[23] gefunden werden.

Bei der Koevolution werden alle oder ein Teil der eingangs genannten Strategieparameter mit in das Genom codiert und unterliegen so zusammen mit den Entscheidungsvariablen der Evolution. Der Grundgedanke dabei besteht in Annahme, dass durch gute Strategieparametereinstellungen auch gute Problemlösungen entstehen, die sich schließlich durchsetzen. Dass dieser Ansatz für Strategieparameter, die ohne Einfluss auf den Aufwand sind, gut funktioniert, zeigt der Erfolg der Evolutionsstrategie mit ihren derart eingestellten Mutationsschrittweiten.

Die Erfahrungen, die sich beim Lauf eines adaptiven Multimem Algorithmus in Form von Memauswahl und Einstellungen der Memparameter ergeben, können dazu genutzt werden, die Starteinstellungen für zukünftige Läufe anzupassen. Dabei ist aber zu beachten, dass anfängliche Einstellungen eines MA-Laufs an dessen Ende nicht mehr unbedingt gut geeignet sein müssen oder umgekehrt. So ist beispielsweise eine anfängliche geringe Genauigkeit bei der Bestimmung lokaler Optima meist ausreichend und es wird erst am Ende der Suche wichtig, gefundene lokale Optima genau zu bestimmen, nämlich dann, wenn ihre Unterschiede geringer werden.

Literatur

  • Ferrante Neri, Carlos Cotta, Pablo Moscato: Handbook of Memetic Algorithms. SCI 379, Springer, Berlin, Heidelberg, 2012. ISBN 978-3-642-23247-3 doi:10.1007/978-3-642-23247-3
  • Memetic Computing, International Journal, Springer, seit März 2009, Journal Homepage
  • P. Moscato, On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms, Caltech Concurrent Computation Program, C3P Report 826, (1989).
  • Enrique Alba, Bernabé Dorronsoro, Hugo Alfonso: Cellular Memetic Algorithms. Journal of Computer Science and Technology, 5(4), 2005, S. 257–263. PDF

Einzelnachweise

  1. ↑ Memetic Computing. Aims and Scope of the Journal. International Journal, seit März 2009. Springer, Berlin, Heidelberg, New York (springer.com).
  2. ↑ a b Wilfried Jakob: HyGLEAM - an Approach to Generally Applicable Hybridization of Evolutionary Algorithms. In: J.J. Merelo et al. (Hrsg.): Conf. Proc. of Parallel Problem Solving from Nature (PPSN VII). LNCS 2439. Springer, Berlin, Heidelberg, New York 2002, S. 527–536 (kit.edu).
  3. ↑ a b William E. Hart, Natalio Krasnogor, James E. Smith: Recent Advances in Memetic Algorithms. Studies in Fuzziness and Soft Computing, Nr. 166. Springer, Berlin, Heidelberg 2005, ISBN 3-540-22904-3.
  4. ↑ a b c d e 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.
  5. ↑ Wilfried Jakob, Sylvia Strack, Alexander Quinte, Günther Bengel, Karl-Uwe Stucky, Wolfgang Süß: Fast Rescheduling of Multiple Workflows to Constrained Heterogeneous Resources Using Multi-Criteria Memetic Computing. In: Algorithms. Band 6, Nr. 2, 22. April 2013, ISSN 1999-4893, S. 245–277, doi:10.3390/a6020245.
  6. ↑ Andrea Caponio, Ferrante Neri: Memetic Algorithms in Engineering and Design. In: Ferrante Neri, Carlos Cotta, Pablo Moscato (Hrsg.): Handbook of Memetic Algorithms. Serie Studies in Computational Intelligence, Nr. 379. Springer, Berlin, Heidelberg 2012, ISBN 978-3-642-23246-6, doi:10.1007/978-3-642-23247-3.
  7. ↑ Edmund K. Burke, Patrick De Causmaecker, Geert De Maere, Jeroen Mulder, Marc Paelinck, Greet Vanden Berghe: A multi-objective approach for robust airline scheduling. In: Computers & Operations Research. Band 37, Nr. 5, Mai 2010, S. 822–832, doi:10.1016/j.cor.2009.03.026 (elsevier.com [abgerufen am 31. Januar 2022]).
  8. ↑ D.H. Wolpert, W.G. Macready: No free lunch theorems for optimization. In: IEEE Transactions on Evolutionary Computation. Band 1, Nr. 1, April 1997, S. 67–82, doi:10.1109/4235.585893.
  9. ↑ David Hilton Wolpert, William G. Macready: No free lunch theorems for search. In: Technical Report. SFI-TR-95-02-010. Santa Fe Institute, Sante Fe, NM, USA 1995 (byu.edu [PDF]).
  10. ↑ Lawrence Davis: Handbook of genetic algorithms. Van Nostrand Reinhold, New York 1991, ISBN 978-0-442-00173-5.
  11. ↑ William E. Hart, Natalio Krasnogor, Jim E. Smith: Editorial Introduction. In: Evolutionary Computation. special issue on memetic algorithms. Band 12, Nr. 3, 2004, S. v-vi.
  12. ↑ a b c William E. Hart: Adaptive Global Optimization with Local Search. Dissertation. University of California, USA 1994.
  13. ↑ a b c Y.S. Ong, A.J. Keane: Meta-Lamarckian Learning in Memetic Algorithms. In: IEEE Transactions on Evolutionary Computation. Band 8, Nr. 2, April 2004, ISSN 1089-778X, S. 99–110, doi:10.1109/TEVC.2003.819944.
  14. ↑ a b James M. Ortega, Maxine L. Rockoff: Nonlinear Difference Equations and Gauss-Seidel Type Iterative Methods. In: SIAM Journal on Numerical Analysis. Band 3, Nr. 3, September 1966, ISSN 0036-1429, S. 497–513, doi:10.1137/0703043.
  15. ↑ a b M. J. Box: A New Method of Constrained Optimization and a Comparison With Other Methods. In: The Computer Journal. Band 8, Nr. 1, 1. April 1965, ISSN 0010-4620, S. 42–52, doi:10.1093/comjnl/8.1.42.
  16. ↑ a b H. H. Rosenbrock: An Automatic Method for Finding the Greatest or Least Value of a Function. In: The Computer Journal. Band 3, Nr. 3, 1. März 1960, ISSN 0010-4620, S. 175–184, doi:10.1093/comjnl/3.3.175.
  17. ↑ Frédéric Gruau, Darrell Whitley: Adding Learning to the Cellular Development of Neural Networks: Evolution and the Baldwin Effect. In: Evolutionary Computation. Band 1, Nr. 3, September 1993, ISSN 1063-6560, S. 213–233, doi:10.1162/evco.1993.1.3.213 (mit.edu [abgerufen am 31. Januar 2022]).
  18. ↑ David Orvosh, Lawrence Davis: Shall We Repair? Genetic Algorithms, Combinatorial Optimization, and Feasibility Constraints. In: S. Forrest (Hrsg.): Conf. Proc. of Int. Conf. on Genetic Algorithms (ICGA). Morgan Kaufmann, San Mateo, CA, USA 1993, S. 650 (semanticscholar.org).
  19. ↑ Darrell Whitley, Vahl Scott Gordon, Keith E. Mathias: Lamarckian Evolution, the Baldwin Effect and Function Optimization. In: Parallel Problem Solving from Nature (PPSN III). LNCS, Nr. 866. Springer, Berlin, Heidelberg 1994, ISBN 978-3-540-58484-1, S. 5–15, doi:10.1007/3-540-58484-6_245.
  20. ↑ K.W.C. Ku, Man Wai Mak, Wan-Chi Siu: A study of the Lamarckian evolution of recurrent neural networks. In: IEEE Transactions on Evolutionary Computation. Band 4, Nr. 1, April 2000, S. 31–42, doi:10.1109/4235.843493.
  21. ↑ Mark William Shannon Land: Evolutionary Algorithms with Local Search for Combinatorial Optimization. Dissertation. University of California, 1998, doi:10.5555/928346.
  22. ↑ James E. Smith: Self-Adaptation in Evolutionary Algorithms for Combinatorial Optimisation. In: Adaptive and Multilevel Metaheuristics. Band 136. Springer, Berlin, Heidelberg 2008, ISBN 978-3-540-79437-0, S. 31–57, doi:10.1007/978-3-540-79438-7_2.
  23. ↑ James E. Smith: Self-adaptative and Coevolving Memetic Algorithms. In: Ferrante Neri, Carlos Cotta, Pablo Moscato (Hrsg.): Handbook of Memetic Algorithms. SCI, Nr. 379. Springer, Berlin, Heidelberg 2012, ISBN 978-3-642-23246-6, doi:10.1007/978-3-642-23247-3.