Nicht-Dominanz Sortierung bei Optimierung mit mehreren Zielfunktionen

Einige Leser hier wissen dass ich PGApack, ein Paket für Genetische Algorithmen, zusammen mit PGApy einer Python Bibliothek pflege (maintaine). PGAPack implementiert Optimierung mit mehreren Zielfunktionen (multi-objective optimization) mit NSGA-II [DPAM02] und NSGA-III [DJ14], [JD14].

Mehrere Zielfunktionen heisst dass wir mehr als ein Zielfunktion (auch Fitness-Funktion genannt) haben. Typischerweise widersprechen sich die Ziele – wenn eine Lösung in einer Zielfunktion besser ist wird, wird sie typischerweise in einer anderen Lösung schlechter – wir müssen uns also überlegen was besser im Kontext von mehreren Zielfunktionen bedeutet. Eine Lösung \(A\) ist strikt besser als eine andere Lösung \(B\) – wir sprechen davon dass Lösung \(A\) die Lösung \(B\) dominiert – wenn \(A\) besser oder gleich \(B\) in allen Zielfunktionen ist und strikt besser in mindestens einer davon.

Weil wir keine einfache Fitness für Lösungen haben, etablieren Algorithmen für mehrere Zielfunktionen typischerweise eine Rangfolge (ranking) der Lösungen nach Dominanz. Lösungen die nicht von einer anderen Lösung dominiert werden bekommen den Rang 0. Dann entfernt man alle Lösungen mit Rang 0. Alle Lösungen die dann nicht dominiert sind bekommen Rang 1 usw. Diese Prozedur heisst typischerweise Nicht-Dominanz Sortierung (non-dominated sorting). Der Rang ist dann eine der Komponenten für eine neue Fitness-Funktion.

Der NSGA-II Artikel [DPAM02] implementiert diese Sortierung indem jede Lösung gegen jede andere Lösung der Population auf Dominanz verglichen wird. Dann werden nicht-dominierte Lösungen eine nach der anderen entfernt und die Ränge zugewiesen wie oben angedeutet. Dieser Algorithmus zur Sortierung hat eine Laufzeit die mit der Anzahl der Lösungen quadratisch ansteigt. In der Informatik schreiben wir mit der O-Notation (auch Landau Symbole) Aussagen über die Laufzeit auf. Der quadratische Aufwand wird als \(O(n^2)\) notiert, wobei \(n\) die Anzahl der Lösungen ist.

2003 hat Jensen [Jen03] einen Algorithmus publiziert der die Nicht-Dominanz-Sortierung mit einem Aufwand von \(O\left(n\cdot(\log n)^{m-1}\right)\) durchführen kann wobei \(m\) die Anzahl der Zielfunktionen (und \(n\) wieder die Populationsgröße) ist. Jensen's Algorithmus wurde zehn Jahre später nochmal geändert publiziert weil das Original nicht mit gleichen Werten der Zielfunktionen umgehen konnte. Jensen schreibt zwar das sei einfach, offensichtlich nicht für andere [FGP13]. Ein Jahr später gab es dann nochmal eine kleinere Modifikation um formal zu beweisen dass die Laufzeit-Komplexität wirklich der obigen Formel folgt [BS14].

Ich habe diesen Algorithmus jetzt implementiert und neue gegen alte Version verglichen. Als Benchmark verwende ich dennn DTLZ-1 Algorithmus [DTLZ05] wie Jensen im Original-Artikel [Jen03]. Ähnlich wie Jensen habe ich die Zeiten bis zu einer Populationsgröße von 2000 gemessen. Auch ich bekomme die größte Beschleunigung für eine niedrige Anzahl von Zielfunktionen. In den folgenden Grafiken ist die Y-Achse in Sekunden CPU-Zeit während die X-Achse die Populationsgröße beschreibt. Es gibt drei Grafiken für 2, 10 und 20 Zielfunktionen. Der Aufwand steigt mit der Anzahl der Zielfunktionen, die anderen (nicht gezeigten) Grafiken sind sehr ähnlich. Die Grafiken haben lineare Achsen, nicht wie bei Jensen doppelt logarithmisch. Alle Messungen beinhalten die Gesamtzeit die der Algorithmus braucht, nicht nur die Nicht-Dominanz-Sortierung, also z.B. auch die Zeit um die Evaluierungsfunktion zu berechnen. Diese Zeiten habe ich nicht separat gemessen.

Die folgende Grafik zeigt die erreichten Beschleunigungen. Bei Jensen waren für hohe Anzahl von Zielfunktionen die Zeiten für den neuen Algorithmus leicht größer. Diesen Effekt sehe ich nicht, vermutlich weil auch die Rechner die letzten 20 Jahre etwas schneller wurden (und damit der Grund-Overhead kleiner ist). Interessant ist, dass beginnend mit etwa 5 Zielfunktionen sich die Beschleunigung mit der Anzahl der Zielfunktionen nicht mehr ändert (das sind natürlich die relativen Werte im Vergleich zum \(O(n^2)\) Algorithmus). Dies passiert vermutlich deshalb weil beide Algorithmen keine weiteren Zielfunktionen vergleichen wenn etabliert ist dass zwei Lösungen einander nicht dominieren: Das ist der Fall wenn eine Lösung bei einer Zielfunktion einen höheren Wert hat während sie bei einer anderen Zielfunktion einen niedrigeren Wert hat. Weil nach einigen Optimierungsschritten die meisten Lösungen nicht-dominiert sind kann anscheinend die Nicht-Dominanz schnell berechnet werden ohne alle Zielfunktionen zu vergleichen.