Scalarized Preferences in Multi-objective Optimization

Multikriterielle Optimierungsprobleme verfügen über keine Lösung, die optimal in jeder Zielfunktion ist. Die Schwierigkeit solcher Probleme liegt darin eine Kompromisslösung zu finden, die den Präferenzen des Entscheiders genügen, der den Kompromiss implementiert. Skalarisierung – die Abbildung des Vektors der Zielfunktionswerte auf eine reelle Zahl – identifiziert eine einzige Lösung als globales Präferenzenoptimum um diese Probleme zu lösen. Allerdings generieren Skalarisierungsmethoden keine zusätzlichen Informationen über andere Kompromisslösungen, die die Präferenzen des Entscheiders bezüglich des globalen Optimums verändern könnten. ... mehrUm dieses Problem anzugehen stellt diese Dissertation eine theoretische und algorithmische Analyse skalarisierter Präferenzen bereit. Die theoretische Analyse besteht aus der Entwicklung eines Ordnungsrahmens, der Präferenzen als Problemtransformationen charakterisiert, die präferierte Untermengen der Paretofront definieren. Skalarisierung wird als Transformation der Zielmenge in diesem Ordnungsrahmen dargestellt. Des Weiteren werden Axiome vorgeschlagen, die wünschenswerte Eigenschaften von Skalarisierungsfunktionen darstellen. Es wird gezeigt unter welchen Bedingungen existierende Skalarisierungsfunktionen diese Axiome erfüllen. Die algorithmische Analyse kennzeichnet Präferenzen anhand des Resultats, das ein Optimierungsalgorithmus generiert. Zwei neue Paradigmen werden innerhalb dieser Analyse identifiziert. Für beide Paradigmen werden Algorithmen entworfen, die skalarisierte Präferenzeninformationen verwenden: Präferenzen-verzerrte Paretofrontapproximationen verteilen Punkte über die gesamte Paretofront, fokussieren aber mehr Punkte in Regionen mit besseren Skalarisierungswerten; multimodale Präferenzenoptima sind Punkte, die lokale Skalarisierungsoptima im Zielraum darstellen. Ein Drei-Stufen-Algorith\-mus wird entwickelt, der lokale Skalarisierungsoptima approximiert und verschiedene Methoden werden für die unterschiedlichen Stufen evaluiert. Zwei Realweltprobleme werden vorgestellt, die die Nützlichkeit der beiden Algorithmen illustrieren. Das erste Problem besteht darin Fahrpläne für ein Blockheizkraftwerk zu finden, die die erzeugte Elektrizität und Wärme maximieren und den Kraftstoffverbrauch minimiert. Präferenzen-verzerrte Approximationen generieren mehr Energie-effiziente Lösungen, unter denen der Entscheider seine favorisierte Lösung auswählen kann, indem er die Konflikte zwischen den drei Zielen abwägt. Das zweite Problem beschäftigt sich mit der Erstellung von Fahrplänen für Geräte in einem Wohngebäude, so dass Energiekosten, Kohlenstoffdioxidemissionen und thermisches Unbehagen minimiert werden. Es wird gezeigt, dass lokale Skalarisierungsoptima Fahrpläne darstellen, die eine gute Balance zwischen den drei Zielen bieten. Die Analyse und die Experimente, die in dieser Arbeit vorgestellt werden, ermöglichen es Entscheidern bessere Entscheidungen zu treffen indem Methoden angewendet werden, die mehr Optionen generieren, die mit den Präferenzen der Entscheider übereinstimmen.

Multi-objective optimization problems are characterized by possessing no single solution that attains the best feasible value in each objective. The intricacy of these problems lies in finding a compromise solution such that the preferences of the decision maker, who implements the compromise, are satisfied. Scalarization – mapping the vector of objectives to a real value – identifies a single solution as global preference optimum to solve this predicament, however, scalarization generates no information about other compromise solutions that might change the decision maker's preferences towards the global optimum. ... mehrTo address this issue, this thesis provides a theoretical and algorithmic analysis of scalarized preferences. The theoretical analysis consists of the development of a framework that characterizes preferences as problem transformations that identify preferred subsets of the Pareto front. Scalarization is placed within this framework as a codomain transformation. Furthermore, axioms are proposed that represent desirable properties scalarization functions may exhibit. It is shown under which conditions existing scalarization functions fulfill these axioms. The algorithmic analysis characterizes preferences by the result an optimization algorithm generates. Two new paradigms are identified within the analysis for which algorithms that use scalarized preference information are designed: Preferences-biased Pareto front approximations distribute points across the entire Pareto front but focus more points in regions with better scalarization values; A theoretical foundation for such distributions and a proof of their existence is given. multimodal preference optima are points that are local scalarization optima in the objective space. A three step algorithm is developed to approximate local scalarization optima and different methods are evaluated for each step. Two real-world optimization problems are presented to illustrate the usefulness of the two algorithms. The first problem consists of finding operating schedules for a combined heat and power plant that maximize electricity and heat output while minimizing fuel consumption. Preference-biased approximations generate more energy efficient solutions among which the decision maker can choose her personal preference weighing the tradeoffs between the three objectives. The second problem is concerned with scheduling devices in a residential building such that energy costs, carbon dioxide emissions and thermal discomfort are minimized. It is shown that local scalarization optima are schedules that balance the three objectives. The analysis and the experiments presented in this work enable decision makers to make better choices by applying methods generating more options that conform to their preferences.