Ziel der vorliegenden Arbeit ist die Entwicklung eines kooperativen Optimierungsverfahrens, d.h. mehrere Low-Level Heuristiken werden von einer High-Level Heuristik so gesteuert, dass sie ein Problem gemeinsam lösen. Gemeinsam lösen heißt hier, sie lösen sich ab, d.h. eine Low-Level Heuristik fängt dort an, wo die andere aufgehört hat.
Warum ist eine kooperative Lösung aber sinnvoll? Die Nachbarschaftsstruktur einer komplexen Zielfunktion kann in verschiedenen Regionen der Zielfunktion sehr unterschiedlich sein. In unterschiedlichen Regionen eignen sich lokal eventuell jeweils andere Low-Level Heuristiken als anderswo, d.h. es gibt eventuell keine Erkundungs-Heuristik, die sich überall gleich gut eignet. Ein anderer Vorteil ist: Man hebt den Grad der Allgemeinheit des Suchverfahrens durch kooperative Suche, während ein Verfahren trotzdem (idealerweise) konkurrenzfähig zu Einzelverfahren bleibt. Allgemeinheit kann besonders für nicht-Experten von Vorteil sein, oder wenn wenig Wissen über die Problemstruktur vorhanden ist. In der Literatur spricht man häufig von “Hyperstrategien”, da Hyperstrategien auf einer noch höheren Abstraktionsebene arbeiten als die “Metaheuristiken”. Hyperstrategien operieren nicht auf Zielfunktionen, sondern sie verwalten Metaheuristiken.
In der vorliegenden Arbeit erfolgt zunächst eine allgemeine Einführung über Optimierung und die eingesetzten Low-Level Heuristiken. Es folgt eine Literatur-Befragung über die generelle Struktur von Hyper-Heuristiken. Im Kern der Arbeit werden drei vom Autor selbst entwickelte kooperative Verfahren vorgestellt. Die zwei zuletzt entwickelten Verfahren werden im Rahmen der Evaluation statistisch verglichen.
Inhaltsverzeichnis
1 Abstract
2 Grundlagen der Optimierung
2.1 Einteilung von Optimierungsverfahren
2.2 Auswahl der Verfahren
3 Die eingesetzten Verfahren
3.1 Die evolutionären Algorithmen
3.2 Die Evolutionsstrategie
3.3 Differential Evolution
3.4 Gradientenabstieg
3.5 Modifiziertes Hillclimbing
4 Die generelle Struktur von Hyper-Heuristiken zur Optimierung
4.1 Das allgemeine Rahmenwerk
4.2 Lernen mit Verstärkung mit Tabu-Liste
5 Die entwickelten Verfahren
5.1 3 phasiger Ansatz zur Optimierung
5.1.1 Vorüberlegungen
5.1.2 Motivation des kooperativen Verfahrens
5.1.3 Algorithmus
5.2 Ansatz mit dynamischer Verfahrensselektion
5.2.1 Vorüberlegungen
5.2.2 Motivation
5.2.3 Algorithmus
5.2.4 Modifikationen
5.3 Hyper-Strategie mit Verstärkungslernen und Tabu-Liste
5.3.1 Vorüberlegungen
5.3.2 Algorithmus
5.3.3 Modifikationen
6 Evaluation
6.1 Eierpappenfunktion
6.1.1 Populationsverlauf
6.1.2 Optimierungsfortschritt
6.1.3 Gefundene Funktionswerte
6.1.4 Funktionsaufrufe
6.1.5 Summierte Funktionsaufrufe
6.1.6 Spinnennetz Funktionsaufrufe
6.2 Rosenbrockfunktion
6.2.1 Populationsverlauf
6.2.2 Optimierungsfortschritt
6.2.3 Gefundene Funktionswerte
6.2.4 Funktionsaufrufe
6.2.5 Summierte Funktionsaufrufe
6.2.6 Spinnennetz Funktionsaufrufe
7 Zusammenfassung
Zielsetzung & Themen
Die vorliegende Master-Thesis befasst sich mit der Entwicklung und Evaluierung kooperativer Optimierungsverfahren, bei denen verschiedene Low-Level-Heuristiken durch eine übergeordnete High-Level-Heuristik gesteuert werden, um komplexe Optimierungsprobleme effizienter zu lösen. Die zentrale Forschungsfrage untersucht, wie sich die Zusammenarbeit und dynamische Selektion von Optimierungsalgorithmen auf die Effizienz und Qualität der gefundenen Lösungen auswirkt.
- Grundlagen von Optimierungsverfahren und deren Einteilung
- Struktur und Funktionsweise von Hyper-Heuristiken
- Entwicklung kooperativer Strategien und dynamischer Verfahrensselektion
- Einsatz von Reinforcement Learning und Tabu-Listen zur Algorithmensteuerung
- Vergleichende Evaluation anhand von Benchmark-Funktionen wie der Eierpappen- und Rosenbrockfunktion
Auszug aus dem Buch
3.1 Die evolutionären Algorithmen
Evolutionäre Algorithmen arbeiten nach dem Vorbild der Natur, indem sie das natürliche Optimierungspotential der Evolution nutzen. Die Evolution hat ausgehend von sehr einfachen Lebewesen immer komplexere, immer besser an ihren Lebensraum angepasste Lebewesen hervorgebracht. Die Lebensformen wurden in einem gewissen Sinne optimiert durch die Evolution. Dabei entstehen bei der Vermehrung der Lebewesen durch Rekombination und Mutation des Erbgutes neue Varianten, von denen aber nur die am besten angepassten überleben, die sich dann weiter vermehren (Selektion). Das Prinzip ist auch bekannt als „Survival of the fittest“, die Zielfunktion heißt daher hier auch Fitnessfunktion. Bei den evolutionären Algorithmen geht man davon aus, dass ein bestimmtes Erscheinungsbild (Phänotyp) durch ein bestimmtes Chromosom (Genotyp) kodiert ist. Konkret ist das Chromosom die Kodierung einer möglichen Lösung eines Optimierungsproblems, die in den Chromosomen abgespeichert ist. Beispielsweise kann eine bestimmte Ampelschaltung, die optimiert werden soll, kodiert sein. Es existieren verschiedene Arten von Kodierungen, die dem Problem angepasst werden müssen, meist erfolgt die Kodierung binär. Im Falle der Parameteroptimierung hat es sich als günstig erwiesen, die Folge von reellen Parametern einfach als Tupel von reellen Zahlen zu kodieren. Ein Tupel von reellen Zahlen ist in gewisser Weise natürlich, weil sich die genetischen Operatoren größtenteils als arithmetische Operationen darstellen lassen. Die bekanntesten zwei hier existierenden Verfahren sind die Evolutionsstrategie und die Differential Evolution. Beide verwenden unterschiedliche Formen der sogenannten genetischen Operatoren, deren Aufgabe hier dargestellt ist.
Selektion: Vielversprechende Lösungen werden zur weiteren Verarbeitung ausgewählt, um aus ihnen evtl. noch bessere Lösungen zu erzeugen.
Rekombination: Zwei vielversprechende Lösungen werden kombiniert, in der Hoffnung, dass sich aus ihnen eine noch bessere Lösung erzeugen lässt.
Mutation: Zur Wahrung der Variation in der Population und zur Verhinderung der vorzeitigen Konvergenz, hat es sich als sinnvoll erwiesen, zufällige Veränderungen der Population zu erzeugen.
Zusammenfassung der Kapitel
1 Abstract: Zusammenfassung der Zielsetzung, kooperative Low-Level-Heuristiken durch High-Level-Heuristiken zu steuern.
2 Grundlagen der Optimierung: Einordnung von Optimierungsaufgaben und Erläuterung der mathematischen Modellierung.
3 Die eingesetzten Verfahren: Detaillierte Beschreibung der verwendeten Optimierungsalgorithmen wie Evolutionsstrategie, Differential Evolution und Gradientenabstieg.
4 Die generelle Struktur von Hyper-Heuristiken zur Optimierung: Vorstellung allgemeiner Rahmenwerke für Hyper-Heuristiken und die Implementierung von Auswahlstrategien.
5 Die entwickelten Verfahren: Präsentation der selbst entwickelten Ansätze für kooperative Optimierung, von der statischen Abfolge bis zur dynamischen Verfahrensselektion.
6 Evaluation: Statistische Gegenüberstellung der entwickelten Verfahren anhand komplexer Benchmark-Funktionen.
7 Zusammenfassung: Resümee über die erreichten Ergebnisse und Ausblick auf künftige Forschungsansätze.
Schlüsselwörter
Optimierung, Hyper-Heuristik, Evolutionsstrategie, Differential Evolution, Gradientenabstieg, Kooperative Optimierung, Verfahrensselektion, Reinforcement Learning, Tabu-Suche, Benchmark-Funktionen, Eierpappenfunktion, Rosenbrockfunktion, Fitnessfunktion, Populationsmanagement, Fitnessoptimierung
Häufig gestellte Fragen
Worum geht es in dieser wissenschaftlichen Arbeit grundsätzlich?
Die Arbeit beschäftigt sich mit dem Bereich der Hyper-Heuristiken, also übergeordneten Strategien zur Steuerung mehrerer, verschiedener Optimierungsverfahren (Low-Level-Heuristiken), um komplexe mathematische Probleme effizienter zu lösen.
Welche zentralen Themenfelder deckt die Studie ab?
Die Arbeit behandelt die mathematischen Grundlagen der Optimierung, die Funktionsweise genetischer Algorithmen, die Struktur von Hyper-Heuristiken sowie die praktische Entwicklung und Evaluation kooperativer Optimierungsstrategien.
Was ist das primäre Ziel der Untersuchung?
Ziel ist die Entwicklung und statistische Evaluierung von kooperativen Verfahren, die durch dynamische Selektion von Algorithmen eine robustere und effizientere Optimierung als Einzelverfahren erreichen sollen.
Welche wissenschaftlichen Methoden werden verwendet?
Es werden verschiedene stochastische (z.B. Evolutionsstrategie, Differential Evolution) und deterministische (z.B. Gradientenabstieg) Optimierungsmethoden kombiniert und durch Reinforcement Learning sowie Tabu-Listen gesteuert.
Was bildet den Schwerpunkt im Hauptteil der Arbeit?
Der Hauptteil gliedert sich in die theoretische Herleitung der Hyper-Heuristik-Strukturen und die detaillierte Vorstellung der selbst entwickelten Algorithmenansätze zur kooperativen Verfahrensselektion.
Welche Schlüsselbegriffe charakterisieren die Arbeit?
Zentrale Begriffe sind Hyper-Heuristik, kooperative Optimierung, Evolutionsstrategie, Differential Evolution sowie der Vergleich anhand der Eierpappen- und Rosenbrockfunktion.
Warum wird die „Eierpappenfunktion“ als Benchmark-Test verwendet?
Diese Funktion dient als Testumgebung, da sie eine spezielle Topologie mit vielen lokalen Optima aufweist, was die Fähigkeit der Verfahren zur globalen Suche und zur Überwindung lokaler Optima testet.
Was unterscheidet den „3 phasigen Ansatz“ vom „Ansatz mit dynamischer Verfahrensselektion“?
Der 3-phasige Ansatz folgt einer festen Abfolge von Algorithmen, während der Ansatz mit dynamischer Verfahrensselektion zur Laufzeit evaluiert, welcher Algorithmus gerade den größten Fortschritt erzielt, und diesen bevorzugt.
Welche Rolle spielt die Tabu-Liste bei den entwickelten Verfahren?
Die Tabu-Liste verhindert, dass bereits schlecht performende Verfahren zu schnell erneut ausgewählt werden, und trägt somit zu einer effizienteren Steuerung der Verfahrens-Auswahl bei.
Welches Fazit zieht der Autor in Bezug auf die Differential Evolution?
Der Autor stellt fest, dass Differential Evolution trotz ihrer Leistungsfähigkeit bei bestimmten Problemen sehr rechenintensiv ist und in den entwickelten kooperativen Systemen durch die Kombination mit schnelleren lokalen Verfahren ergänzt werden muss.
- Arbeit zitieren
- Thomas Plehn (Autor:in), 2010, Entwicklung und Evaluation von kooperativen Optimierungsverfahren, München, GRIN Verlag, https://www.hausarbeiten.de/document/146127
