Das Räuber-Beute-Modell für die mehrkriterielle Optimierung - Analyse und Anwendung
Loading...
Date
2012-10-12
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Das Streben nach Verbesserung von Systemen ist schon immer eine allgegenwärtige
Herausforderung in Wissenschaft und technischer Anwendung. In der Regel ist
jeder Ingenieur nicht nur mit dem Problem konfrontiert, ein einziges Ziel möglichst
gut zu erfüllen; für die Entwicklung realer Systeme sind oftmals mehrere sich widersprechende
Ziele (oder Kriterien) zugleich zu erfüllen. So ergibt sich für die mehrkriterielle
Optimierung die Aufgabe, eine Menge sogenannter optimaler Kompromisse
aufzufinden, die alle Kriterien zugleich möglichst gut erfüllen. In den letzten
30 Jahren haben evolutionäre Algorithmen als gute Heuristiken für diesen Bereich
an Bedeutung gewonnen. Dort sind Standardverfahren entwickelt worden, die gute
Approximationen der Kompromissmenge liefern, jedoch oftmals monolithisch
aufgebaut sind und eine für die Anwenderschaft hohe Komplexität aufweisen.
In dieser Arbeit betrachten wir eine einfache und ebenfalls naturinspirierte
Alternative zu den etablierten Verfahren: das Räuber-Beute-Modell für die mehrkriterielle
Optimierung. Anders als die Standardansätze basiert es auf lokal agierenden
einkriteriellen algorithmischen Komponenten und ist sehr modular. Dies
erleichtert neben der Parallelisierung des Ansatzes auch die
exible und anwendungsbezogene Konfiguration. Zugleich ist es jedoch ein Verfahren, dessen Dynamik
noch weitgehend unverstanden ist, so dass eine Abschätzung über das Potential
des Ansatzes (über die zuvor genannte Flexibilität und Einfachheit in der
Anwendung hinaus) bisher aussteht. Die erste Aufgabe in dieser Arbeit ist es
daher, die inneren Prozesse des Räuber-Beute-Modells zu beobachten und theoretisch
zu beschreiben. Erst mit diesem Wissen stellen wir exemplarisch zwei Erweiterungsmöglichkeiten des Verfahrens vor und zeigen deren Nutzen. Schließlich übertragen wir das Modell in die Anwendung für den Bereich des mehrkriteriellen
Schedulings und stellen dar, dass es nicht nur etablierten Verfahren überlegen ist,
sondern durch seinen modularen Aufbau auch als Framework zur Integration von
heuristischem Expertenwissen gewinnbringend angewendet werden kann.
The quest for improvement of systems is and has been an ubiquitous challenge for science as well as for technical application. Every engineer is confronted not only with the task of fulfilling a single optimality criterion but with the requirement to satisfy many often contradicting criteria as good as possible. He then strives for a set of so-called optimal compromises. Over the last 30 years, evolutionary algorithms have emerged as well-suited heuristics to solve this task. Nowadays, this area provides a set of standard approaches which usually yield good approximation results. However for engineers without detailed insight into an algorithm's structure, most of the monolithic approaches are complex to apply. In this work, we thus focus on a simple and also nature-inspired alternative approach: the Predator Prey Model for multi-objective optimization. Unlike the established algorithms, this approach comprises local acting single-objective components, which make it rather modular. That property enables parallelization and an application-specific configuration. Surprisingly, the dynamics of the approach are not well understood, such that a conclusion regarding its application potential is still open. Therefore, a first task of this work is the observation of internal processes and their theoretical description. With that background at hand, we propose and evaluate two exemplary extensions of the model and show their benefit for approximation quality. Finally, we transfer the model to the area of multi-objective scheduling and show its superiority to established models. In this context we demonstrate,how the modular character of the Predator-Prey Model can be used to establish a framework for the integration of heuristic expert knowledge.
The quest for improvement of systems is and has been an ubiquitous challenge for science as well as for technical application. Every engineer is confronted not only with the task of fulfilling a single optimality criterion but with the requirement to satisfy many often contradicting criteria as good as possible. He then strives for a set of so-called optimal compromises. Over the last 30 years, evolutionary algorithms have emerged as well-suited heuristics to solve this task. Nowadays, this area provides a set of standard approaches which usually yield good approximation results. However for engineers without detailed insight into an algorithm's structure, most of the monolithic approaches are complex to apply. In this work, we thus focus on a simple and also nature-inspired alternative approach: the Predator Prey Model for multi-objective optimization. Unlike the established algorithms, this approach comprises local acting single-objective components, which make it rather modular. That property enables parallelization and an application-specific configuration. Surprisingly, the dynamics of the approach are not well understood, such that a conclusion regarding its application potential is still open. Therefore, a first task of this work is the observation of internal processes and their theoretical description. With that background at hand, we propose and evaluate two exemplary extensions of the model and show their benefit for approximation quality. Finally, we transfer the model to the area of multi-objective scheduling and show its superiority to established models. In this context we demonstrate,how the modular character of the Predator-Prey Model can be used to establish a framework for the integration of heuristic expert knowledge.
Description
Table of contents
Keywords
Evolutionäre Algorithmen, Heuristik, Mehrkriterielles Scheduling, Mehrzieloptimierung, Räuber-Beute-Modell