Mehrzieloptimierung

Die Mehrzieloptimierung behandelt Probleme der Form min/max f(x) = (f_1(x), f_2(x), ..., f_k(x)) mit k≥2 Zielen über einer gemeinsamen Zulässigkeitsmenge x ∈ X. Anstelle eines einzelnen globalen Optimums wird die Pareto-effiziente Menge gesucht: x* ist Pareto-optimal genau dann, wenn kein y ∈ X mit f_i(y) ≤ f_i(x*) für alle i und strikter Ungleichheit für mindestens ein j existiert (Pareto 1906). Skalarisierungsansätze gliedern sich in fünf Familien: (1) Gewichtete Summe — min Σ w_i f_i, liefert Punkte auf der konvexen Hülle der Pareto-Front, verfehlt jedoch nicht-konvexe Bereiche; (2) ε-Constraint-Verfahren (Haimes u. a. 1971) — ein Ziel wird optimiert, die übrigen als f_i ≤ ε_i beschränkt; kann die gesamte Front abtasten; (3) Lexikographische Ordnung — Ziele werden nach Priorität sequenziell optimiert, der vorherige Optimalwert tritt als Restriktion in die nächste Stufe ein; (4) Zielprogrammierung (Charnes und Cooper 1961) — Anspruchsniveau pro Ziel, Abweichungsvariablen werden minimiert; (5) Mehrziel-Metaheuristiken — NSGA-II (Deb u. a. 2002), SPEA2 (Zitzler u. a. 2001) entwickeln eine Population, die parallel zur Pareto-Front konvergiert. Komplexität: jede Skalarisierung ist ein LP bei linearen Zielen; die vollständige Aufzählung oder Repräsentation der Pareto-Menge ist im Allgemeinen NP-schwer. Standardmonographien sind Miettinen (1999), Steuer (1986) und Ehrgott (2005).