Vergleich und Erweiterung von globalen Optimierungsverfahren auf nichtglatten Funktionen

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

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.