imported>Thomas Dresler: Anpassung

2026-03-10T10:06:44Z

Anpassung

Neue Seite

{{Dieser Artikel|behandelt die mathematische Methode der ''Mehrzieloptimierung''. Für die ''Pareto-optimalen'' Zustände siehe [[Pareto-Optimum]].}}
In der [[Mathematik]] bezeichnet man mit '''Mehrzieloptimierung''' (auch '''Pareto-Optimierung''' nach [[Vilfredo Pareto]], '''mehrkriterielle Optimierung''', '''multikriterielle Optimierung''' oder '''Vektoroptimierung''') das Lösen eines [[Optimierungsproblem]]s 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 [[Lagrange-Multiplikator|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.

Als Beispiel für eine skalarisierte Mehrzieloptimierung (siehe unten) kann die [[Bayes’sche Optimierung]] gesehen werden, wobei eine Akquisionsfunktion einen gewissen [[Trade-off]] zwischen verschiedenen Zielen auswählt.

== Motivation ==
Bei vielen Optimierungsaufgaben lassen sich mehrere, voneinander grundsätzlich unabhängige [[Fitnessfunktion|Zielsetzungen]] definieren.

Zum Beispiel soll bei einer [[Kraftmaschine]] der
* [[Wirkungsgrad]] maximiert,
* die [[Leistung (Physik)|Leistung]] maximiert und
* der [[Luftschadstoff|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 [[Gewichtung]]sfaktoren zu einer gemeinsamen [[Optimierung (Mathematik)|Zielfunktion]] zusammenzufassen (siehe Skalarisierung der Zielfunktion). Man erhält auf diese Weise ein einfacheres 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 ==
{{Hauptartikel|Pareto-Ordnung}}
Liegen mehrere Teilziele <math>f_i</math> (mit <math>i>1</math>) vor, welche zu einer vektorwertigen Zielfunktion <math>\vec{f}=(f_1, \dots f_n)^T</math> zusammengefasst werden, so ist es im Allgemeinen nicht mehr möglich, genau ein Optimum <math>\vec{x}^*</math> zu finden. Dies liegt daran, dass hier für <math>n\geq 2</math> keine [[totale Ordnungsrelation]] existiert, welche nicht eine der Ziele bevorzugen würde. Daher können verschiedene Lösungen ''unvergleichbar'' sein.<ref>"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 PDF] </ref> Sprich, es gibt keine totale Ordnungsrelation, welche den Vergleich <math>\vec{f}(\vec{x}^*) \geq \vec{f}(\vec{x})</math> 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.<ref name="HwangMasud1979">{{Literatur |Autor=Ching-Lai Hwang, Abu Syed Md Masud |Titel=Multiple objective decision making, methods and applications: a state-of-the-art survey |Verlag=Springer-Verlag |Datum=1979 |ISBN=0-387-09111-4 |Online=https://archive.org/details/multipleobjectiv0000hwan |Abruf=2012-05-29}}</ref> Bekannte Beispiele für a-priori-Methoden sind die Nutzenfunktionsmethode (vgl. [[Indifferenzkurve]]), die [[Lexikographische Ordnung|lexikographische Methode]] und die [[Zielprogrammierung]]. Auch [[Metaheuristik]]en wie die [[Evolutionärer Algorithmus|evolutionären Algorithmen]] können bei einer geeigneten Ausgestaltung und vor allem bei einer geeigneten [[Fitnessfunktion]], basierend z. B. auf linearer Gewichtung, als a-priori-Methode eingesetzt werden.<ref name=":0">{{Literatur |Autor=Kaisa Miettinen |Titel=Introduction to Multiobjective Optimization: Noninteractive Approaches |Hrsg=Jürgen Branke, Kalyanmoy Deb, Kaisa Miettinen, Roman Słowiński |Sammelwerk=Multiobjective Optimization: Interactive and Evolutionary Approaches |Band=LNCS 5252 |Verlag=Springer |Ort=Berlin, Heidelberg |Datum=2008 |ISBN=978-3-540-88907-6 |DOI=10.1007/978-3-540-88908-3 |Seiten=1-26}}</ref><ref name=":1">{{Literatur |Autor=Wilfried Jakob, Christian Blume |Titel=Pareto Optimization or Cascaded Weighted Sum: A Comparison of Concepts |Sammelwerk=Algorithms |Band=7 |Nummer=1 |Datum=2014-03-21 |ISSN=1999-4893 |arXiv=2203.02697 |DOI=10.3390/a7010166 |Seiten=166–185}}</ref>

=== A-Posteriori-Methoden ===
A-posteriori-Methoden dienen der Erzeugung aller Pareto-optimalen Lösungen oder einer repräsentativen Teilmenge davon. 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;
* Spezielle [[evolutionäre Algorithmen]], bei denen ein Durchlauf des Algorithmus eine Menge von Pareto-optimalen Lösungen erzeugt;
* [[Deep Learning|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 (<math>\epsilon</math>-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.<ref name="Emmerich2018">M. T. M. Emmerich, A. H. Deutz: ''A tutorial on multiobjective optimization: fundamentals and evolutionary methods.'' Nat Comput 17, 2018, S. 585–609. https://doi.org/10.1007/s11047-018-9685-y</ref>

Beispiele sind:
* Lineare Gewichtung
* [[Chebychev Skalarisierung]]
* <math>\epsilon</math>-beschränkte Methode
* Boundary intersection method
* [[Minimax-Algorithmus]], wobei jeweils die schlechteste aller Zielfunktionen optimiert wird<ref>J. Xu, Z. Tao: ''Rough Multiple Objective Decision Making.'' Vereinigtes Königreich: CRC Press, 2011, S. 67 https://www.google.de/books/edition/Rough_Multiple_Objective_Decision_Making/zwDSBQAAQBAJ?hl=de&gbpv=1&dq=the%20minimax%20multi%20objective%20-game&pg=PA67</ref>

[[Datei:NonConvex.gif|mini|Nicht-konvexe Pareto-Front und aufgefundene Optima durch lineare Gewichtung der Zielfunktionen.]]
==== Lineare Gewichtung ====
Bei der Linearen Gewichtung führt man eine vereinfachte Zielfunktion ein, welche die Teilziele gewichtet:
:<math>f = \sum_{i=1}^n \lambda_i f_i</math>
Es ist zu beachten, dass die Pareto-Menge im Allgemeinen nicht vollständig durch mehrere Läufe mit geeignet variierten Gewichtungsfaktoren in der skalarisierten Zielfunktion bestimmt werden kann (vergleiche Animation).<ref name=":0" details="Weighting Method, S. 10-12" />
==== Epsilon beschränkte Methode ====
Bei der <math>\epsilon</math>-beschränkten Methode wird das <math>n</math> dimensionale Mehrzielproblem in <math>n</math> eindimensionale Ziele (jeweils mit <math>n-1</math> Nebenbedingungen) überführt, sodass man potentiell eine Menge mit verschiedenen Lösungen erhält.<ref name=":0" details="ε-Constraint Method, S. 12-13" /><ref name="Mavrotas2009">{{Literatur |Autor=George Mavrotas |Titel=Effective implementation of the ε-constraint method in Multi-Objective Mathematical Programming problems |Sammelwerk=Applied Mathematics and Computation |Band=213 |Nummer=2 |Datum=2009 |ISSN=0096-3003 |Seiten=455–465 |DOI=10.1016/j.amc.2009.03.037}}</ref>

::<math>
\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}</math>

=== Evolutionäre Algorithmen ===
{{Hauptartikel|Fitness-Funktion}}
[[Evolutionärer Algorithmus|Evolutionäre Algorithmen]] (EA) können sowohl als a-priori- als auch als a-posteriori Methode eingesetzt werden. Maßgeblich kommt es dabei auf die Formulierung der Fitnessfunktion an, welche die Qualität der durch den EA erzeugten Lösungsvorschläge bewertet. Wenn die Fitnessfunktion auf der linearen Gewichtung beruht, kann der resultierende EA als a-priori-Methode Verwendung finden, wobei zu beachten ist, dass damit nur die konvexen Teile der Paretofront bestimmt werden können.<ref name=":0" details="Weighting Method, S. 10-12" /><ref name=":1" />

Bei geeigneter Ausgestaltung des EAs und Verwendung der Pareto-Optimalität bei der Formulierung der Fitnessfunktion können EAs zur Bestimmung der Pareto-Front – oder zumindest wesentlicher Teile davon – genutzt werden. Da EAs als populationsbasierte (Optimierungs-)Methode eine Vielzahl von Lösungen gleichzeitig betrachten, kann dies auch in einem Lauf erfolgen.<ref name=":12">{{Literatur |Autor=Kalyanmoy Deb |Titel=Introduction to Evolutionary Multiobjective Optimization |Hrsg=Jürgen Branke, Kalyanmoy Deb, Kaisa Miettinen, Roman Słowiński |Sammelwerk=Multiobjective Optimization: Interactive and Evolutionary Approaches |Band=LNCS |Nummer=5252 |Verlag=Springer |Ort=Berlin, Heidelberg |Datum=2008 |ISBN=978-3-540-88907-6 |DOI=10.1007/978-3-540-88908-3 |Seiten=58-96 |Online=https://www.researchgate.net/publication/242505658}}</ref> Häufig eingesetzte EAs zur Bestimmung der Pareto-Front sind der NSGA-II,<ref>{{Literatur |Autor=K. Deb, A. Pratap, S. Agarwal, T. Meyarivan |Titel=A fast and elitist multiobjective genetic algorithm: NSGA-II |Sammelwerk=IEEE Transactions on Evolutionary Computation |Band=6 |Nummer=2 |Datum=2002-04 |ISSN=1089-778X |Seiten=182–197 |DOI=10.1109/4235.996017}}</ref> sein Nachfolger der NSGA-III<ref>{{Literatur |Autor=Kalyanmoy Deb, Himanshu Jain |Titel=An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints |Sammelwerk=IEEE Transactions on Evolutionary Computation |Band=18 |Nummer=4 |Datum=2014-08 |ISSN=1089-778X |Seiten=577–601 |DOI=10.1109/TEVC.2013.2281535}}</ref><ref>{{Literatur |Autor=Himanshu Jain, Kalyanmoy Deb |Titel=An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point Based Nondominated Sorting Approach, Part II: Handling Constraints and Extending to an Adaptive Approach |Sammelwerk=IEEE Transactions on Evolutionary Computation |Band=18 |Nummer=4 |Datum=2014-08 |ISSN=1089-778X |Seiten=602–622 |DOI=10.1109/TEVC.2013.2281534}}</ref> oder der SPEA.<ref>{{Literatur |Autor=Eckart Zitzler, Marco Laumanns, Lothar Thiele |Titel=SPEA2: Improving the strength pareto evolutionary algorithm |Band=Technical Report |Nummer=103 |Verlag=ETH Zürich, Computer Engineering and Networks Laboratory (TIK) |Datum=2001-05 |Seiten=1-21 |Online=https://www.research-collection.ethz.ch/handle/20.500.11850/145755 |Abruf=2023-11-14 |DOI=10.3929/ethz-a-004284029}}</ref>

== Lösungen: Pareto-Menge ==
{{Hauptartikel|Pareto-Menge}}
[[Datei:Front pareto.svg|mini|300px|Beispiel einer [[Pareto-Front]] (in rot)]]
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 ==
* [[Trade-off]]
* [[Entscheidung unter Sicherheit#Entscheidungsregeln bei multi-kriteriellen Entscheidungsproblemen]]
* [[Multikriterielle Entscheidungsanalyse]]
* [[Transfer Learning]]

== Literatur ==
* M. T. M. Emmerich, A. H. Deutz: ''A tutorial on multiobjective optimization: fundamentals and evolutionary methods.'' Nat Comput 17, 2018, S. 585–609. 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 ==
<references></references>

[[Kategorie:Optimierungsalgorithmus]]

Mehrzieloptimierung - Versionsgeschichte

imported>Thomas Dresler: Anpassung