„Memetischer Algorithmus“ – Versionsunterschied

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Versionsgeschichte interaktiv durchsuchen
[gesichtete Version][ungesichtete Version]
← Zum vorherigen VersionsunterschiedZum nächsten Versionsunterschied →
Inhalt gelöscht Inhalt hinzugefügt
VisuellWikitext
Link lokale Suche + Kategorie OR (constraint optimization)
Keine Bearbeitungszusammenfassung
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 |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>
'''Memetische Algorithmen''' sind ein populationsbasierter Ansatz für die [[Heuristik|heuristische]] Suche bei Optimierungsproblemen. Für einige Problemstellungen haben sie sich als effizienter erwiesen als reine [[Evolutionärer Algorithmus|genetische Algorithmen]]. Einige Forscher betrachten sie als '''hybride genetische Algorithmen''' oder '''parallele genetische Algorithmen'''.
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 ==
Geht man von '''genetischen Algorithmen''' aus und ergänzt sie um [[Lokale Suche|lokale Suchfunktionen]], nennt man dies einen memetischen Algorithmus.
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 Erstellung eines universitären Stundenplans, zur [[Proteinstrukturvorhersage|Vorhersage von Proteinstrukturen]] oder zur Berechnung von Flugbahnen.
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''.


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

== Theoretische Grundlage ==
{{Hauptartikel|No-free-Lunch-Theoreme}}

Die No-free-Lunch-Theoreme der Optimierung<ref>{{Literatur |Autor=D.H. Wolpert, W.G. Macready |Titel=No free lunch theorems for optimization |Sammelwerk=IEEE Transactions on Evolutionary Computation |Band=1 |Nummer=1 |Datum=1997-04 |DOI=10.1109/4235.585893 |Seiten=67–82 |Online=http://ieeexplore.ieee.org/document/585893/ |Abruf=2022-01-31}}</ref> und der Suche<ref>{{Literatur |Autor=David Hilton Wolpert, William G. Macready |Titel=No free lunch theorems for search |Sammelwerk=Technical Report |Band=SFI-TR-95-02-010 |Verlag=Santa Fe Institute |Ort=Sante Fe, NM, USA |Datum=1995 |Online=http://axon.cs.byu.edu/~martinez/classes/678/Papers/Wolpert_NFLsearch.pdf}}</ref> 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<ref>{{Literatur |Autor=Lawrence Davis |Titel=Handbook of genetic algorithms |Verlag=Van Nostrand Reinhold |Ort=New York |Datum=1991 |ISBN=978-0442001735 |Online= |Abruf=}}</ref> 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:<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?
# 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 oft soll eine lokale Verbesserung versucht werden?
# 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 [[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.

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

=== 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. [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]

=== 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 [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]

=== 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. [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 ==
* ''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]
* 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).

* ''Recent Advances in Memetic Algorithms'', Series: Studies in Fuzziness and Soft Computing, Vol. 166, Hart, William E.; Krasnogor, N.; Smith, J.E. (Eds.), 2005
== Einzelnachweise ==
<references />


[[Kategorie:Evolutionärer Algorithmus]]
[[Kategorie:Evolutionärer Algorithmus]]

Version vom 31. Januar 2022, 13:20 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. [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]

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 [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]

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

  • 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 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 William E. Hart: Adaptive Global Optimization with Local Search. Dissertation. University of California, USA 1994.
  13. ↑ 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. ↑ 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. ↑ 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. ↑ 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]).
Abgerufen von „https://de.wikipedia.org/w/index.php?title=Memetischer_Algorithmus&oldid=219729892“