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.

Als Beispiel für eine skalarisierte Mehrzieloptimierung (siehe unten) kann 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 Zielsetzungen definieren.

Zum Beispiel soll bei einer Kraftmaschine 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

→ Hauptartikel: Pareto-Ordnung

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

Beispiele sind:

• Lineare Gewichtung
• Chebychev Skalarisierung
• $\epsilon$-beschränkte Methode
• Boundary intersection method
• Minimax-Algorithmus, wobei jeweils die schlechteste aller Zielfunktionen optimiert wird

Lineare Gewichtung

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

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

Nicht-konvexe Pareto-Front und aufgefundene Optima durch lineare Gewichtung der Zielfunktionen.

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 $\epsilon$-beschränkte Methode wird das $n$ dimensionale Mehrzielproblem in $n$ eindimensionale Ziele (jeweils mit $n-1$ Nebenbedingungen) überführt, sodass man potentiell eine Menge mit verschiedenen Lösungen erhält.

${\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

→ Hauptartikel: Fitness-Funktion

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 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, sein Nachfolger der NSGA-III oder der SPEA.

Lösungen: Pareto-Menge

→ Hauptartikel: Pareto-Menge

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

• 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.