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
• 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 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.