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.[1] 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.[2] Werden hingegen andere global suchende Metaheuristiken zu Grunde gelegt, spricht man häufig auch von Memetic Computing oder Memetic Computation. MAs sind also ein Teilgebiet des Memetic Computing.[3][4]

Häufig werden die Meme 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 umgekehrt: Sie bleiben auf eine Umgebung ihres Startpunktes beschränkt, finden aber vergleichsweise schnell ein sich darin befindendes (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 bei der Erweiterung eines EAs zum MA deutlich sinkt.[5]

Der Anwendungsbereich memetischer Algorithmen entspricht zunächst dem Anwendungsfeld des zu Grunde liegenden global suchenden Verfahrens, kann aber durch die Wahl anwendungsspezifischer Meme eingeschränkt werden. Als Beispiel mögen die häufig zur globalen Suche verwendeten EAs dienen, die unter anderem sowohl für kombinatorische Probleme als auch für Optimierungen in kontinuierlichen oder gemischt-ganzzahligen Parameterräumen geeignet sind. Wenn ein solcher EA zum Beispiel um ein Mem zur Verbesserung von Permutationen ergänzt wird, erfolgt implizit eine Spezialisierung auf kombinatorische Aufgabenstellungen und damit eine Einschränkung des sinnvollen Einsatzfeldes.

MAs wurden unter anderem zur Bearbeitung vieler klassischer NP-Probleme eingesetzt, darunter Scheduling,[6] Graphpartitionierung,[7] minimale Graphenfärbung,[8] Travelling-Salesman-Problem,[9] mehrdimensionaler Knapsack,[10][11] quadratisches Zuordnungsproblem[12] und Bin Packing.[13]

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.

Basisalgorithmus

Da viele MA-Implementierungen auf EAs beruhen, wird nachfolgend in Anlehnung an Krasnogor der Pseudocode eines MAs angegeben,[14] der optional auch die Anpassung der Chromosome an die gefundenen Verbesserungen (Lamarcksche Evolution) enthält.

Pseudocode eines Memetischen Algorithmus basierend auf einem elitären EA mit sexueller Reproduktion:
   Initialisierung: ;
                    Erzeuge eine zufällige Startpopulation ;
                    Berechne die Fitness ;  // initiale Bewertung
   while Abbruchkriterien sind nicht erfüllt do
       Partnerwahl: Wähle entsprechend  eine Teilmenge von  und speichere sie in ;
       Nachkommen:  Rekombiniere und mutiere Individuen  und speichere sie in ;
       Lernphase:    Verbessere  durch lokale Suche oder eine Heuristik ;
       Bewertung:   Berechne die Fitness ;
       if Lamarcksche Evolution then
          Update: Passe das Chromosom von  gemäß der jeweiligen Verbesserung  an;
       fi
       Neue Generation: Erzeuge  durch Auswahl von Individuen aus  und ;
       ;
   end while
   Ergebnis: Liefere bestes Individuum  als Ergebnis ab;

Es gibt einige Alternativen zu diesem MA-Schema. Zum Beispiel:

  • Die Eltern können anstelle der Nachkommen lokal verbessert werden.
  • Anstelle aller Nachkommen kann auch nur ein zufällig ausgewählter oder fitnessabhängiger Teil lokal verbessert werden.
  • Nachkommen werden (zusätzlich) aus einem Elter durch ein geeignetes Mem erzeugt.

Darüber hinaus können alle oder nur einige Individuen der Startpopulation durch das oder die Meme verbessert werden. Dabei ist auf eine ausreichende genotypische Diversität der so modifizierten Startpopulation zu achten und gegebenenfalls nur ein Teil zu verbessern.

Theoretische Grundlage

Die No-free-Lunch-Theoreme der Optimierung[15] und der Suche[16] 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[17] 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:[18][19][20]

  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.[19][21] 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,[22] den Complex-Algorithmus[23] oder das Rosenbrock-Verfahren,[24] so wird die generelle Anwendbarkeit des EAs lediglich auf die den lokalen Verfahren zugänglichen Probleme der kontinuierlichen oder gemischt-ganzzahligen Optimierung beschränkt.[5] 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.[25][26][27] 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.[20]

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[21] oder jeweils nur die Nachkommen einer Paarung.[20] Bei Memen mit geringem Rechenaufwand kann es auch sinnvoll sein, es auf alle Nachkommen anzuwenden.[28]

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.[22][23][24] Ü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[19] und von Land für den Bereich der kombinatorischen Optimierung untersucht.[29]

Multimem Algorithmen

Da die Auswahl eines geeigneten Mems von entscheidender Bedeutung für den Erfolg ist, bietet es sich an, mehrere geeignet erscheinende Meme 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.[30] 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.[21] Ä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.[20] Ein Überblick über selbst-adaptive und koevolutionäre Multimem Algorithmen kann im Handbook of Memetic Algorithms[31] 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.[32] 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.

Anwendungen

Memetische Algorithmen wurden bereits auf eine Vielzahl realer Problemstellungen angewandt. Die nachfolgende Aufzählung ist exemplarisch zu sehen und erhebt keinesfalls den Anspruch auf Vollständigkeit: Lösung von Routingproblemen,[33] VLSI-Design,[34] Vorhersage von Proteinstrukturen,[35][32] Scheduling mit Nebenbedingungen,[36][20][37] automatische Zeitplanung,[38][39] Scheduling von Workflows zu heterogenen Ressourcen,[40] Bearbeitung von Designproblemen,[41][42][43] Clustering von Genexpressionsprofilen,[44] Optimierung der Ausführung paralleler Programme,[45] Business Analytics,[46] Merkmalsauswahl und -identifikation[47][48] oder Erstellung von Flugplänen.[49]

Literatur

Einzelnachweise

  1. ↑ Pablo Moscato: On Evolution, Search, Optimization, Genetic Algorithms and MartialArts: Towards Memetic Algorithms. Caltech Concurrent Computation Program, Technical Report 826. California Institute of Technology, Pasadena, CA, USA 1989, S. 19–20 (researchgate.net [PDF]).
  2. ↑ Memetic Computing. Aims and Scope of the Journal. International Journal, seit März 2009. Springer, Berlin, Heidelberg, New York (springer.com).
  3. ↑ Xianshun Chen, Yew-Soon Ong, Meng-Hiot Lim, Kay Chen Tan: A Multi-Facet Survey on Memetic Computation. In: IEEE Transactions on Evolutionary Computation. Band 15, Nr. 5, Oktober 2011, ISSN 1089-778X, S. 591–607, doi:10.1109/TEVC.2011.2132725 (ieee.org [abgerufen am 14. September 2023]).
  4. ↑ Yew-Soon Ong, Meng Lim, Xianshun Chen: Research Frontier: Memetic Computation - Past, Present & Future. In: IEEE Computational Intelligence Magazine. Band 5, Nr. 2, Mai 2010, ISSN 1556-603X, S. 24–31, doi:10.1109/MCI.2010.936309 (ieee.org [abgerufen am 14. September 2023]).
  5. ↑ 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, doi:10.1007/3-540-45712-7_51 (kit.edu).
  6. ↑ Carlos Cotta, Antonio J. Fernàndez: Memetic Algorithms in Planning, Scheduling, and Timetabling. In: Evolutionary Scheduling. Band 49. Springer, Berlin, Heidelberg 2007, ISBN 978-3-540-48582-7, S. 1–30, doi:10.1007/978-3-540-48584-1_1.
  7. ↑ Philippe Galinier, Zied Boujbel, Michael Coutinho Fernandes: An efficient memetic algorithm for the graph partitioning problem. In: Annals of Operations Research. Band 191, Nr. 1, November 2011, ISSN 0254-5330, S. 1–22, doi:10.1007/s10479-011-0983-3.
  8. ↑ Zhipeng Lü, Jin-Kao Hao: A memetic algorithm for graph coloring. In: European Journal of Operational Research. Band 203, Nr. 1, Mai 2010, S. 241–250, doi:10.1016/j.ejor.2009.07.016 (elsevier.com [abgerufen am 20. September 2023]).
  9. ↑ Gregory Gutin, Daniel Karapetyan: A memetic algorithm for the generalized traveling salesman problem. In: Natural Computing. Band 9, Nr. 1, März 2010, ISSN 1567-7818, S. 47–60, doi:10.1007/s11047-009-9111-6.
  10. ↑ Abdellah Rezoug, Dalila Boughaci, Mohamed Badr-El-Den: Memetic Algorithm for Solving the 0-1 Multidimensional Knapsack Problem. In: Progress in Artificial Intelligence. Band 9273. Springer International Publishing, Cham 2015, ISBN 978-3-319-23484-7, S. 298–304, doi:10.1007/978-3-319-23485-4_31.
  11. ↑ Ender Özcan, Can Başaran: A case study of memetic algorithms for constraint optimization. In: Soft Computing. Band 13, Nr. 8-9, Juli 2009, ISSN 1432-7643, S. 871–882, doi:10.1007/s00500-008-0354-4.
  12. ↑ P. Thainiam: The Effects of Memes on Memetic Algorithms for Solving Quadratic Assignment Problem. IEEE, 2019, ISBN 978-1-72813-804-6, S. 1334–1338, doi:10.1109/IEEM44572.2019.8978780 (ieee.org [abgerufen am 20. September 2023]).
  13. ↑ Kristina Yancey Spencer, Pavel V. Tsvetkov, Joshua J. Jarrell: A greedy memetic algorithm for a multiobjective dynamic bin packing problem for storing cooling objects. In: Journal of Heuristics. Band 25, Nr. 1, Februar 2019, ISSN 1381-1231, S. 1–45, doi:10.1007/s10732-018-9382-0.
  14. ↑ Natalio Krasnogor: Studies on the Theory and Design Space of Memetic Algorithms. Dissertation. University of the West of England, Bristol, UK 2002, S. 23 (englisch, bl.uk).
  15. ↑ 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.
  16. ↑ 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]).
  17. ↑ Lawrence Davis: Handbook of genetic algorithms. Van Nostrand Reinhold, New York 1991, ISBN 0-442-00173-8.
  18. ↑ William E. Hart, Natalio Krasnogor, Jim E. Smith: Editorial Introduction. In: Evolutionary Computation. special issue on memetic algorithms. Band 12, Nr. 3. MIT Press, 2004, S. v-vi, doi:10.1162/1063656041775009 (mit.edu [PDF]).
  19. ↑ a b c William E. Hart: Adaptive Global Optimization with Local Search. Dissertation. University of California, USA 1994, doi:10.5555/221524.
  20. ↑ 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.
  21. ↑ 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.
  22. ↑ 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.
  23. ↑ 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.
  24. ↑ 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.
  25. ↑ 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]).
  26. ↑ 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).
  27. ↑ 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 3-540-58484-6, S. 5–15, doi:10.1007/3-540-58484-6_245.
  28. ↑ 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.
  29. ↑ Mark William Shannon Land: Evolutionary Algorithms with Local Search for Combinatorial Optimization. Dissertation. University of California, 1998, doi:10.5555/928346.
  30. ↑ 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.
  31. ↑ 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.
  32. ↑ a b J.E. Smith: The Co-Evolution of Memetic Algorithms for Protein Structure Prediction. In: William E. Hart, J. E. Smith, N. Krasnogor (Hrsg.): Recent Advances in Memetic Algorithms (= Studies in Fuzziness and Soft Computing). Band 166. Springer-Verlag, Berlin, Heidelberg 2005, ISBN 3-540-22904-3, S. 105–128, doi:10.1007/3-540-32363-5.
  33. ↑ Christian Prins, Samir Bouchenoua: A Memetic Algorithm Solving the VRP, the CARP and General Routing Problems with Nodes, Edges and Arcs. In: William E. Hart, Natalio Krasnogor, James E. Smith (Hrsg.): Recent Advances in Memetic Algorithms. Studies in Fuzziness and Soft Computing, Nr. 166. Springer, Berlin, Heidelberg 2005, ISBN 3-540-22904-3, S. 65–85, doi:10.1007/3-540-32363-5.
  34. ↑ Shawki Areibi, Zhen Yang: Effective Memetic Algorithms for VLSI Design = Genetic Algorithms + Local Search + Multi-Level Clustering. In: Evolutionary Computation. Band 12, Nr. 3, September 2004, ISSN 1063-6560, S. 327–353, doi:10.1162/1063656041774947 (mit.edu [abgerufen am 20. September 2023]).
  35. ↑ David A. Pelta, Natalio Krasnogor: Multimeme Algorithms Using Fuzzy Logic Based Memes For Protein Structure Prediction. In: William E. Hart, J. E. Smith, N. Krasnogor (Hrsg.): Recent Advances in Memetic Algorithms (= Studies in Fuzziness and Soft Computing). Band 166. Springer-Verlag, Berlin/Heidelberg 2005, ISBN 3-540-22904-3, S. 49–64, doi:10.1007/3-540-32363-5.
  36. ↑ Ender Özcan: Memes, Self-generation and Nurse Rostering. In: Practice and Theory of Automated Timetabling VI. Band 3867. Springer Berlin Heidelberg, Berlin, Heidelberg 2007, ISBN 978-3-540-77344-3, S. 85–104, doi:10.1007/978-3-540-77345-0_6.
  37. ↑ E. K. Burke, A. J. Smith: A memetic algorithm to schedule planned maintenance for the national grid. In: ACM Journal of Experimental Algorithmics. Band 4, 31. Dezember 1999, ISSN 1084-6654, S. 1, doi:10.1145/347792.347801.
  38. ↑ Daniel Costa: An Evolutionary Tabu Search Algorithm And The NHL Scheduling Problem. In: INFOR: Information Systems and Operational Research. Band 33, Nr. 3, August 1995, ISSN 0315-5986, S. 161–178, doi:10.1080/03155986.1995.11732279.
  39. ↑ A. Alkan, E. Ozcan: Memetic algorithms for timetabling. Band 3. IEEE, 2003, ISBN 0-7803-7804-0, S. 1796–1802, doi:10.1109/CEC.2003.1299890 (ieee.org [abgerufen am 20. September 2023]).
  40. ↑ 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.
  41. ↑ 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.
  42. ↑ Dongsu Lee, Seungho Lee, Jong-Wook Kim, Cheol-Gyun Lee, Sang-Yong Jung: Intelligent Memetic Algorithm Using GA and Guided MADS for the Optimal Design of Interior PM Synchronous Machine. In: IEEE Transactions on Magnetics. Band 47, Nr. 5, Mai 2011, ISSN 0018-9464, S. 1230–1233, doi:10.1109/TMAG.2010.2072913 (ieee.org [abgerufen am 20. September 2023]).
  43. ↑ Shawki Areibi, Zhen Yang: Effective Memetic Algorithms for VLSI Design = Genetic Algorithms + Local Search + Multi-Level Clustering. In: Evolutionary Computation. Band 12, Nr. 3, September 2004, ISSN 1063-6560, S. 327–353, doi:10.1162/1063656041774947 (mit.edu [abgerufen am 20. September 2023]).
  44. ↑ Peter Merz, Andreas Zell: Clustering Gene Expression Profiles with Memetic Algorithms. In: Parallel Problem Solving from Nature — PPSN VII. Band 2439. Springer Berlin Heidelberg, Berlin, Heidelberg 2002, ISBN 3-540-44139-5, S. 811–820, doi:10.1007/3-540-45712-7_78.
  45. ↑ Ender Özcan, Esin Onbaşioğlu: Memetic Algorithms for Parallel Code Optimization. In: International Journal of Parallel Programming. Band 35, Nr. 1, 1. Februar 2007, ISSN 1573-7640, S. 33–61, doi:10.1007/s10766-006-0026-x.
  46. ↑ Pablo Moscato, Luke Mathieson: Memetic Algorithms for Business Analytics and Data Science: A Brief Survey. In: Business and Consumer Analytics: New Ideas. Springer International Publishing, Cham 2019, ISBN 978-3-03006222-4, S. 545–608, doi:10.1007/978-3-030-06222-4_13.
  47. ↑ Zexuan Zhu, Yew-Soon Ong, Manoranjan Dash: Wrapper–Filter Feature Selection Algorithm Using a Memetic Framework. In: IEEE Transactions on Systems, Man and Cybernetics, Part B (Cybernetics). Band 37, Nr. 1, Februar 2007, ISSN 1083-4419, S. 70–76, doi:10.1109/TSMCB.2006.883267 (ieee.org [abgerufen am 20. September 2023]).
  48. ↑ Zexuan Zhu, Yew-Soon Ong, Manoranjan Dash: Markov blanket-embedded genetic algorithm for gene selection. In: Pattern Recognition. Band 40, Nr. 11, November 2007, S. 3236–3248, doi:10.1016/j.patcog.2007.02.007 (elsevier.com [abgerufen am 20. September 2023]).
  49. ↑ 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]).
Quelle: https://de.wikipedia.org/wiki/Memetischer_Algorithmus