Das Räuber-Beute-Modell für die mehrkriterielle Optimierung - Analyse und Anwendung
Creators: name: Grimme, Christian
Publisher: name: Technische Universität Dortmund
Year: 2012
Subjects: subject: Evolutionäre Algorithmen
subject: Heuristik
subject: Mehrkriterielles Scheduling
subject: Mehrzieloptimierung
subject: Räuber-Beute-Modell
subject: 004

description: 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.
description: 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.