Entwicklung und Evaluation von kooperativen Optimierungsverfahren

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

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.