"Wasser": Ein Mehrdimensionales Benchmark Problem

Dies ist ein kurzes Essay das eigentlich in die Dokumentation von PGAPack gehört, aber ich habe es nicht geschafft, plotly Grafiken in ein github README.rst file einzubinden, nichtmal mit der Proxy-Seite raw.githack.com (das ist eine Seite die html und javascript files mit dem richtigen Content-Type ausliefert so dass man sie im Web-Browser anzeigen kann, github liefert diese Seiten mit dem Content-Type text/plain aus). Github weigert sich, einen iframe in einer github Seite zu rendern.

Das "Wasser Ressourcenplanungs-Problem" [RTS01] ist ein technisches Problem das als Benchmark für das Testen von Optimierungssalgorithmen mit mehreren Zielfunktionen in der Literatur verwendet wird, unter andererem in Klassikern wie dem NSGA-II Artikel [DPAM02]. Das Problem besteht aus sieben Randbedingungen und einer fünfdimensionalen Zielfunktion.

Ich nutze dieses Problem seit einiger Zeit als Test meiner NSGA-II Implementierung in PGAPack. Es ist im Verzeichnis examples/nsgaii und kann (nach compilieren) mit dem Test-Problem Index 12 aufgerufen werden:

examples/nsgaii/optimize 12

Die Ausgabe des Programms kann auch in der folgenden Datei gefunden werden:

test/nsgaii_optimize_12.data

Zum Testen liefere ich auch das Script crowdingplot zum Plotten von mehrdimensionalen Optimierungsproblemen mit. Es findet sich im selben Directory wie der Code für das Beispiel.

Das "Wasser" Problem hat eine starke Korrelation zwischen den Zielfunktionen 0 und 2 (was auch von Singh et. al. [SIR11] publiziert wurde), wir sehen das wenn wir die beiden Zielfunktionen gegeneinander plotten mit:

crowdingplot -x=0 -y=2 test/nsgaii_optimize_12.data

Der obige Aufruf von crowdingplot nutzt das matplotlib Backend, wenn das mit dem plotly Backend angezeigt werden soll (wo wie in der obigen Grafik) kann die -S Option verwendet werden.

Was wir in dieser Grafik sehen ist dass wir bei einer besseren Bewertung für die Zielfunktion 0 auch eine bessere Bewertung für die Zielfunktion 2 bekommen und umgekehrt, d.h., die Zielfunktionen widersprechen sich nicht. Ausserdem ist die Zielfunktion 3 redundant [SIR11] mit den anderen Zielfunktionen und man kann sie beim Plotten der Zielfunktionen weglassen. So kann eine fünfdimensionale Pareto-Front zu einer dreidimensionalen reduziert werden und mit crowdingplot in drei Dimensionen angezeigt werden, mit sehr ähnlichen Resultaten wenn man die Achsen auf gleiche Werte skaliert:

crowdingplot -3 -x=0 -y=1 -z=4 test/nsgaii_optimize_12.data
crowdingplot -3 -x=2 -y=1 -z=4 test/nsgaii_optimize_12.data

Da bedeutet einerseits dass das Beispiel nicht wirklich fünfdimensional ist – andererseits ist es nett, die Daten zu visualisieren was in fünf Dimensionen wohl nicht so einfach wäre.