Memetischer Algorithmus

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

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.

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, Graphpartitionierung, minimale Graphenfärbung, Travelling-Salesman-Problem, mehrdimensionaler Knapsack, quadratisches Zuordnungsproblem und Bin Packing.

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, 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: $t=0$;
                    Erzeuge eine zufällige Startpopulation $P(t)$;
                    Berechne die Fitness $f(p)\ \ \forall p\in P(t)$;  // initiale Bewertung
   while Abbruchkriterien sind nicht erfüllt do
       Partnerwahl: Wähle entsprechend $f(p)$ eine Teilmenge von $P(t)$ und speichere sie in $M(t)$;
       Nachkommen:  Rekombiniere und mutiere Individuen $p\in M(t)$ und speichere sie in $M'(t)$;
       Lernphase:    Verbessere $p'$ durch lokale Suche oder eine Heuristik $\forall p'\in M'(t)$;
       Bewertung:   Berechne die Fitness $f(p')\ \ \forall p'\in M'(t)$;
       if Lamarcksche Evolution then
          Update: Passe das Chromosom von $p'$ gemäß der jeweiligen Verbesserung $\forall p'\in M'(t)$ an;
       fi
       Neue Generation: Erzeuge $P(t+1)$ durch Auswahl von Individuen aus $P(t)$ und $M'(t)$;
       $t=t+1$;
   end while
   Ergebnis: Liefere bestes Individuum $p\in P(t-1)$ 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

→ Hauptartikel: No-free-Lunch-Theoreme

Die No-free-Lunch-Theoreme der Optimierung und der Suche 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 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:

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. 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, den Complex-Algorithmus oder das Rosenbrock-Verfahren, so wird die generelle Anwendbarkeit des EAs lediglich auf die den lokalen Verfahren zugänglichen Probleme der kontinuierlichen oder gemischt-ganzzahligen Optimierung beschränkt. 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. 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.

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

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. Ü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 und von Land für den Bereich der kombinatorischen Optimierung untersucht.

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. 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. Ä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. Ein Überblick über selbst-adaptive und koevolutionäre Multimem Algorithmen kann im Handbook of Memetic Algorithms gefunden werden.

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

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

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, VLSI-Design, Vorhersage von Proteinstrukturen, Scheduling mit Nebenbedingungen, automatische Zeitplanung, Scheduling von Workflows zu heterogenen Ressourcen, Bearbeitung von Designproblemen, Clustering von Genexpressionsprofilen, Optimierung der Ausführung paralleler Programme, Business Analytics, Merkmalsauswahl und -identifikation oder Erstellung von Flugplänen.

Literatur

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