Entwicklung und Evaluation von kooperativen Optimierungsverfahren

Page 3

23 Funktionswerte gefundener Optima des kooperativen Verfahrens bei der Rosenbrockfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 24 Funktionswerte gefundener Optima der Hyperstrategie bei der Rosenbrockfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 25 Funktionswerte gefundener Optima der Diernetial Evolution bei der Rosenbrockfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 26 Funktionsaufrufe des kooperativen Verfahrens bei der Rosenbrockfunktion . 45 27 Funktionsaufrufe der Hyperstrategie bei der Rosenbrockfunktion . . . . . . 45 28 Summierte Funktionsaufrufe des kooperativen Verfahrens bei der Rosenbrockfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 29 Summierte Funktionsaufrufe der Hyperstrategie bei der Rosenbrockfunktion 46 30 Summierte Funktionsaufrufe der Dierential Evolution bei der Rosenbrockfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 31 Funktionsaufrufe und Lösungsgüte des kooperativen Verfahrens bei der Rosenbrockfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 32 Funktionsaufrufe und Lösungsgüte der Hyperstrategie bei der Rosenbrockfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

Tabellenverzeichnis

1 Wahlmöglichkeiten für Auswahlfunktion und Akzeptanzfunktion (vgl. Korkmaz et al., 2008) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

Algorithmenverzeichnis

1 Lernen mit Verstärkung (vgl. Burke und Subeiga, 2003) . . . . . . . . . . 15 2 Lernen mit Verstärkung mit Tabu-Liste (vgl. Yagiura et al., 2005, S. 136) 15 3 3-pasiger Algorithmus zur Optimierung . . . . . . . . . . . . . . . . . . . . 19 4 Subroutine für 3-pasigen Algorithmus zur Optimierung . . . . . . . . . . . 20 5 Algorithmus mit dynamischer Verfahrensselktion (Teil 1) . . . . . . . . . . 23 6 Algorithmus mit dynamischer Vefahrensselktion (Teil 2) . . . . . . . . . . . 24 7 angepasste Hyperstrategie (Teil 1) . . . . . . . . . . . . . . . . . . . . . . . 26 8 angepasste Hyperstrategie (Teil 2) . . . . . . . . . . . . . . . . . . . . . . . 26

1 Abstract

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.

Page 4

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äug 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.

2 Grundlagen der Optimierung

Optimierungsaufgaben können in drei Kategorien eingeteilt werden, Parameteroptimierung, Reihenfolgeoptimierung und Auswahloptimierung. Die vorliegende Arbeit beschäftigt sich mit Parameteroptimierung. Parameteroptimierung bezeichnet die Suche nach möglichst optimalen Entwurfsparametern für ein Produkt, einen Prozess oder ein System. Bei der Suche wird davon ausgegangen, das die sogenannten Designvariablen beim Entwurf veränderbar sind, wie beispielsweise Querschnitte und andere geometrische Gröÿen. Ein so entstandener Entwurf hat dann eine gewisse Güte, die durch eine Gütefunktion bzw. Zielfunktion bestimmt werden kann. Bei der Festlegung der Zielfunktion müssen oft mehrere teilweise konkurierende Kriterien gewichtet werden, die optimiert werden sollen, beispielsweise Biegesteigkeit, Spannungsverteilung unter Belastung, etc. Dies alles durch einen einfachen Wert zu messen ist oft nicht einfach und efrordert einiges an mathematischer Modellierung, denn die Wahl der Zielfunktion beeinusst nachher maÿgeblich, was im Laufe der Optimierung unter den konkurrierenden Lösungen als optimaler angesehen wird. Bei der mathematischen Modellierung einer Aufgabe der Parameteroptimierung lässt sich das Vorgehen wie folgt beschreiben:

Zunächst müssen die Suchvariablen für den Optimierungsprozess bestimmt werden. Die Suchvariablen sind hier die einstellbaren Gröÿen des Systems, für welche der Optimierungsprozess den optimalen Wert nden soll. Die Suchvariablen werden hier bezeichnet mit x i ; x (u)