In dieser Diplomarbeit werden globale Optimierungsverfahren untersucht, die auf nichtglatten und insbesondere nichtstetigen Funktionen operieren können.
In Kapitel 2 wird die speziell für die Diplomarbeit entwickelte Testumgebung OptimizeTest vorgestellt, mit der eine Vielzahl von Optimierungsverfahren getestet werden können. In Kapitel 3 werden die Testfunktionen behandelt, die in OptimizeTest enthalten sind. Die Testfunktionen werden zum Vergleichen und Analysieren der Optimierungsverfahren benutzt. Um zu erkennen, welche Prinzipien der biologischen Evolution bei den Evolutionären Algorithmen übernommen werden, wird in Kapitel 4 eine Einführung in die biologische Evolution gegeben. Die Evolutionären Algorithmen insbesondere Evolutionsstrategien sind in Kapitel 4 detailliert beschrieben. Es wurden aber auch andere Optimierungsverfahren gesucht, die in Kapitel 6 beschrieben sind. Im Rahmen meiner Analyse habe ich Modifikationen an den Optimierungsverfahren vorgenommen und diese sind in Kaptiel 7 zu finden. Einige Modifikationen beantworten die oben gestellten Fragen. Zuletzt werden in Kapitel 8 die Optimierungsverfahren miteinander verglichen.
Inhaltsverzeichnis
1 Einleitung
2 Die Anwendung OptimizeTest
2.1 Bedienung
2.2 Implementierung
3 Testfunktionen für Optimierungsverfahren
3.1 Funktionen einer Veränderlichen
3.1.1 Differenzierbare Funktionen
3.1.2 Stetige Funktionen
3.1.3 Unstetige Funktionen
3.2 Funktionen mehrer Veränderlichen
3.2.1 Differenzierbare Funktionen
3.2.2 Stetige Funktionen
3.2.3 Unstetige Funktionen
3.2.4 Minigolf-Problem (Abb. 3.28 und 3.29)
4 Evolution
4.1 Genetik
4.1.1 Von der DNA zur RNA
4.1.2 Proteine
4.1.3 Befruchtung
4.1.4 Genetische Variabilität
4.2 Vererbung
4.3 Artentrennung
4.3.1 Präzygotische Fortpflanzungsbarrieren
4.3.2 Postzygotische Fortpflanzungsbarrieren
4.4 Evolutionsfaktoren
4.4.1 Variablität innerhalb der Population
4.4.2 Inzucht
4.5 Evolution als Optimierungsprozess
5 Evolutionäre Algorithmen
5.1 Evolutionsstrategien und Genetische Algorithmen
5.1.1 Prinzipielle Struktur
5.1.2 Repräsentation der Individuen
5.1.3 Initialisierung
5.1.4 Bewertung
5.1.5 Fitness
5.1.6 Selektion
5.1.7 Rekombination
5.1.8 Mutation
5.1.9 Wiedereinfügen
5.1.10 Abbruchkriterien
5.2 Mutation-Selektion-Verfahren
6 Weitere Optimierungsverfahren
6.1 Partikelschwarm-Optimierung
6.2 Zyklisches Abstiegsverfahren
6.3 STEP
6.3.1 Schwierigkeit einer Partition
6.3.2 Der STEP-Algorithmus
6.4 DIRECT
6.4.1 Initialisierung
6.4.2 Unterteilung eines Hyper-Rechtecks
6.4.3 Auswahl der zu unterteilenden Hyper-Rechtecke
6.5 Simulated Annealing
6.6 Nelder-Mead-Verfahren
6.6.1 Konstruktionsprinzipien
6.6.2 Ablauf des Nelder-Mead-Verfahrens
6.7 Rosenbrock-Methode
6.7.1 Verbessertes Orthogonalisierungsverfahren
7 Erweiterung der Algorithmen
7.1 Erweiterung bei der Evolutionsstrategie
7.1.1 Parallelogramm-Rekombination
7.1.2 Elliptische Rekombination
7.1.3 Fitnessberechnung mit verminderter Überbevölkerung
7.1.4 Rekombination aus der Nachbarschaft
7.1.5 Mutation mit Partitionen
7.2 Erweiterung von DIRECT
7.2.1 DIRECT mit Nelder-Mead
7.2.2 DIRECT mit Beschränkung der Partitionsanzahl
8 Vergleich der Optimierungsverfahren
8.1 Auswahl der Testfunktionen
8.2 Auswahl der Parameter
8.3 Vergleich der lokalen Optimierungsverfahren
8.4 Vergleich der globalen Optimierungsverfahren
Zielsetzung & Themen
Die Arbeit untersucht und vergleicht globale Optimierungsverfahren, die speziell für den Einsatz auf nichtglatten und nichtstetigen Funktionen entwickelt wurden, um deren Effektivität zu bewerten und durch Modifikationen zu verbessern.
- Entwicklung und Implementierung der Testumgebung OptimizeTest
- Analyse diverser Testfunktionen zur Evaluierung von Optimierern
- Untersuchung biologischer Evolutionsprinzipien für Algorithmen
- Vergleich klassischer und evolutionärer Optimierungsstrategien
- Optimierung und Erweiterung von Algorithmen zur effizienteren globalen Suche
Auszug aus dem Buch
Minigolf-Problem (Abb. 3.28 und 3.29)
Innerhalb eines überschneidungsfreien Polygons P ⊂ R2 gibt es einen Startpunkt xstart an dem ein Ball positioniert ist und einen Zielpunkt xziel. Gesucht ist ein optimialer Abschlag, der den Ball möglichst nahe an den Zielpunkt bringt und dabei einen möglichst kurzen Weg zurücklegt. Die zu optimierenden Parameter sind der Abschlagwinkel ω ∈ [0, 360] im Gradmaß bezüglich der x-Achse sowie die Abschlagstärke s ∈ [0.1, 20]. Falls der Ball mit dem Rand des Polygons kollidiert, ändert sich die Richtung des Balles so, dass der Einfallwinkel gleich dem Ausfallwinkel ist. Dadurch verläuft die Bahn des Balles stets im inneren von P. Die Reibung mit der Wand wird in dieser Simulation nicht beachtet. Die Abschlagsstärke wird mit der zurückgelegten Strecke des Balles identifiziert. Ein Ball mit s = 8 legt also 8 Einheiten auf P zurück und die Simulation stoppt anschließend.
Abbildung 3.28 zeigt ein examplarisches Minigolf-Problem mit der Trajektorie eines optimalen Schlages. Bei diesen Beispiel sind die Koordinaten der Eckpunkte von P: (0, 0)T , (1, 0)T , (1, 3)T , (2, 3)T , (6, 0)T , (9, 0)T , (9, 2)T , (6, 2)T , (3, 4)T und (0, 4). Weiter ist xstart = (0.5, 0.2)T , xziel = (8, 1)T und der optimale Schlag bei diesen Parametern wird mit ω∗ ≈ 304.321◦, s∗ ≈ 12.592 erreicht.
Zusammenfassung der Kapitel
1 Einleitung: Diese Einleitung stellt die Motivation dar, Optimierungsverfahren für nichtglatte Funktionen zu untersuchen, und gibt einen Überblick über die in der Arbeit vorgestellte Testumgebung und die behandelten Algorithmen.
2 Die Anwendung OptimizeTest: Dieses Kapitel erläutert die Funktionsweise und Implementierung der Testumgebung, die für den Vergleich der Optimierungsverfahren in dieser Arbeit verwendet wurde.
3 Testfunktionen für Optimierungsverfahren: Es werden verschiedene Testfunktionen eingeführt, um die Qualität und Konvergenzgeschwindigkeit globaler Optimierungsverfahren systematisch zu bestimmen.
4 Evolution: Das Kapitel liefert eine Einführung in biologische Evolutionsmechanismen, die als Vorbild für evolutionäre Algorithmen dienen.
5 Evolutionäre Algorithmen: Hier werden heuristische Suchverfahren wie Evolutionsstrategien detailliert beschrieben und ihre Prinzipien für die Optimierung erläutert.
6 Weitere Optimierungsverfahren: Dieses Kapitel behandelt diverse weitere Algorithmen wie Partikelschwarm-Optimierung, DIRECT, Simulated Annealing und klassische lokale Verfahren.
7 Erweiterung der Algorithmen: Der Autor präsentiert spezifische Modifikationen und Erweiterungen der zuvor vorgestellten Algorithmen zur Verbesserung der globalen Suchleistung.
8 Vergleich der Optimierungsverfahren: Die Arbeit schließt mit einem systematischen Leistungsvergleich der untersuchten Optimierungsverfahren anhand der ausgewählten Testfunktionen und Parameter.
Schlüsselwörter
Globale Optimierung, Nichtglatte Funktionen, Evolutionsstrategien, Genetische Algorithmen, Partikelschwarm-Optimierung, DIRECT-Algorithmus, Simulated Annealing, Nelder-Mead-Verfahren, Rosenbrock-Methode, Konvergenz, Testfunktionen, Populationsdynamik, Fitnessfunktion, Selektionsdruck, Funktionsauswertung
Häufig gestellte Fragen
Worum geht es in dieser Arbeit?
Die Diplomarbeit untersucht und vergleicht verschiedene globale Optimierungsverfahren, insbesondere für den Einsatz bei nichtglatten und nichtstetigen Zielfunktionen.
Welche zentralen Themenfelder werden abgedeckt?
Zentrale Themen sind die biologische Evolution als Vorbild für Optimierung, die Implementierung einer Testumgebung namens OptimizeTest sowie der detaillierte Vergleich von Evolutionsstrategien, Schwarmintelligenz und deterministischen Verfahren.
Was ist das primäre Ziel der Forschung?
Das Ziel ist es, die Leistungsfähigkeit verschiedener Algorithmen zu analysieren und Modifikationen zu entwickeln, welche die globale Suche in schwierigen Suchräumen verbessern.
Welche wissenschaftlichen Methoden kommen zum Einsatz?
Es wird eine experimentelle Methodik verwendet, bei der diverse mathematische Testfunktionen herangezogen werden, um Algorithmen unter definierten Bedingungen hinsichtlich Konvergenz und Robustheit zu messen.
Was wird im Hauptteil behandelt?
Der Hauptteil gliedert sich in die Vorstellung der Testumgebung, die theoretische Einführung in biologische Konzepte, die Beschreibung der Optimierungsalgorithmen sowie die detaillierte Präsentation erarbeiteter Erweiterungen und Modifikationen.
Welche Schlüsselwörter charakterisieren die Arbeit?
Zu den wichtigsten Begriffen gehören Globale Optimierung, Evolutionäre Algorithmen, Nichtstetigkeit, Fitness, Selektion und die verschiedenen Verfahren wie DIRECT oder Partikelschwarm-Optimierung.
Was macht das Minigolf-Problem so besonders?
Es dient als praxisnahes, hochgradig nichtstetiges Testbeispiel, da bei kleinen Parameteränderungen das Verhalten der Simulation aufgrund kollisionsbedingter Richtungsänderungen unstetig wechselt.
Warum wird eine Modifikation von DIRECT vorgeschlagen?
Um die Konvergenzgeschwindigkeit zu erhöhen und den Speicherbedarf zu begrenzen, da der ursprüngliche DIRECT-Algorithmus bei vielen Partitionen sehr rechen- und speicherintensiv wird.
- Citation du texte
- Stefan Fenn (Auteur), 2008, Vergleich und Erweiterung von globalen Optimierungsverfahren auf nichtglatten Funktionen, Munich, GRIN Verlag, https://www.grin.com/document/412495
