Zielgrößenoptimierung

Pareto-Front (2D, Nicht-Dominanz-Filter)

Filtert eine Menge von Punkten auf die nicht-dominierten Lösungen — die Pareto-Front einer Multi-Ziel-Optimierung.

Statusvalidated

Version1.0.0

Beschreibung

Bei konkurrierenden Zielen (z.B. Mittelwert maximieren UND Streuung minimieren) gibt es selten eine einzelne Lösung, die alle Ziele gleichzeitig optimiert. Die Pareto-Front ist die Menge aller Punkte, bei denen keine Verbesserung in einem Ziel ohne Verschlechterung in einem anderen möglich ist. Algorithmus: ein Punkt a dominiert b, wenn a in jedem Ziel ≤ b ist und in mindestens einem Ziel echt kleiner. Nicht-dominierte Punkte (jene, die von keinem anderen dominiert werden) bilden die Front. Die Funktion erwartet Minimierung — für Maximierungs-Ziele die Vorzeichen tauschen.

Formeln

Dominanz

a ≻ b ⟺ (\forall i : a_{i} \leq b_{i}) \land (\exists i : a_{i} < b_{i})

a dominiert b, wenn a in jeder Komponente kleiner-gleich und in mindestens einer echt kleiner ist

Frontier

P = {x \in X : ∄ y \in X mit y ≻ x}

Pareto-Front: Punkte, die von keinem anderen dominiert werden

Annahmen

Alle Ziele werden minimiert (für Maximierung Vorzeichen umdrehen)
Punkte haben dieselbe Dimension (Anzahl Ziele)

Einschränkungen

Naïver O(n²)-Algorithmus — bei n > 10 000 Punkten effizientere Verfahren erwägen
Bei mehr als 3 Zielen wird die Pareto-Front in der Praxis schnell groß und schwer interpretierbar

Referenzen

Pareto, V. (1906). Manuale di Economia Politica
Deb, K. (2001). Multi-Objective Optimization Using Evolutionary Algorithms, Wiley — Chapter 2.4
Myers, R.H., Montgomery, D.C., Anderson-Cook, C.M. (2016). Response Surface Methodology, 4th Ed., Wiley — Chapter 6.5 (Multi-Response Optimization)