Neue Messungen zur Nicht-Dominanz Sortierung

Dies ist eine Aktualisierung zu einem früheren Beitrag [Sch25] zur Implementierung von Nicht-Dominanz Sortierung in PGAPack. Nicht-Dominanz Sortierung ist eine zentrale Komponente von Optimierungsalgorithmen mit mehreren Zielfunktionen.

Im früheren Beitrag hatte ich nicht erwähnt für wie viele Generation der Test lief: Die Anzahl der Generationen im letzten und in diesem Test war 200. Im letzten Test war der Code ohne Optimierung compiliert. Die folgenden Messungen wurden mit der Option -O3 gemacht, der besten die gcc anbietet. Ausserdem war mir aufgefallen, dass meine Implementierung des DTLZ-1 tests [DTLZ05] quadratisch in der Anzahl der Zielfunktionen ist und ich befürchtete dass dies die Tests beeinflussen könnte. Es stellte sich aber heraus dass dies nicht der Fall war, der Overhead für 20 Zielfunktionen ist immer noch zu klein um bemerkbar zu sein.

Zusätzlich zu den ersten Tests messe ich jetzt – neben der Gesamtzeit – auch die Zeit nur für die Nicht-Dominanz Sortierung. Im folgenden gibt es also zwei Typen von Grafiken: Wo im Titel "Overall" steht ist die Zeit für die Zielfunktion und was der Algorithmus sonst noch an Verwaltung tut inkludiert (Gesamtzeit). Die anderen welche mit "Non-dominated" anfangen messen nur die Zeit für die Nicht-Dominanz Sortierung.

Also sehen wir uns erstmal die Gesamt-Zeiten an, verglichen mit meinem letzten Beitrag [Sch25] diesmal mit eingeschalteter Optimierung.

Ich habe hier auch die absolute Differenz zwischen den Messungen geplottet. Die absolute Differenz wenn die Gesamtzeit gemessen wird verglichen wenn nur die Zeit für die Nicht-Dominanz Sortierung gemessen wird ist bis auf ein paar Millisekunden gleich (wie man erwarten würde). Wir sehen dass die absoluten Differenzen schneller als linear wachsen, was man erwartet da die Laufzeit des alten Algorithmus quadratisch mit der Populationsgröße wächst und damit das kleinere Wachstum des neuen Algorithmus überdeckt.

Schließlich zeigt die folgende Grafik die Beschleunigungen die wir bekommen. Ähnlich wie Jensen [Jen03] sind die Zeiten für den neuen Algorithmus bei großer Anzahl von Zielfunktionen und niedriger Anzahl von Individuen etwas größer. Die absolute Differenz ist aber sehr klein wie man in der vorangegangenen Grafik nur sehen kann wenn man zu den ersten zwei Messungen mit Populationsgröße 100 und 200 zoomt. Die absolute Differenz ist unter 30ms für 200 Generationen. Ich werde also keinen Spezialfall für kleine Populationsgrößen implementieren – dies wäre einerseits schwierig weil es von der CPU-Geschwindigkeit abhängt wie man im letzten Blog-Beitrag sehen kann [Sch25] wo wir (bei abgeschalteter Optimierung) keine Verlangsamung mit dem neuen Algorithmus sehen. Ausserdem braucht man für viele Zielfunktionen typischerweise größere Populationen um die Pareto-Front abzudecken [Jen03].

Die folgenden Grafiken enthalten die Messungen wo nur die Zeit für die Nicht-Dominanz Sortierung gemessen wurde. Wenn man die Beschleunigung vergleicht (in der vorhergehenden Grafik als auch am Ende der folgenden Grafiken), besonders wenn man die Kurven für 2, 3 und 5 Zielfunktionen ausschaltet (das ist möglich wennn man in der Legende auf der rechten Seite der Grafik klickt), sieht man dass die Zuwächse sub-linear sind. Bei der Berechnung der Kurve teilen wir hier etwas das quadratisch wächst durch etwas was etwas stärker als linear wächst. Der Bruch ist dann sub-linear wie erwartet. Dabei sollte die Wirksamkeit des neuen Algorithmus nicht unterschätzen: Wie oben gezeigt wachsen die absoluten Differenzen stärker als linear.

Das Script das zur Messung verwendet wurde, das Script zum Plotten und die gemessenen Daten (und die alten gemessenen Daten) mache ich verfügbar falls das jemand nachvollziehen möchte. Das Beispiel ist in PGAPack im Verzeichnis examples/nsgaii aber die Version mit dem neuen Nicht-Dominanz Sortierungs-Algorithmus und der Instrumentierung zur Zeitmessung im Beispiel ist noch nicht released während ich das hier schreibe.