08.10.2018

Auf den Gebieten der heuristischen Optimierung und des maschinellen Lernens ist Experimentieren der Weg, um die Leistung eines Algorithmus-Setups und die Härte von Problemen zu bewerten. Gutes Experimentieren ist kompliziert. Die meisten Algorithmen in der Domäne sind jederzeit verfügbare Algorithmen, was bedeutet, dass sie ihre Approximationsqualität im Laufe der Zeit verbessern können. Dies bedeutet, dass ein Algorithmus anfänglich besser abschneidet als ein anderer, aber am Ende zu schlechteren Lösungen konvergiert. Statt einzelner Endergebnisse muss das gesamte Laufzeitverhalten von Algorithmen verglichen werden (und die Laufzeit kann auf verschiedene Arten gemessen werden). Wir wollen nicht nur wissen, welcher Algorithmus am besten funktioniert und welches Problem am schwierigsten ist - ein Forscher möchte wissen, warum. Wir führen einen Prozess ein, der 1) den Fortschritt von Algorithmus-Setups auf verschiedenen Probleminstanzen basierend auf in Experimenten gesammelten Daten automatisch modellieren kann, 2) diese Modelle zum Auffinden von Clustern von Algorithmus- (oder Probleminstanz-) Verhalten verwendet und 3) Gründe vorschlägt, warum eine bestimmte Algorithmuseinstellung (oder Probleminstanz) zu einem bestimmten Algorithmus (oder Probleminstanz) Verhaltenscluster gehört. Diese Schlussfolgerungen auf hoher Ebene werden in Form von Entscheidungsbäumen präsentiert, die Algorithmusparameter (oder Instanzmerkmale) auf Cluster-IDs beziehen. Wir betonen die Dualität der Analyse von Algorithmus-Setups und Probleminstanzen. Unser Prozess wurde als Open-Source-Software implementiert und in zwei Fallstudien, dem Problem der maximalen Erfüllbarkeit und dem Problem des reisenden Verkäufers, getestet. Neben der grundsätzlichen Anwendung auf rohe experimentelle Daten, die zu Clustern und Erklärungen des "quantitativen" Algorithmusverhaltens führen, erlaubt unser Prozess auch "qualitative" Schlussfolgerungen, indem er mit Daten versorgt wird, die mit Problemmerkmalen oder Algorithmusparametern normalisiert sind. Es kann auch rekursiv angewendet werden, um beispielsweise das Verhalten der Algorithmen im Cluster mit den leistungsstärksten Setups für die Probleminstanzen zu untersuchen, die zu dem Cluster der härtesten Instanzen gehören. Beide Anwendungsfälle werden in den Fallstudien untersucht.