Entwicklung und Evaluation von kooperativen Optimierungsverfahren

Ziel der vorliegenden Arbeit ist die Entwicklung eines kooperativen Optimierungsverfahrens, d.h. mehrere Low-Level Heuristiken werden von einer High-Level Heuristik so gesteuert, dass sie ein Problem gemeinsam lösen. Gemeinsam lösen heißt hier, sie lösen sich ab, d.h. eine Low-Level Heuristik fängt dort an, wo die andere aufgehört hat.

Warum ist eine kooperative Lösung aber sinnvoll? Die Nachbarschaftsstruktur einer komplexen Zielfunktion kann in verschiedenen Regionen der Zielfunktion sehr unterschiedlich sein. In unterschiedlichen Regionen eignen sich lokal eventuell jeweils andere Low-Level Heuristiken als anderswo, d.h. es gibt eventuell keine Erkundungs-Heuristik, die sich überall gleich gut eignet. Ein anderer Vorteil ist: Man hebt den Grad der Allgemeinheit des Suchverfahrens durch kooperative Suche, während ein Verfahren trotzdem (idealerweise) konkurrenzfähig zu Einzelverfahren bleibt. Allgemeinheit kann besonders für nicht-Experten von Vorteil sein, oder wenn wenig Wissen über die Problemstruktur vorhanden ist. In der Literatur spricht man häufig von “Hyperstrategien”, da Hyperstrategien auf einer noch höheren Abstraktionsebene arbeiten als die “Metaheuristiken”. Hyperstrategien operieren nicht auf Zielfunktionen, sondern sie verwalten Metaheuristiken.

In der vorliegenden Arbeit erfolgt zunächst eine allgemeine Einführung über Optimierung und die eingesetzten Low-Level Heuristiken. Es folgt eine Literatur-Befragung über die generelle Struktur von Hyper-Heuristiken. Im Kern der Arbeit werden drei vom Autor selbst entwickelte kooperative Verfahren vorgestellt. Die zwei zuletzt entwickelten Verfahren werden im Rahmen der Evaluation statistisch verglichen.

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

Zielsetzung und Themenschwerpunkte

Diese Arbeit zielt darauf ab, ein kooperatives Optimierungsverfahren zu entwickeln, bei dem mehrere Low-Level-Heuristiken von einer High-Level-Heuristik so gesteuert werden, dass sie ein Problem gemeinsam lösen. Die Low-Level-Heuristiken arbeiten dabei abwechselnd an dem Problem, indem sie dort weitermachen, wo die vorherige Heuristik aufgehört hat.

• Die Vorteile von kooperativen Optimierungsverfahren
• Die generelle Struktur von Hyper-Heuristiken
• Entwicklung und Evaluation von drei kooperativen Verfahren
• Statistischer Vergleich der zwei zuletzt entwickelten Verfahren
• Zusammenfassende Analyse der Ergebnisse

Zusammenfassung der Kapitel

Das erste Kapitel führt in das Thema Optimierung ein und erläutert die verschiedenen Kategorien von Optimierungsaufgaben. Es werden die Grundlagen der Parameteroptimierung, die in dieser Arbeit im Mittelpunkt steht, beschrieben. Die Wahl der Zielfunktion und die Bedeutung der mathematischen Modellierung werden ebenfalls beleuchtet. Das zweite Kapitel gibt einen Überblick über die in der Arbeit verwendeten Low-Level-Heuristiken, wie beispielsweise evolutionäre Algorithmen, Evolutionsstrategie, Differential Evolution, Gradientenabstieg und modifiziertes Hillclimbing.

Kapitel 4 behandelt die generelle Struktur von Hyper-Heuristiken, die eine höhere Abstraktionsebene als Metaheuristiken einnehmen. Es wird das allgemeine Rahmenwerk von Hyper-Heuristiken vorgestellt und die Anwendung von Verstärkungslernen mit Tabu-Liste erläutert. In Kapitel 5 werden die vom Autor entwickelten kooperativen Verfahren vorgestellt, darunter ein 3-phasiger Ansatz zur Optimierung, ein Ansatz mit dynamischer Verfahrensselektion und eine Hyper-Strategie mit Verstärkungslernen und Tabu-Liste. Die Evaluation der Verfahren in Kapitel 6 umfasst verschiedene Testfunktionen, wie die Eierpappenfunktion und die Rosenbrockfunktion, und untersucht die Performance der Verfahren anhand verschiedener Kennzahlen, wie Populationsverlauf, Optimierungsfortschritt und Funktionsaufrufe.

Schlüsselwörter

Die Arbeit beschäftigt sich mit der Entwicklung und Evaluation von kooperativen Optimierungsverfahren. Dabei werden verschiedene Low-Level-Heuristiken, wie evolutionäre Algorithmen, Evolutionsstrategie und Differential Evolution, in einem Hyper-Heuristik-Rahmenwerk kombiniert. Die Arbeit untersucht die Vorteile von Hyperstrategien und die Verwendung von Verstärkungslernen mit Tabu-Liste. Die Evaluation der entwickelten Verfahren erfolgt mit Hilfe verschiedener Testfunktionen und Kennzahlen.

Details

• Hochschule: Fachhochschule Bielefeld (FB Ingenieurwissenschaften und Mathematik)
• Note: 1,0
• Autor: Thomas Plehn (Autor:in)
• Erscheinungsjahr: 2010
• Seiten: 51
• Katalognummer: V146127
• ISBN (eBook): 9783640569656
• ISBN (Buch): 9783640570492
• Sprache: Deutsch
• Schlagworte: Entwicklung Evaluation Optimierungsverfahren