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
- 3.1 Funktionen einer Veränderlichen
- 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
- 4.1 Genetik
- 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
- 5.1 Evolutionsstrategien und Genetische Algorithmen
- 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
- 7.1 Erweiterung bei der Evolutionsstrategie
- 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 und Themenschwerpunkte
Diese Diplomarbeit befasst sich mit der Untersuchung und Erweiterung globaler Optimierungsverfahren für nichtglatte Funktionen, insbesondere nichtstetige Funktionen. Ziel ist es, bestehend Verfahren zu vergleichen und Verbesserungen zu entwickeln, die eine effizientere globale Suche ermöglichen.
- Vergleich verschiedener globaler Optimierungsverfahren
- Entwicklung und Implementierung von Erweiterungen bestehender Algorithmen
- Analyse der Konvergenzgeschwindigkeit der Verfahren
- Untersuchung des Einflusses von Parametern auf die Leistungsfähigkeit
- Anwendung der Verfahren auf verschiedene Testfunktionen
Zusammenfassung der Kapitel
1 Einleitung: Diese Einleitung führt in die Thematik der globalen Optimierung nichtglatter Funktionen ein und beschreibt die Motivation für die vorliegende Arbeit. Die ungelösten Fragen aus einer vorherigen Arbeit zum Thema selbstlernende Bewegungsabläufe von vierbeinigen Robotern werden als Ausgangspunkt für die hier durchgeführten Untersuchungen genannt. Die Arbeit gliedert sich in die einzelnen Kapitel, welche die verwendeten Methoden und deren Ergebnisse detailliert beschreiben.
2 Die Anwendung OptimizeTest: Dieses Kapitel präsentiert die speziell für diese Diplomarbeit entwickelte Testumgebung OptimizeTest. Es wird sowohl die Bedienung der Software beschrieben als auch die Implementierung in Java und JavaScript erläutert. Die Verwendung von XML-Dateien zur Datenverwaltung und die Integration der 2D-Zeichenfläche aus dem Projekt Math4u2 werden hervorgehoben.
3 Testfunktionen für Optimierungsverfahren: Hier werden die verschiedenen Testfunktionen vorgestellt, die zur Evaluierung der Optimierungsverfahren verwendet wurden. Die Funktionen werden nach Anzahl der Variablen (eine oder mehrere) und nach ihren Eigenschaften (differenzierbar, stetig, unstetig) kategorisiert. Für jede Funktion werden die Charakteristika, der Definitionsbereich und die Lage des globalen Optimums beschrieben. Besondere Schwerpunkte liegen auf den Schwierigkeiten, die diese Funktionen für verschiedene Optimierungsalgorithmen darstellen.
4 Evolution: Dieses Kapitel bietet eine Einführung in die biologischen Grundlagen der Evolution. Es werden die Konzepte der Genetik, Vererbung und Artentrennung erläutert, um die Prinzipien der evolutionären Algorithmen besser zu verstehen. Die verschiedenen Evolutionsfaktoren wie genetische Drift, natürliche Selektion und Mutation werden detailliert beschrieben. Schließlich wird die Evolution als Optimierungsprozess interpretiert, der die Grundlage für die in dieser Arbeit verwendeten evolutionären Algorithmen bildet.
5 Evolutionäre Algorithmen: Dieses Kapitel beschreibt evolutionäre Algorithmen im Allgemeinen und Evolutionsstrategien im Besonderen. Es wird die prinzipielle Struktur, die Repräsentation der Individuen, die Initialisierung, Bewertung, Fitness, Selektion, Rekombination, Mutation, das Wiedereinfügen und die Abbruchkriterien erläutert. Verschiedene Varianten dieser Prozesse werden vorgestellt und diskutiert.
6 Weitere Optimierungsverfahren: Dieses Kapitel stellt weitere Optimierungsverfahren vor, darunter Partikelschwarm-Optimierung, zyklisches Abstiegsverfahren, STEP, DIRECT, Simulated Annealing, Nelder-Mead-Verfahren und Rosenbrock-Methode. Für jedes Verfahren werden die grundlegenden Prinzipien und der Algorithmus erläutert.
7 Erweiterung der Algorithmen: In diesem Kapitel werden Erweiterungen für die Evolutionsstrategie und den DIRECT-Algorithmus vorgestellt und diskutiert. Für die Evolutionsstrategie werden neue Rekombinationsmethoden (Parallelogramm- und elliptische Rekombination), eine Fitnessberechnung mit verminderter Überbevölkerung und eine Mutation mit Partitionen eingeführt. Für den DIRECT-Algorithmus wird eine Erweiterung mit dem Nelder-Mead-Verfahren und eine Beschränkung der Partitionsanzahl vorgeschlagen.
8 Vergleich der Optimierungsverfahren: Das letzte Kapitel, welches in dieser Zusammenfassung nicht enthalten ist, da es die Ergebnisse der Arbeit darstellt und somit Spoiler enthalten könnte, vergleicht die verschiedenen Verfahren anhand ausgewählter Testfunktionen und ermittelt die optimalen Parameterkonfigurationen.
Schlüsselwörter
Globale Optimierung, nichtglatte Funktionen, nichtstetige Funktionen, Evolutionsstrategien, Genetische Algorithmen, Partikelschwarmoptimierung, STEP, DIRECT, Simulated Annealing, Nelder-Mead-Verfahren, Rosenbrock-Methode, Konvergenzgeschwindigkeit, Testfunktionen, Optimierungsparameter, Populationsdynamik, biologische Evolution.
Häufig gestellte Fragen (FAQ) zur Diplomarbeit: Globale Optimierungsverfahren für nichtglatte Funktionen
Was ist das Thema der Diplomarbeit?
Die Diplomarbeit untersucht und erweitert globale Optimierungsverfahren für nichtglatte, insbesondere nichtstetige Funktionen. Ziel ist der Vergleich bestehender Verfahren und die Entwicklung von Verbesserungen für eine effizientere globale Suche.
Welche Optimierungsverfahren werden untersucht?
Die Arbeit betrachtet verschiedene globale Optimierungsverfahren, darunter Evolutionsstrategien, Genetische Algorithmen, Partikelschwarmoptimierung, STEP, DIRECT, Simulated Annealing, Nelder-Mead-Verfahren und die Rosenbrock-Methode. Zusätzlich werden Erweiterungen für die Evolutionsstrategie und den DIRECT-Algorithmus entwickelt und implementiert.
Welche Erweiterungen der Algorithmen wurden entwickelt?
Für die Evolutionsstrategie wurden neue Rekombinationsmethoden (Parallelogramm- und elliptische Rekombination), eine Fitnessberechnung mit verminderter Überbevölkerung und eine Mutation mit Partitionen eingeführt. Für den DIRECT-Algorithmus wurde eine Erweiterung mit dem Nelder-Mead-Verfahren und eine Beschränkung der Partitionsanzahl vorgeschlagen.
Wie werden die Optimierungsverfahren verglichen?
Der Vergleich der Verfahren erfolgt anhand ausgewählter Testfunktionen mit unterschiedlichen Eigenschaften (Anzahl der Variablen, Differenzierbarkeit, Stetigkeit). Die optimalen Parameterkonfigurationen für jedes Verfahren werden ermittelt und die Konvergenzgeschwindigkeit analysiert.
Welche Testfunktionen wurden verwendet?
Die Arbeit verwendet eine Reihe von Testfunktionen, die nach Anzahl der Variablen (eine oder mehrere) und ihren Eigenschaften (differenzierbar, stetig, unstetig) kategorisiert sind. Die Auswahl der Testfunktionen zielt darauf ab, die Stärken und Schwächen der verschiedenen Optimierungsverfahren aufzuzeigen.
Welche Software wurde verwendet?
Die Diplomarbeit nutzt die speziell entwickelte Testumgebung OptimizeTest, implementiert in Java und JavaScript. Die Datenverwaltung erfolgt über XML-Dateien, und die 2D-Zeichenfläche aus dem Projekt Math4u2 ist integriert.
Welche biologischen Grundlagen werden behandelt?
Die Arbeit enthält eine Einführung in die biologischen Grundlagen der Evolution, einschließlich Genetik, Vererbung, Artentrennung und Evolutionsfaktoren. Dies dient dem Verständnis der Prinzipien evolutionärer Algorithmen, da die Evolution als Optimierungsprozess interpretiert wird.
Welche Schlüsselwörter beschreiben die Arbeit?
Globale Optimierung, nichtglatte Funktionen, nichtstetige Funktionen, Evolutionsstrategien, Genetische Algorithmen, Partikelschwarmoptimierung, STEP, DIRECT, Simulated Annealing, Nelder-Mead-Verfahren, Rosenbrock-Methode, Konvergenzgeschwindigkeit, Testfunktionen, Optimierungsparameter, Populationsdynamik, biologische Evolution.
Gibt es eine Zusammenfassung der einzelnen Kapitel?
Ja, die Arbeit bietet eine detaillierte Zusammenfassung jedes Kapitels, beginnend mit der Einleitung und der Motivation, über die Beschreibung der verwendeten Methoden und Algorithmen bis hin zu den Ergebnissen (ausgenommen das Kapitel mit den Ergebnissen, um Spoiler zu vermeiden).
Wo finde ich die Ergebnisse des Vergleichs der Optimierungsverfahren?
Die Ergebnisse des Vergleichs der Optimierungsverfahren sind im letzten Kapitel der Diplomarbeit enthalten. Die Zusammenfassung enthält diese Ergebnisse nicht, um Spoiler zu vermeiden.
- Quote paper
- Stefan Fenn (Author), 2008, Vergleich und Erweiterung von globalen Optimierungsverfahren auf nichtglatten Funktionen, Munich, GRIN Verlag, https://www.grin.com/document/412495
