OPTANO Algorithm Tuner – Die Entwickler im Interview

Der OPTANO Algorithm Tuner ist da und für jeden frei verfügbar. Wir haben uns gefragt, was man eigentlich tunen kann und wie das genau  funktioniert. Deshalb haben wir bei den Entwicklern Britta Heymann und Jannick Lange nachgefragt.

Britta Heymann

Britta Heymann

Britta Heymann ist als OR-Expertin vor allem für Optimierung, aber auch für Softwareentwicklung zuständig. Sie hat den OPTANO Algorithm Tuner schon als studentische Mitarbeiterin und in ihrer Masterarbeit entwickelt.

Jannick Lange

Jannick Lange

Jannick Lange ist in der Softwareentwicklung im Bereich Operations Research für Kundenprojekte und OPTANO Modeling verantwortlich. Er hat bereits als studentischer Mitarbeiter am OPTANO Algorithm Tuner gearbeitet.

Guten Morgen, vielen Dank, dass ihr beide mir heute Rede und Antwort zu unserem neuen Algorithm Tuner stehen werdet. Und da wären wir auch direkt bei der ersten Frage: Ein Algorithm Tuner – wozu braucht man den?

Britta Heymann: Da gibt es eine schöne Analogie, die wir oft benutzen: die Formel 1. Die Teams können an ihren Autos unheimlich viel einstellen, je nachdem ob die Strecke viele scharfe Kurven oder lange Geraden hat, wie das Wetter ist und so weiter. Das Auto wird also für jede Strecke neu eingestellt und getestet. Der Algorithmus ist das Auto und die Parameter können wir unterschiedlich einstellen, je nachdem für was der Algorithmus genutzt werden soll. Der Algorithm Tuner lässt quasi ganz viele Formel 1 Autos fahren und guckt, welche Zusammenstellung der Parameter für das aktuelle Problem die beste ist.

Britta, du bist seit Anfang an beim Projekt dabei. Wie seid ihr denn darauf gekommen, den Algorithm Tuner zu enwickeln?

Britta Heymann: Algorithm Tuning ist ein unheimlich spannendes Thema mit sehr vielen Anwendungsfällen. Wir hatten damals in Zusammenarbeit mit der Uni die Möglichkeit, das Thema anzugehen. Uns war es wichtig, dass wir die Schwerpunkte so legen konnten, wie sie für unsere Zwecke wichtig waren. Deshalb haben wir uns dazu entschieden, selbst eine Tuning-Software zu entwickeln. Ich konnte die erste Projektphase teilweise in mein Studium einbringen und mich später auch im Rahmen meiner Masterarbeit mit dem Algorithm Tuner beschäftigen.

Wann bist du zum Projekt dazugekommen, Jannick?

Jannick Lange: Als ich dazugekommen bin, war GGA schon implementiert und ich habe dann im Rahmen einer Studienarbeit bei Prof. Tierney den GGA++ Teil als Erweiterung in unseren Algorithm Tuner eingebaut.

GGA – Was ist das und wie funktioniert es?

Britta Heymann: Die Grundidee ist, dass der Tuner mit einer Menge an Parameter-Konfigurationen startet und diese dann auf clevere Weise Stück für Stück verbessert. In jedem Durchgang werden Konfigurationen getestet, indem der Algorithmus mit ihnen eine bestimmte Menge Eingabedaten durchrechnet. Dann werden die Ergebnisse verglichen und die besten Konfigurationen werden verwendet, um die Menge an Konfigurationen durch Kombinationen zu aktualisieren. Und das wird wieder und wieder wiederholt bis eine Abbruchbedingung erreicht ist.

Jannick Lange: Wenn aus den besten Konfigurationen neue erstellt werden, passiert das bei GGA nach dem Zufallsprinzip. Die Parameter beider Konfigurationen haben grob gesagt eine feste Wahrscheinlichkeit, für die neue Konfiguration ausgewählt zu werden. Bei GGA++ wird an dieser Stelle Machine Learning eingesetzt. Es werden mehrere 10.000 zufällige Konfigurationen erzeugt und „einfach vorhergesagt“ (das ist der Machine Learning Part), wie gut die sich verhalten werden. Dann wird die Konfiguration genutzt, die die beste Vorhersage hat. So kann man schneller gute Konfigurationen anstelle von Zufallskonfigurationen erzeugen.

Das tolle am Algorithm Tuner ist, dass jeder Nutzer frei wählen kann, ob er GGA oder GGA++ oder einen Mix daraus nutzen will.

Und was kann man damit machen? Algorithmen schneller?

GGA steht für Gender-Based Genetic Algorithm

Britta Heymann: Ja. (lacht) Im Wesentlichen ist die Idee von Algorithm Tuning, dass man einen bestehenden Algorithmus, den man vielleicht auch schon nutzt, so konfiguriert, dass er genau abgestimmt ist auf das Anwendungsgebiet bzw. eine bestimmte Art von Eingabedaten, die man vorliegen hat. Man kann bei Algorithmen häufig  irgendwelche Parameter setzen und die Werte, die dort voreingestellt sind, sind im Durchschnitt auch sehr gut! Aber für den eigenen, speziellen Anwendungsfalls kann man noch bessere Einstellungen finden. Besser – was besser heißt, kann man selbst bestimmen. Häufig heißt es natürlich, dass die Laufzeit kürzer wird. Es kann aber auch sein, dass man bei einem Algorithmus, der kein exaktes Ergebnis liefert, sondern Vorschläge, die Qualität dieser Vorschläge verbessern möchte.

In der Praxis investiert man also anfangs viel Rechenzeit, um eine gute Konfiguration zu finden. In der Nutzungsphase des Algorithmus profitiert man davon dann bei jedem Lauf, sodass insgesamt gesehen Ressourcen gespart werden.

Gibt es Möglichkeiten diese Rechenzeit am Anfang zu verkürzen?

Britta Heymann: Das wichtigste ist Parallelisierung! Wir können entweder gleichzeitig auf einem Rechner parallele Evaluationen ausführen oder auch mehrere Rechner in einem Rechnernetz nutzen – was ich empfehlen würde – etwa in Verbindung mit Cloud-Computing.

Wenn es beim Tuning um die Laufzeit geht, können wir so sogar Evaluationen frühzeitig abbrechen, wenn durch parallele Ergebnisse klar wird, dass die zugehörige Konfiguration nicht zu den besten gehören kann.

Man sollte auch unbedingt einstellen, dass ein Evaluationslauf nach einer bestimmten Zeit abgebrochen wird. Sonst wendet der Tuner möglicherweise viel Zeit für einen Lauf auf, der zufällig mit einer sehr schlechten Konfiguration gestartet ist und von dem eigentlich früh klar ist, dass er ein sehr schlechtes Ergebnis liefern wird.

Für welche Algorithmen eignet sich Tuning denn besonders? Oder gibt es auch Algorithmen, für die Tuning nicht geeignet ist?

Jannick Lange: Sinnvoll ist es immer, wenn Algorithmen verhältnismäßig lange Laufzeiten haben oder bei laufzeitkritische Algorithmen. Also wenn ein Modell in einer bestimmten Laufzeit gelöst werden muss. Das ist manchmal durch Tuning überhaupt erst möglich.

Was eignet sich schlecht? Grundsätzlich muss ein Algorithmus natürlich Parameter anbieten, mit denen das Verhalten beeinflusst werden kann.
Schwierig gestaltet sich das Tuning auch, wenn nur sehr wenige Instanzen verfügbar sind oder einzelne Auswertungen mehrere Stunden oder Tage benötigen. Im ersten Fall besteht die Gefahr eines Overfittings, also einer Parameterkombination, die zu stark auf die Trainingsinstanzen spezifiziert ist und im Allgemeinen keine Vorteile bietet. Im zweiten Fall kann es passieren, dass die benötigte Zeit für die Durchführung des Tunings in astronomische Höhen wächst. Eine mögliche Lösung für dieses Problem wäre es zum Beispiel „kleinere“ Instanzen aus der gleichen Problemklasse fürs Tuning zu nutzen – unter der Annahme, dass die gefundenen Konfigurationen auf Grund der strukturellen Ähnlichkeit übertragbar sind.

Britta Heymann: Im Wesentlichen muss man sich entscheiden, ob man am Anfang die Zeit für das Tuning investieren möchte. Ich denke, das bringt am meisten, wenn es besonders wichtig ist, dass der Algorithmus eine kurze Laufzeit erfüllt, oder aber wenn man den Algorithmus sehr häufig benutzt. Dann lohnt es sich, weil man bei jedem Lauf davon profitiert.

Je schneller der Algorithmus von Anfang an ist, umso schneller findet der Tuner auch gute Konfigurationen. Das heißt, dass selbst bei Algorithmen, die schon relativ schnell sind, das Tuning sinnvoll sein kann, weil das Tuning an sich dann auch schneller geht.

Gibt es etwas am Tuner, über das ihr euch besonders freut oder worauf ihr besonders stolz seid?

Britta Heymann: Ich bin stolz darauf, dass der Tuner tatsächlich so anpassbar geworden ist, wie wir uns das vorgestellt hatten! Und ich freu mich sehr, dass er jetzt veröffentlicht ist – und das auch noch open source.

Apropos open source – wie kam es dazu?

Jannick Lange: So steht der Tuner maximal vielen Anwendern zur Verfügung, ganz unabhängig von ihrem Budget. Und über Github können Anwender ganz leicht Feedback geben, Features vorschlagen oder sogar am Code mitarbeiten. Wir glauben, dass das die Hürden, den Tuner zu nutzen, sehr niedrig macht und hoffen, dass ihn viele nutzen und davon profitieren können.

Der OPTANO Algorithm Tuner ist als open source verfübar. Einfach herunterladen und ausprobieren!

Und wie geht es jetzt weiter?

Britta Heymann:  Je mehr man dran arbeitet, umso mehr Ideen hat man. (lacht) Wir haben ein paar Ideen, wie wir die Parallelisierung noch besser machen können, sodass der Tuner noch schneller wird. Wir arbeiten aber auch – in Kooperation mit der Uni Bielefeld – an einer inhaltlichen Verbesserung: Das ist das Graybox-Tuning. Dabei geht es darum, schon während der Evaluation Daten zu sammeln, so dass diese früher abgebrochen werden kann. Das wird sehr spannend, inwiefern das klappt und und wie viel schneller das Tuning dadurch wird.

Auch interessant…