„Memetischer Algorithmus“ – Versionsunterschied

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Versionsgeschichte interaktiv durchsuchen
[ungesichtete Version][ungesichtete Version]
← Zum vorherigen VersionsunterschiedZum nächsten Versionsunterschied →
Inhalt gelöscht Inhalt hinzugefügt
VisuellWikitext
K leere Struktur auskommentiert
Vollständige Überarbeitung des Artikels, siehe Kommentar im Diskussionsbereich
Zeile 1: Zeile 1:
'''Memetische Algorithmen''' (MA) sind sind eine Erweiterung von global suchenden [[Populationsmodell (evolutionärer Algorithmus)|populationsbasierten]] [[Metaheuristik|Metaheuristiken]] um Verfahren zur [[Lokale Suche|lokalen Suche]], des [[Maschinelles Lernen|maschinellen Lernens]] oder anderer Verbesserungs- oder [[Optimierungsverfahren]]. Typische Vertreter erweitern einen [[Evolutionärer Algorithmus|Evolutionären Algorithmus]] (EA) als global suchendes Verfahren um ein oder mehrere [[Optimierung (Mathematik)#Nichtlineare Optimierung|lokale Suchverfahren]] oder [[Heuristik|Heuristiken]], die als Mem bezeichnet werden. Sie können problemspezifisch sein, müssen es aber nicht.<ref>{{Literatur |Titel=Memetic Computing |TitelErg=Aims and Scope of the Journal |Band=International Journal, seit März 2009 |Verlag=Springer |Ort=Berlin, Heidelberg, New York |Datum= |Online=https://www.springer.com/journal/12293/}}</ref>
'''Memetische Algorithmen''' (MA) sind sind eine Erweiterung von global suchenden [[Populationsmodell (evolutionärer Algorithmus)|populationsbasierten]] [[Metaheuristik|Metaheuristiken]] um Verfahren zur [[Lokale Suche|lokalen Suche]], des [[Maschinelles Lernen|maschinellen Lernens]] oder anderer Verbesserungs- oder [[Optimierungsverfahren]]. Typische Vertreter erweitern einen [[Evolutionärer Algorithmus|Evolutionären Algorithmus]] (EA) als global suchendes Verfahren um ein oder mehrere [[Optimierung (Mathematik)#Nichtlineare Optimierung|lokale Suchverfahren]] oder [[Heuristik|Heuristiken]], die als Mem bezeichnet werden. Sie können problemspezifisch sein, müssen es aber nicht.<ref>{{Literatur |Titel=Memetic Computing |TitelErg=Aims and Scope of the Journal |Sammelwerk= |WerkErg= |Band=International Journal, seit März 2009 |Verlag=Springer |Ort=Berlin, Heidelberg, New York |Datum= |Online=https://www.springer.com/journal/12293/}}</ref>


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.
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 ==
== Einführung ==
Die Grundidee der memetischen [[Algorithmus|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 (Mathematik)|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 [[Optimierung (Mathematik)#Begriffe: Zielfunktion, Nebenbedingungen, zulässige Menge, lokale und globale Optimierung|(Sub)Optimum]]. Das Ziel der Kombination beider Verfahrensklassen ist eine Reduktion des meist in [[Fitnessfunktion|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.<ref name=":0">{{Literatur |Autor=Wilfried Jakob |Hrsg=J.J. Merelo et al. |Titel=HyGLEAM - an Approach to Generally Applicable Hybridization of Evolutionary Algorithms |Sammelwerk=Conf. Proc. of Parallel Problem Solving from Nature (PPSN VII) |Nummer=LNCS 2439 |Verlag=Springer |Ort=Berlin, Heidelberg, New York |Datum=2002 |Seiten=527–536 |Online=https://publikationen.bibliothek.kit.edu/170049221/3814055}}</ref>
Die Grundidee der memetischen [[Algorithmus|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 (Mathematik)|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 [[Optimierung (Mathematik)#Begriffe: Zielfunktion, Nebenbedingungen, zulässige Menge, lokale und globale Optimierung|(Sub)Optimum]]. Das Ziel der Kombination beider Verfahrensklassen ist eine Reduktion des meist in [[Fitnessfunktion|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.<ref name=":0">{{Literatur |Autor=Wilfried Jakob |Titel=HyGLEAM - an Approach to Generally Applicable Hybridization of Evolutionary Algorithms |Hrsg=J.J. Merelo et al. |Sammelwerk=Conf. Proc. of Parallel Problem Solving from Nature (PPSN VII) |Band= |Nummer=LNCS 2439 |Verlag=Springer |Ort=Berlin, Heidelberg, New York |Datum=2002 |Seiten=527–536 |Online=https://publikationen.bibliothek.kit.edu/170049221/3814055}}</ref>

Memetische Algorithmen wurden bereits auf eine Vielzahl realer Problemstellungen angewandt, zum Beispiel zur zur Lösung von Routingproblemen,<ref name=":1">{{Literatur |Autor=William E. Hart, Natalio Krasnogor, James E. Smith |Titel=Recent Advances in Memetic Algorithms |Band=Studies in Fuzziness and Soft Computing |Nummer=166 |Verlag=Springer |Ort=Berlin, Heidelberg |Datum=2005 |ISBN=3-540-22904-3}}</ref> zur [[Proteinstrukturvorhersage|Vorhersage von Proteinstrukturen]],<ref name=":1" /> zur Lösung von Schedulingproblemen mit Nebenbedingungen<ref name=":2">{{Literatur |Autor=Wilfried Jakob |Titel=A general cost-benefit-based adaptation framework for multimeme algorithms |Sammelwerk=Memetic Computing |Band=2 |Nummer=3 |Datum=2010-09 |ISSN=1865-9284 |Seiten=201–218 |Online=http://link.springer.com/10.1007/s12293-010-0040-9 |Abruf=2022-01-31 |DOI=10.1007/s12293-010-0040-9}}</ref> oder von Workflows zu heterogenen Ressourcen,<ref>{{Literatur |Autor=Wilfried Jakob, Sylvia Strack, Alexander Quinte, Günther Bengel, Karl-Uwe Stucky |Titel=Fast Rescheduling of Multiple Workflows to Constrained Heterogeneous Resources Using Multi-Criteria Memetic Computing |Sammelwerk=Algorithms |Band=6 |Nummer=2 |Datum=2013-04-22 |ISSN=1999-4893 |Seiten=245–277 |Online=http://www.mdpi.com/1999-4893/6/2/245 |Abruf=2022-01-31 |DOI=10.3390/a6020245}}</ref> zur Bearbeitung von Designproblemen<ref>{{Literatur |Autor=Andrea Caponio, Ferrante Neri |Hrsg=Ferrante Neri, Carlos Cotta, Pablo Moscato |Titel=Memetic Algorithms in Engineering and Design |Sammelwerk=Handbook of Memetic Algorithms |Band=Serie Studies in Computational Intelligence |Nummer=379 |Verlag=Springer |Ort=Berlin, Heidelberg |Datum=2012 |ISBN=978-3-642-23246-6 |Online=http://link.springer.com/10.1007/978-3-642-23247-3 |Abruf=2022-01-31 |DOI=10.1007/978-3-642-23247-3}}</ref> oder für die Erstellung von Flugplänen.<ref>{{Literatur |Autor=Edmund K. Burke, Patrick De Causmaecker, Geert De Maere, Jeroen Mulder, Marc Paelinck, Greet Vanden Berghe |Titel=A multi-objective approach for robust airline scheduling |Sammelwerk=Computers & Operations Research |Band=37 |Nummer=5 |Datum=2010-05 |Seiten=822–832 |Online=https://linkinghub.elsevier.com/retrieve/pii/S0305054809000896 |Abruf=2022-01-31 |DOI=10.1016/j.cor.2009.03.026}}</ref>
Memetische Algorithmen wurden bereits auf eine Vielzahl realer Problemstellungen angewandt, zum Beispiel zur zur Lösung von Routingproblemen,<ref name=":1">{{Literatur |Autor=William E. Hart, Natalio Krasnogor, James E. Smith |Titel=Recent Advances in Memetic Algorithms |Band=Studies in Fuzziness and Soft Computing |Nummer=166 |Verlag=Springer |Ort=Berlin, Heidelberg |Datum=2005 |ISBN=3-540-22904-3 |Online= |Abruf=}}</ref> zur [[Proteinstrukturvorhersage|Vorhersage von Proteinstrukturen]],<ref name=":1" /> zur Lösung von Schedulingproblemen mit Nebenbedingungen<ref name=":2">{{Literatur |Autor=Wilfried Jakob |Titel=A general cost-benefit-based adaptation framework for multimeme algorithms |Sammelwerk=Memetic Computing |Band=2 |Nummer=3 |Datum=2010-09 |ISSN=1865-9284 |DOI=10.1007/s12293-010-0040-9 |Seiten=201–218 |Online=http://link.springer.com/10.1007/s12293-010-0040-9 |Abruf=2022-01-31}}</ref> oder von Workflows zu heterogenen Ressourcen,<ref>{{Literatur |Autor=Wilfried Jakob, Sylvia Strack, Alexander Quinte, Günther Bengel, Karl-Uwe Stucky |Titel=Fast Rescheduling of Multiple Workflows to Constrained Heterogeneous Resources Using Multi-Criteria Memetic Computing |Sammelwerk=Algorithms |Band=6 |Nummer=2 |Datum=2013-04-22 |ISSN=1999-4893 |DOI=10.3390/a6020245 |Seiten=245–277 |Online=http://www.mdpi.com/1999-4893/6/2/245 |Abruf=2022-01-31}}</ref> zur Bearbeitung von Designproblemen<ref>{{Literatur |Autor=Andrea Caponio, Ferrante Neri |Titel=Memetic Algorithms in Engineering and Design |Hrsg=Ferrante Neri, Carlos Cotta, Pablo Moscato |Sammelwerk=Handbook of Memetic Algorithms |Band=Serie Studies in Computational Intelligence |Nummer=379 |Verlag=Springer |Ort=Berlin, Heidelberg |Datum=2012 |Reihe= |ISBN=978-3-642-23246-6 |DOI=10.1007/978-3-642-23247-3 |Online=http://link.springer.com/10.1007/978-3-642-23247-3 |Abruf=2022-01-31}}</ref> oder für die Erstellung von Flugplänen.<ref>{{Literatur |Autor=Edmund K. Burke, Patrick De Causmaecker, Geert De Maere, Jeroen Mulder, Marc Paelinck, Greet Vanden Berghe |Titel=A multi-objective approach for robust airline scheduling |Sammelwerk=Computers & Operations Research |Band=37 |Nummer=5 |Datum=2010-05 |DOI=10.1016/j.cor.2009.03.026 |Seiten=822–832 |Online=https://linkinghub.elsevier.com/retrieve/pii/S0305054809000896 |Abruf=2022-01-31}}</ref>


Die [[Memetik]] ist eine Forschungsrichtung, in der [[Evolution|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''.
Die [[Memetik]] ist eine Forschungsrichtung, in der [[Evolution|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''.
Zeile 23: Zeile 24:
Beim Design eines MA sind im Wesentlichen die folgenden fünf Fragen zu klären:<ref>{{Literatur |Autor=William E. Hart, Natalio Krasnogor, Jim E. Smith |Titel=Editorial Introduction |Sammelwerk=Evolutionary Computation |WerkErg=special issue on memetic algorithms |Band=12 |Nummer=3 |Datum=2004 |Seiten=v-vi}}</ref><ref name=":3">{{Literatur |Autor=William E. Hart |Titel=Adaptive Global Optimization with Local Search |TitelErg=Dissertation |Verlag=University of California |Ort=USA |Datum=1994}}</ref><ref name=":2" />
Beim Design eines MA sind im Wesentlichen die folgenden fünf Fragen zu klären:<ref>{{Literatur |Autor=William E. Hart, Natalio Krasnogor, Jim E. Smith |Titel=Editorial Introduction |Sammelwerk=Evolutionary Computation |WerkErg=special issue on memetic algorithms |Band=12 |Nummer=3 |Datum=2004 |Seiten=v-vi}}</ref><ref name=":3">{{Literatur |Autor=William E. Hart |Titel=Adaptive Global Optimization with Local Search |TitelErg=Dissertation |Verlag=University of California |Ort=USA |Datum=1994}}</ref><ref name=":2" />


# Welches lokale Verfahren soll genutzt werden?
# Welches lokale Verfahren soll genutzt werden?
# Soll durch eine gefundene Verbesserung das [[Genom (evolutionärer Algorithmus)|Genom]] angepasst werden?
# Soll durch eine gefundene Verbesserung das [[Genom (evolutionärer Algorithmus)|Genom]] angepasst werden?
# Wie werden die Nachkommen für die lokale Verbesserung ausgewählt?
# Wie werden die Nachkommen für die lokale Verbesserung ausgewählt?
# Wie oft soll eine lokale Verbesserung versucht werden?
# Wie oft soll eine lokale Verbesserung versucht werden?
# Wie intensiv soll die lokale Suche sein?
# 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.
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 [[Breitensuche|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.
Bei Metaheuristiken wie den EA spielt das Verhältnis zwischen [[Breitensuche|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.
Zeile 37: Zeile 38:
=== Welches lokale Verfahren soll genutzt werden? ===
=== Welches lokale Verfahren soll genutzt werden? ===


Die richtige Auswahl eines für die aktuelle Anwendung geeigneten Verfahren ist wesentlich für den Erfolg.<ref name=":3">{{Literatur |Autor=William E. Hart |Titel=Adaptive Global Optimization with Local Search |TitelErg=Dissertation |Verlag=University of California |Ort=USA |Datum=1994}}</ref><ref>{{Literatur |Autor=Y.S. Ong, A.J. Keane |Titel=Meta-Lamarckian Learning in Memetic Algorithms |Sammelwerk=IEEE Transactions on Evolutionary Computation |Band=8 |Nummer=2 |Datum=2004-04 |ISSN=1089-778X |Seiten=99–110 |Online=http://ieeexplore.ieee.org/document/1288050/ |Abruf=2022-01-31 |DOI=10.1109/TEVC.2003.819944}}</ref> 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,<ref>{{Literatur |Autor=James M. Ortega, Maxine L. Rockoff |Titel=Nonlinear Difference Equations and Gauss-Seidel Type Iterative Methods |Sammelwerk=SIAM Journal on Numerical Analysis |Band=3 |Nummer=3 |Datum=1966-09 |ISSN=0036-1429 |Seiten=497–513 |Online=http://epubs.siam.org/doi/10.1137/0703043 |Abruf=2022-01-31 |DOI=10.1137/0703043}}</ref> den Complex-Algorithmus<ref>{{Literatur |Autor=M. J. Box |Titel=A New Method of Constrained Optimization and a Comparison With Other Methods |Sammelwerk=The Computer Journal |Band=8 |Nummer=1 |Datum=1965-04-01 |ISSN=0010-4620 |Seiten=42–52 |Online=https://academic.oup.com/comjnl/article-lookup/doi/10.1093/comjnl/8.1.42 |Abruf=2022-01-31 |DOI=10.1093/comjnl/8.1.42}}</ref> oder das Rosenbrock-Verfahren,<ref>{{Literatur |Autor=H. H. Rosenbrock |Titel=An Automatic Method for Finding the Greatest or Least Value of a Function |Sammelwerk=The Computer Journal |Band=3 |Nummer=3 |Datum=1960-03-01 |ISSN=0010-4620 |Seiten=175–184 |Online=https://academic.oup.com/comjnl/article-lookup/doi/10.1093/comjnl/3.3.175 |Abruf=2022-01-31 |DOI=10.1093/comjnl/3.3.175}}</ref> so wird die generelle Anwendbarkeit des EAs lediglich auf die den lokalen Verfahren zugänglichen Probleme der kontinuierlichen oder gemischt-ganzzahligen Optimierung beschränkt.<ref name=":0" /> Bei einer diskreten oder gemischt-ganzzahligen Optimierung werden die Werte an der Schnittstelle zwischen EA und Mem bei Bedarf gerundet.
Die richtige Auswahl eines für die aktuelle Anwendung geeigneten Verfahren ist wesentlich für den Erfolg.<ref name=":3">{{Literatur |Autor=William E. Hart |Titel=Adaptive Global Optimization with Local Search |TitelErg=Dissertation |Verlag=University of California |Ort=USA |Datum=1994}}</ref><ref name=":4">{{Literatur |Autor=Y.S. Ong, A.J. Keane |Titel=Meta-Lamarckian Learning in Memetic Algorithms |Sammelwerk=IEEE Transactions on Evolutionary Computation |Band=8 |Nummer=2 |Datum=2004-04 |ISSN=1089-778X |DOI=10.1109/TEVC.2003.819944 |Seiten=99–110 |Online=http://ieeexplore.ieee.org/document/1288050/ |Abruf=2022-01-31}}</ref> 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]],<ref name=":5">{{Literatur |Autor=James M. Ortega, Maxine L. Rockoff |Titel=Nonlinear Difference Equations and Gauss-Seidel Type Iterative Methods |Sammelwerk=SIAM Journal on Numerical Analysis |Band=3 |Nummer=3 |Datum=1966-09 |ISSN=0036-1429 |DOI=10.1137/0703043 |Seiten=497–513 |Online=http://epubs.siam.org/doi/10.1137/0703043 |Abruf=2022-01-31}}</ref> den Complex-Algorithmus<ref name=":6">{{Literatur |Autor=M. J. Box |Titel=A New Method of Constrained Optimization and a Comparison With Other Methods |Sammelwerk=The Computer Journal |Band=8 |Nummer=1 |Datum=1965-04-01 |ISSN=0010-4620 |DOI=10.1093/comjnl/8.1.42 |Seiten=42–52 |Online=https://academic.oup.com/comjnl/article-lookup/doi/10.1093/comjnl/8.1.42 |Abruf=2022-01-31}}</ref> oder das [[Rosenbrock-Verfahren]],<ref name=":7">{{Literatur |Autor=H. H. Rosenbrock |Titel=An Automatic Method for Finding the Greatest or Least Value of a Function |Sammelwerk=The Computer Journal |Band=3 |Nummer=3 |Datum=1960-03-01 |ISSN=0010-4620 |DOI=10.1093/comjnl/3.3.175 |Seiten=175–184 |Online=https://academic.oup.com/comjnl/article-lookup/doi/10.1093/comjnl/3.3.175 |Abruf=2022-01-31}}</ref> so wird die generelle Anwendbarkeit des EAs lediglich auf die den lokalen Verfahren zugänglichen Probleme der kontinuierlichen oder gemischt-ganzzahligen Optimierung beschränkt.<ref name=":0" /> 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.
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? ===
=== Soll durch eine gefundene Verbesserung das Genom angepasst werden? ===
Entweder wirkt eine gefundene Verbesserung nur durch die bessere Fitness ([[Baldwin-Effekt|Baldwin-Evolution]]) oder es wird auch das Genom entsprechend angepasst ([[Lamarckismus|Lamarcksche Evolution]]). Diese Frage wurde bereits in den 90-iger Jahren kontrovers in der Literatur diskutiert, wobei festgestellt wurde, dass der konkrete Anwendungsfall eine wesentliche Rolle spielt.<ref>{{Literatur |Autor=Frédéric Gruau, Darrell Whitley |Titel=Adding Learning to the Cellular Development of Neural Networks: Evolution and the Baldwin Effect |Sammelwerk=Evolutionary Computation |Band=1 |Nummer=3 |Datum=1993-09 |ISSN=1063-6560 |DOI=10.1162/evco.1993.1.3.213 |Seiten=213–233 |Online=https://direct.mit.edu/evco/article/1/3/213-233/1109 |Abruf=2022-01-31}}</ref><ref>{{Literatur |Autor=David Orvosh, Lawrence Davis |Titel=Shall We Repair? Genetic Algorithms, Combinatorial Optimization, and Feasibility Constraints |Hrsg=S. Forrest |Sammelwerk=Conf. Proc. of Int. Conf. on Genetic Algorithms (ICGA) |Verlag=Morgan Kaufmann |Ort=San Mateo, CA, USA |Datum=1993 |Seiten=650 |Online=https://www.semanticscholar.org/paper/Shall-We-Repair-Genetic-AlgorithmsCombinatorial-Orvosh-Davis/c1a930dea91a59ccec2cf20f7f81a953bd53f46a}}</ref><ref>{{Literatur |Autor=Darrell Whitley, Vahl Scott Gordon, Keith E. Mathias |Titel=Lamarckian Evolution, the Baldwin Effect and Function Optimization |Sammelwerk=Parallel Problem Solving from Nature (PPSN III) |Band=LNCS |Nummer=866 |Verlag=Springer |Ort=Berlin, Heidelberg |Datum=1994 |ISBN=978-3-540-58484-1 |DOI=10.1007/3-540-58484-6_245 |Seiten=5–15 |Online=http://link.springer.com/10.1007/3-540-58484-6_245 |Abruf=2022-01-31}}</ref> Der Hintergrund der Debatte besteht darin, dass eine Anpassung des Genoms eine [[Populationsmodell (evolutionärer Algorithmus)|vorzeitige Konvergenz]] fördern kann. Dieses Risiko kann durch andere Maßnahmen zur besseren Ausgewogenheit zwischen Breiten- und Tiefensuche, wie der Verwendung [[Populationsmodell (evolutionärer Algorithmus)|strukturierter Populationen]], wirksam verringert werden.<ref name=":2" />


⚫
=== Wie werden die Nachkommen für die lokale Verbesserung ausgewählt? ===
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 90-iger Jahren kontrovers in der Literatur diskutiert, wobei festgestellt wurde, dass der konkrete Anwendungsfall eine wesentliche Rolle spielt. [Gruau][Orvosh][Whitley] 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. [Jakob-10]
⚫
Die Auswahl kann zufällig oder fitnessbasiert erfolgen. Dabei kann die gesamte Nachkommenschaft einer Generation zur Grundlage der Auswahl gemacht werden<ref name=":4" /> oder jeweils nur die Nachkommen einer Paarung.<ref name=":2" /> Bei Mems mit geringem Rechenaufwand kann es auch sinnvoll sein, es auf alle Nachkommen anzuwenden.<ref>{{Literatur |Autor=K.W.C. Ku, Man Wai Mak, Wan-Chi Siu |Titel=A study of the Lamarckian evolution of recurrent neural networks |Sammelwerk=IEEE Transactions on Evolutionary Computation |Band=4 |Nummer=1 |Datum=2000-04 |DOI=10.1109/4235.843493 |Seiten=31–42 |Online=http://ieeexplore.ieee.org/document/843493/ |Abruf=2022-01-31}}</ref>


=== Wie werden die Nachkommen für die lokale Verbesserung ausgewählt? ===
=== 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? ===
⚫
Die Auswahl kann zufällig oder fitnessbasiert erfolgen. Dabei kann die gesamte Nachkommenschaft einer Generation zur Grundlage der Auswahl gemacht werden [Ong-Keane] oder jeweils nur die Nachkommen einer Paarung [Jakob-10]. Bei Mems mit geringem Rechenaufwand kann es auch sinnvoll sein, es auf alle Nachkommen anzuwenden. [Ku]
⚫
Heuristiken und lokale Suchverfahren arbeiten in der Regel iterativ und brechen beim Absinken der Verbesserungen unter ein vorgegebenes Limit ab.<ref name=":5" /><ref name=":6" /><ref name=":7" /> Ü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<ref name=":3" /> und von Land für den Bereich der [[Kombinatorische Optimierung|kombinatorischen Optimierun]]<nowiki/>g untersucht.<ref>{{Literatur |Autor=Mark William Shannon Land |Titel=Evolutionary Algorithms with Local Search for Combinatorial Optimization |TitelErg=Dissertation |Sammelwerk= |Verlag=University of California |Datum=1998 |Online=https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.55.8986&rep=rep1&type=pdf}}</ref>
⚫
=== Wie oft soll eine lokale Verbesserung versucht werden? ===


⚫
== Multimem Algorithmen ==
⚫
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.


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.<ref>{{Literatur |Autor=James E. Smith |Titel=Self-Adaptation in Evolutionary Algorithms for Combinatorial Optimisation |Sammelwerk=Adaptive and Multilevel Metaheuristics |Band=136 |Verlag=Springer |Ort=Berlin, Heidelberg |Datum=2008 |ISBN=978-3-540-79437-0 |DOI=10.1007/978-3-540-79438-7_2 |Seiten=31–57 |Online=http://link.springer.com/10.1007/978-3-540-79438-7_2 |Abruf=2022-01-31}}</ref> 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.<ref name=":4" /> Ä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.<ref name=":2" /> Ein Überblick über selbst-adaptive und koevolutionäre Multimem Algorithmen kann im Handbook of Memetic Algorithms<ref>{{Literatur |Autor=James E. Smith |Titel=Self-adaptative and Coevolving Memetic Algorithms |Hrsg=Ferrante Neri, Carlos Cotta, Pablo Moscato |Sammelwerk=Handbook of Memetic Algorithms |Band=SCI |Nummer=379 |Verlag=Springer |Ort=Berlin, Heidelberg |Datum=2012 |Reihe= |ISBN=978-3-642-23246-6 |DOI=10.1007/978-3-642-23247-3 |Online=http://link.springer.com/10.1007/978-3-642-23247-3 |Abruf=2022-01-31}}</ref> gefunden werden.
⚫
=== Wie intensiv soll die lokale Suche sein? ===

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 [[Evolutionärer Algorithmus#Evolutionsstrategien (ES)|Evolutionsstrategie]] mit ihren derart eingestellten [[Mutation (evolutionärer Algorithmus)#Mutation reeller Zahlen|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 oder 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.
⚫
Heuristiken und lokale Suchverfahren arbeiten in der Regel iterativ und brechen beim Absinken der Verbesserungen unter ein vorgegebenes Limit ab. [Ortega][Rosenbrock][Complex] Ü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 [Hart] und von Land für den Bereich der kombinatorischen Optimierung untersucht. [Land]


⚫
<!-- == Multimem Algorithmen == -->
== Literatur ==
== Literatur ==
* ''Memetic Computing'', International Journal, Springer, seit März 2009, [https://www.springer.com/journal/12293/ Journal Homepage]
* ''Memetic Computing'', International Journal, Springer, seit März 2009, [https://www.springer.com/journal/12293/ Journal Homepage]
* Ferrante Neri, Carlos Cotta, Pablo Moscato: ''Handbook of Memetic Algorithms''. SCI 379, Springer, Berlin, Heidelberg, 2012. ISBN 978-3-642-23247-3 doi: [https://www.doi.org/10.1007/978-3-642-23247-3 10.1007/978-3-642-23247-3]
* Ferrante Neri, Carlos Cotta, Pablo Moscato: ''Handbook of Memetic Algorithms''. SCI 379, Springer, Berlin, Heidelberg, 2012. ISBN 978-3-642-23247-3 doi: [https://www.doi.org/10.1007/978-3-642-23247-3 10.1007/978-3-642-23247-3]
* Enrique Alba, Bernabé Dorronsoro, Hugo Alfonso: ''Cellular Memetic Algorithms''. Journal of Computer Science and Technology, 5(4), 2005, S.257-263. [https://core.ac.uk/download/pdf/301030757.pdf PDF]
* Enrique Alba, Bernabé Dorronsoro, Hugo Alfonso: ''Cellular Memetic Algorithms''. Journal of Computer Science and Technology, 5(4), 2005, S.257-263. [https://core.ac.uk/download/pdf/301030757.pdf PDF]
* P. Moscato, ''On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms'', Caltech Concurrent Computation Program, C3P Report 826, (1989).
* P. Moscato, ''On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms'', Caltech Concurrent Computation Program, C3P Report 826, (1989).

Version vom 31. Januar 2022, 16:33 Uhr

Memetische Algorithmen (MA) sind 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 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 Verfahren 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 90-iger 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 oder 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

  • Memetic Computing, International Journal, Springer, seit März 2009, Journal Homepage
  • 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
  • Enrique Alba, Bernabé Dorronsoro, Hugo Alfonso: Cellular Memetic Algorithms. Journal of Computer Science and Technology, 5(4), 2005, S.257-263. PDF
  • P. Moscato, On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms, Caltech Concurrent Computation Program, C3P Report 826, (1989).

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 (springer.com [abgerufen am 31. Januar 2022]).
  5. ↑ Wilfried Jakob, Sylvia Strack, Alexander Quinte, Günther Bengel, Karl-Uwe Stucky: 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 (mdpi.com [abgerufen am 31. Januar 2022]).
  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 (springer.com [abgerufen am 31. Januar 2022]).
  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 (ieee.org [abgerufen am 31. Januar 2022]).
  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 (ieee.org [abgerufen am 31. Januar 2022]).
  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 (siam.org [abgerufen am 31. Januar 2022]).
  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 (oup.com [abgerufen am 31. Januar 2022]).
  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 (oup.com [abgerufen am 31. Januar 2022]).
  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 (springer.com [abgerufen am 31. Januar 2022]).
  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 (ieee.org [abgerufen am 31. Januar 2022]).
  21. ↑ Mark William Shannon Land: Evolutionary Algorithms with Local Search for Combinatorial Optimization. Dissertation. University of California, 1998 (psu.edu [PDF]).
  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 (springer.com [abgerufen am 31. Januar 2022]).
  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 (springer.com [abgerufen am 31. Januar 2022]).
Abgerufen von „https://de.wikipedia.org/w/index.php?title=Memetischer_Algorithmus&oldid=219735306“