AG Optimierung

Approximation Methods for Multiobjective Optimization Problems

Das Projekt "Approximation Methods for Multiobjective Optimization Problems" ist Teil des "Programm des Projektbezogenen Personenaustauschs (PPP)" des DAAD und wird von 01. Januar 2018 bis 31. Dezember 2019 gefördert.

Das verbreitetste Lösungskonzept für multikriterielle Optimierungsprobleme (MOPs) ist die Pareto-Optimalität: Eine Lösung heißt Pareto-optimal (oder effizient), wenn es keine andere Lösung gibt, deren Zielfunktionswert in jeder Zielfunktion mindestens genauso gut und in mindestens einer Zielfunktion echt besser ist. Jede effiziente Lösung repräsentiert somit einen anderen Kompromiss zwischen den verschiedenen Zielfunktionen und ist potentiell für einen Entscheidungsträger relevant. Daher besteht das Ziel in der multikriteriellen Optimierung in der effizienten Berechnung der gesamten Menge der effizienten Lösungen (der effizienten Menge) oder einer guten Repräsentation davon.


Verschiedene Resultate in der Literatur zeigen, dass das exakte Lösen von MOPs häufig sehr schwierig ist - selbst wenn sich entsprechende einkriterielle Probleme in polynomieller Zeit lösen lassen. Zusätzlich kann die Kardinalität der effizienten Menge (oder sogar die ihres Bildes, der nichtdominierten Menge) exponentiell groß in der Eingabegröße sein. Dies liefert eine starke Motivation für die Berechnung von Approximationen der effizienten Menge bzw. der nichtdominierten Menge. Während in der Literatur zahlreiche Approximationsverfahren für spezifische (hauptsächlich kombinatorische) multikriterielle Optimierungsprobleme existieren, sind nur relativ wenige allgemeine Resultate und Verfahren zur Approximation multikriterieller Probleme bekannt.


Das klassische Konzept der Approximation multikriterieller Optimierungsprobleme resultiert aus einer direkten Übertragung des Approximationsbegriffs der einkriteriellen Optimierung: Analog zum einkriteriellen Fall, wo ein einzelner Approximationsfaktor ausdrückt, wie gut der Zielfunktionswert jeder zulässigen Lösung im Worst-Case approximiert wird, wird bei multikriteriellen Problemen ein einzelner Vektor an Approximationsfaktoren angegeben, der ausdrückt, wie gut jede zulässige Lösung im Worst-Case in allen Zielfunktionen approximiert wird. Da der Vektor der Approximationsfaktoren in jeder Komponenten den schlechtesten für irgendeine Lösung erzielten Approximationsfaktor enthält, erlaubt es dieses Konzept jedoch nicht, verschiedene Kompromisse zwischen der Approximation der verschiedenen Zielfunktionen abzubilden, die für verschiedene Lösungen auftreten können.


Daher beschäftigt sich dieses Projekt mit der Entwicklung und Untersuchung eines neuen Approximationsbegriffs für multikriterielle Optimierungsprobleme - der sogenannten Multi-Faktor-Approximation. Hier wird anstatt eines einzelnen Vektors an Approximationsfaktoren eine Menge verschiedener solcher Vektoren betrachtet und verlangt, dass jede zulässige Lösung mit den durch einen der Vektoren in der Menge gegebenen Approximationsfaktoren approximiert wird. Dies stellt eine Verallgemeinerung des klassischen Approximationsbegriffs dar, erlaubt aber eine wesentlich genauere Beschreibung der erzielten Approximationsgüte.


Im Laufe des des Projekts soll der neue Multi-Faktor-Approximationsbegriff untersucht und angewandt werden, um neue, akkurate Approximationsresultate zu erhalten. Dabei sollen sowohl Resultate für allgemeine MOPs als auch für MOPs mit einer spezifischen Struktur erzielt werden.

Partner

LAMSADE (Laboratoire d'Analyse et Modélisation de Systèmes pour l'Aide à la Décision), Université Paris Dauphine, Paris, Frankreich

Förderung

Zum Seitenanfang