Mehrzieloptimierung

In der Mathematik bezeichnet man mit Mehrzieloptimierung (auch Pareto-Optimierung nach Vilfredo Pareto, mehrkriterielle Optimierung, multikriterielle Optimierung oder Vektoroptimierung) das Lösen eines Optimierungsproblems mit mehreren (sich möglicherweise widersprechenden) Zielen, also eines mehrkriteriellen oder multikriteriellen Problemes. Dass sich die Ziele widersprechen können unterscheidet die Mehrzieloptimierung von der Optimierung unter Nebenbedingungen.

Ein Pareto-Optimum ist eine Lösung eines Optimierungsproblems mit der Eigenschaft, dass kein Ziel verbessert werden kann, ohne ein anderes Ziel zu verschlechtern.

Motivation

Bei vielen Optimierungsaufgaben lassen sich mehrere, voneinander grundsätzlich unabhängige Zielsetzungen definieren.

Zum Beispiel soll bei einer Kraftmaschinen der

• Wirkungsgrad maximiert
• die Leistung maximiert und
• der Schadstoffausstoß minimiert werden.

Oft gibt es keine Lösung, die in allen Zielen zugleich jeweils am besten ist; die Ziele sind oft gegenläufig, und eine Verbesserung bezüglich eines Ziels bewirkt eine Verschlechterung bei einem anderen. Man kann sich zum Beispiel in der Situation befinden, dass man die maximale Leistung eines Motors nur erhöhen kann (eine Verbesserung), wenn gleichzeitig der Wirkungsgrad sinkt (eine Verschlechterung).

Das übliche Vorgehen zur Behandlung solcher Aufgaben ist es, die interessierenden Ziele als Teilziele aufzufassen und sie mittels Gewichtungsfaktoren zu einer gemeinsamen Zielfunktion zusammenzufassen (siehe Skalarisierung der Zielfunktion). Man erhält auf diese Weise ein einfaches Problem – statt mehrerer Ziele hat man nun nur noch ein Ziel, die „multikriterielle Optimierung“ wird also auf ein (einziges) (Gesamt-)Kriterium reduziert. Dieses vereinfachte Optimierungsproblem löst man mit einem der unter Operations Research genannten Verfahren und erhält dadurch eine optimale Lösung für die vereinfachte Zielfunktion.

Bei nicht ineinander umrechenbaren Zielgrößen, wie etwa im gegebenen Beispiel, sind die anzusetzenden Gewichtungsfaktoren willkürlich und in bestimmten Rahmen subjektiv. Hierdurch ergibt sich auch eine entsprechende Willkürlichkeit beim Auffinden der gesuchten „besten“ Lösung des Optimierungsproblems. Eine sinnvolle Vorgehensweise ist in solchen Fällen die separate Optimierung für alle möglichen Kombinationen von Gewichtungsfaktoren. Dabei wird man in der Regel nicht eine einzelne beste Lösung finden, da die Zielkriterien meist miteinander in Konflikt stehen (wie oben die maximale Leistung und der Wirkungsgrad).

Pareto-Ordnung

Liegen mehrere Teilziele ${\displaystyle f_{i}}$ (mit ${\displaystyle i>1}$) vor, welche zu einer vektorwertigen Zielfunktion ${\displaystyle {\vec {f}}=(f_{1},\dots f_{n})^{T}}$ zusammengefasst werden, so ist es im Allgemeinen nicht mehr möglich genau ein Optimum ${\displaystyle {\vec {x}}^{*}}$ zu finden. Dies liegt daran, dass für ${\displaystyle n\geq 2}$ keine totale Ordnungsrelation existiert. Daher können verschiedene Lösungen unvergleichbar sein.^[1]: Sprich es gibt keine totale Ordnungsrelation, welche den Vergleich ${\displaystyle {\vec {f}}({\vec {x}}^{*})\geq {\vec {f}}({\vec {x}})}$ leisten könnte. Lediglich die Pareto-Ordnung kann betrachtet werden.

Arten der Mehrzieloptimierung

A-priori-Methoden

A-priori-Methoden erfordern, dass ausreichende Präferenzinformationen ausgedrückt werden, bevor der Lösungsprozess beginnt.^[2] Bekannte Beispiele für a-priori-Methoden sind die Nutzenfunktionsmethode (vgl. Indifferenzkurve), die lexikographische Methode und die Zielprogrammierung.

A-Posteriori-Methoden

Erzeugung aller Pareto-optimalen Lösungen oder einer repräsentativen Teilmenge der Pareto-optimalen Lösungen. Die meisten a-posteriori-Methoden fallen in eine der folgenden drei Klassen:

• Mathematische Programmierung, bei denen ein Algorithmus wiederholt wird und jeder Durchlauf des Algorithmus eine Pareto-optimale Lösung erzeugt
• Evolutionäre Algorithmen, bei denen ein Durchlauf des Algorithmus eine Menge von Pareto-optimalen Lösungen erzeugt;
• Deep-Learning-Methoden, bei denen ein Modell zunächst auf einer Teilmenge von Lösungen trainiert wird und dann abgefragt wird, um andere Lösungen auf der Pareto-Front bereitzustellen.

Ansätze

Skalarisierung

Skalarisierungsansätze können sowohl A-priori-Methoden sein (Beispiel lineare Gewichtung) als auch A-posteriori Methoden (${\displaystyle \epsilon }$-beschränkte Methode).

Um zu einem einfacher lösbaren Problem zu gelangen, kann die vektorwertige Zielfunktion skalarisiert werden, indem die verschiedenen Teilziele mithilfe einer Aggregierungsfunktion zusammengefasst werden^[3].

Beispiele sind:

• Lineare Gewichtung
• Chebychev Skalarisierung
• ${\displaystyle \epsilon }$-beschränkte Methode
• Boundary intersection method

Lineare Gewichtung

Bei der Lineare Gewichtung führt man eine vereinfachte Zielfunktion ein, welche die Teilziele gewichtet:

${\displaystyle f=\sum _{i=1}^{n}\lambda _{i}f_{i}}$

Es ist zu beachten, dass die Pareto-Menge im Allgemeinen nicht vollständig durch die Variation von Gewichtungsfaktoren in der skalarisierten Zielfunktion bestimmt werden kann (vergleiche Animation).

Epsilon beschränkte Methode

Bei der ${\displaystyle \epsilon }$-beschränkte Methode wird das ${\displaystyle n}$ dimensionale Mehrzielproblem in ${\displaystyle n}$ eindimensionale Ziele (jeweils mit ${\displaystyle n-1}$ Nebenbedingungen) überführt, sodass man potentiell eine Menge mit verschiedenen Lösungen erhält^[4].

${\displaystyle {\begin{array}{ll}\min &f_{j}(x)\\{\text{s.t.}}&x\in X\\&f_{i}(x)\leq \epsilon _{i}{\text{ for }}i\in \{1,\ldots ,k\}\setminus \{j\}\end{array}}}$

Evolutionäre Algorithmen

Evolutionäre Algorithmen sind Beispiele für eine a-posteriori Methode. Die Qualität eines Lösungsvorschlags eines evolutionären (Optimierungs-)Algorithmus wird durch eine Fitnessfunktion beschrieben^[5][6] und werden unter anderem bei Metaheuristiken wie den evolutionären Algorithmen (EA) verwendet. Häufig eingesetzte EAs zur Bestimmung der Pareto-Front sind der NSGA-II,^[7] sein Nachfolger der NSGA-III^[8][9] oder der SPEA.^[10]

Lösungen: Pareto-Menge

Da keine eindeutig beste Lösung definiert ist, bestimmt man eine Menge von Lösungen des Optimierungsproblems, bei der eine Verbesserung eines Zielfunktionswertes nur noch durch Verschlechterung eines anderen erreicht werden kann, also die Menge optimaler Kompromisse. Diese Lösungsmenge bezeichnet man als Pareto-Menge des zugrunde liegenden Paretooptimierungsproblems. Bei einem Optimierungsproblem mit n Zielen wird die Pareto-Menge eine (n − 1)-dimensionale Hyper-Grenzfläche darstellen. Die Elemente der Pareto-Menge sind „pareto-optimal“.

Siehe auch

• Multikriterielle Entscheidungsanalyse
• Entscheidung unter Sicherheit#Entscheidungsregeln bei multi-kriteriellen Entscheidungsproblemen
• Transfer Learning
• Trade-off

Literatur

• Emmerich, M.T.M., Deutz, A.H. A tutorial on multiobjective optimization: fundamentals and evolutionary methods. Nat Comput 17, 585–609 (2018). https://doi.org/10.1007/s11047-018-9685-y
• Matthias Ehrgott: Multicriteria Optimization. Lecture Notes in Economic and Mathematical Systems 491, Springer Verlag, 2000.

Einzelnachweise

1. ↑ "The main difficulty is that, in contrast to the single-objective case where there is a total order relation between solutions, Pareto dominance is a partial order, which leads to solutions (and solution sets) being incomparable" Li, M., López-Ibáñez, M., & Yao, X. (Accepted/In press). Multi-Objective Archiving. IEEE Transactions on Evolutionary Computation. https://arxiv.org/pdf/2303.09685.pdf
2. ↑ Ching-Lai Hwang, Abu Syed Md Masud: Multiple objective decision making, methods and applications: a state-of-the-art survey. Springer-Verlag, 1979, ISBN 978-0-387-09111-2 (archive.org [abgerufen am 29. Mai 2012]). 
3. ↑ Emmerich, M.T.M., Deutz, A.H. A tutorial on multiobjective optimization: fundamentals and evolutionary methods. Nat Comput 17, 585–609 (2018). https://doi.org/10.1007/s11047-018-9685-y
4. ↑ George Mavrotas: Effective implementation of the ε-constraint method in Multi-Objective Mathematical Programming problems. In: Applied Mathematics and Computation. 213. Jahrgang, Nr. 2, 2009, ISSN 0096-3003, S. 455–465, doi:10.1016/j.amc.2009.03.037. 
5. ↑ Kaisa Miettinen: Introduction to Multiobjective Optimization: Noninteractive Approaches. In: Jürgen Branke, Kalyanmoy Deb, Kaisa Miettinen, Roman Słowiński (Hrsg.): Multiobjective Optimization: Interactive and Evolutionary Approaches. LNCS 5252. Springer, Berlin, Heidelberg 2008, ISBN 978-3-540-88907-6, S. 1–26, doi:10.1007/978-3-540-88908-3. 
6. ↑ Wilfried Jakob, Christian Blume: Pareto Optimization or Cascaded Weighted Sum: A Comparison of Concepts. In: Algorithms. Band 7, Nr. 1, 21. März 2014, ISSN 1999-4893, S. 166–185, doi:10.3390/a7010166, arxiv:2203.02697. 
7. ↑ K. Deb, A. Pratap, S. Agarwal, T. Meyarivan: A fast and elitist multiobjective genetic algorithm: NSGA-II. In: IEEE Transactions on Evolutionary Computation. Band 6, Nr. 2, April 2002, ISSN 1089-778X, S. 182–197, doi:10.1109/4235.996017. 
8. ↑ Kalyanmoy Deb, Himanshu Jain: An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints. In: IEEE Transactions on Evolutionary Computation. Band 18, Nr. 4, August 2014, ISSN 1089-778X, S. 577–601, doi:10.1109/TEVC.2013.2281535. 
9. ↑ Himanshu Jain, Kalyanmoy Deb: An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point Based Nondominated Sorting Approach, Part II: Handling Constraints and Extending to an Adaptive Approach. In: IEEE Transactions on Evolutionary Computation. Band 18, Nr. 4, August 2014, ISSN 1089-778X, S. 602–622, doi:10.1109/TEVC.2013.2281534. 
10. ↑ Eckart Zitzler, Marco Laumanns, Lothar Thiele: SPEA2: Improving the strength pareto evolutionary algorithm. Technical Report, Nr. 103. ETH Zürich, Computer Engineering and Networks Laboratory (TIK), Mai 2001, S. 1–21, doi:10.3929/ethz-a-004284029 (ethz.ch [abgerufen am 14. November 2023]).