A New Approach to Characterising Optimisation Problems Using Programmatic Representation and Complexity Measures

Stellen Sie sich vor, Sie versuchen, einem Roboter beizubringen, ein Labyrinth zu lösen. Manchmal ist das Labyrinth ein einfacher, gerader Flur; manchmal ist es ein sich windendes, drehendes Labyrinth mit Sackgassen und Fallen. In der Welt der Informatik nennt man das Optimierung: das Finden der bestmöglichen Lösung für ein Problem. Aber hier liegt der Haken: Nicht alle Labyrinthe sind gleich. Einige sind für einen Roboter leicht zu lösen, während andere selbst die klügsten Algorithmen auf sich angewiesen machen.

Um Robotern zu helfen, die richtige Strategie zu wählen, versuchen Wissenschaftler, diese Labyrinthe zu „charakterisieren“ oder zu beschreiben, bevor der Roboter überhaupt losläuft. Sie suchen nach Hinweisen, wie etwa wie uneben der Boden ist oder wie viele Sackgassen existieren. Normalallerweise muss der Roboter dazu einige Schritte machen, sich umsehen und das Gelände messen. Das ist so, als würde man einen Späher in die Dunkelheit schicken, um eine Höhle zu kartieren. Aber was wäre, wenn der Roboter einfach den Bauplan des Labyrinths betrachten und erraten könnte, wie schwer es zu lösen ist, ohne jemals einen Fuß hineingesetzt zu haben? Das ist die große Frage, die dieses Paper stellt. Es legt nahe, dass die Art und Weise, wie ein Problem in Computercode geschrieben ist, das Geheimnis darüber bergen kann, wie schwierig es zu lösen ist – genau wie die Komplexität eines Rezepts erahnen lässt, wie schwierig das Kochen sein wird.

---

Der Code als Kristallkugel

In diesem Paper schlagen Marcus Gallagher und Katherine Malan eine frische, fast schon magische Art vor, diese schwierigen Probleme zu betrachten. Anstatt einen Späher auszusenden, um die Landschaft zu vermessen, schlagen sie vor, einfach das „Rezept“ zu lesen, das der Computer verwendet, um das Problem zu erstellen.

Betrachten Sie ein Optimierungsproblem wie ein Level in einem Videospiel. Um das Level zu bauen, schreibt ein Programmierer Code. Einige Levels sind einfach: „Vorwärts bewegen, über eine Grube springen, die Münze einsammeln.“ Der Code dafür ist kurz und verwendet grundlegende Befehle. Andere Levels sind chaotisch: „Wenn der Himmel blau ist, multipliziere deine Geschwindigkeit mit der Anzahl der Sterne, dann subtrahiere die Quadratwurzel deiner Gesundheit, aber nur, wenn du einen Hut trägst.“ Der Code dafür ist lang, unordentlich und verwendet eine riesige Vielfalt an Befehlen.

Die große Idee der Autoren ist: Je unordentlicher und komplexer der Code ist, desto schwieriger ist es für einen Algorithmus, das Problem zu lösen.

Sie leihen sich zwei Werkzeuge aus der Softwaretechnik, um diese „Unordnung“ zu messen:

1. Halstead-Volumen: Stellen Sie sich vor, Sie zählen jedes einzelne Wort und jedes Symbol in einem Absatz. Wenn Sie eine kurze Geschichte mit einfachen Wörtern haben, ist die Zählung niedrig. Wenn Sie einen Roman mit komplexem Vokabular und langen Sätzen haben, ist die Zählung hoch. Dieses Maß zählt die „Operatoren“ (wie mathematische Symbole) und „Operanden“ (wie Zahlen und Variablen) im Code.
2. Shannon-Entropie: Dies ist ein wenig wie das Messen des Überraschungsfaktors. Wenn ein Absatz immer wieder dieselben fünf Wörter verwendet, ist er vorhersehbar (niedrige Entropie). Wenn er eine riesige Vielfalt an einzigartigen Wörtern in einer zufälligen Reihenfolge verwendet, ist er unvorhersehbar (hohe Entropie).

Das Experiment: Von einfachen Kreisen zu chaotischen Gipfeln

Um ihre Theorie zu testen, nahmen die Autoren einen berühmten Satz von 24 Testproblemen, die Wissenschaftler auf der ganzen Welt verwenden (bekannt als BBOB-Suite). Diese reichen von der „Sphere“-Funktion (einem perfekt glatten, runden Hügel, der leicht hinunterzurollen ist) bis zur „Lunacek bi-Rastrigin“-Funktion (einer zerklüfteten, felsigen Landschaft mit tausenden winzigen Gipfeln und Tälern).

Sie schrieben den Computercode für jedes dieser 24 Probleme auf und ließen ihre „Unordnungs“-Rechner darüber laufen. Die Ergebnisse waren genau das, was sie erhofft hatten:

• Die einfache, glatte Sphere-Funktion hatte die niedrigsten Komplexitätswerte.
• Die zerklüftete, schwierige Lunacek-Funktion hatte die höchsten Komplexitätswerte.
• Tatsächlich war die Lunacek-Funktion in ihrer Codestruktur etwa 9,3-mal komplexer als die Sphere-Funktion.

Sie testeten dies sogar an einer anderen Art von Problem: dem Training eines neuronalen Netzwerks (eines KI-Gehirns). Sie fanden heraus, dass der Code für ein Netzwerk, das eine „Tanh“-Aktivierungsfunktion verwendet, etwas komplexer war als der eines Netzwerks mit „ReLU“, und dies entsprach der Vorstellung, dass die Tanh-Version ein etwas schwierigeres Rätsel zum Lösen ist.

Die magische Verbindung: Code-Komplexität sagt die Leistung voraus

Die wahre Magie geschieht, wenn sie diese Code-Scores mit der tatsächlichen Leistung der verschiedenen Algorithmen vergleichen. Sie betrachteten die Daten von fünf verschiedenen „Roboter“-Algorithmen, die versuchten, diese 24 Probleme zu lösen.

Sie fanden ein klares Muster: Je komplexer der Code, desto schlechter performten die Roboter.

Es handelt sich um eine negative Beziehung. Wenn der Code einfach war (niedriges Halstead-Volumen), lösten die Roboter das Problem schnell und mühelos. Wenn der Code komplex war (hohes Halstead-Volumen), hatten die Roboter Schwierigkeiten, brauchten länger oder blieben stecken. Beispielsweise war in 5-dimensionalen Problemen der Zusammenhang zwischen Code-Komplexität und schlechter Leistung recht stark.

Die Autoren weisen jedoch vorsichtig darauf hin, dass dies keine perfekte Kristallkugel ist. Es gab einige „Ausreißer“-Probleme, bei denen der Code sehr komplex war, die Roboter aber nicht ganz so schlecht abschnitten, wie der Code vermuten ließ. Dies deutet darauf hin, dass die Code-Komplexität zwar ein großartiger Hinweis ist, aber nicht das einzige ist, was zählt.

Warum das wichtig ist

Die Schönheit dieses Ansatzes liegt darin, dass er unglaublich schnell ist und keine zusätzliche Arbeit erfordert. Traditionelle Methoden, um ein Problem zu verstehen, beinhalten oft, den Algorithmus tausendfach laufen zu lassen, nur um zu sehen, wie die Landschaft aussieht. Das ist so, als würde man einen Späher durch das gesamte Labyrinth laufen lassen, nur um eine Karte zu zeichnen.

Im Gegensatz dazu ist die Methode der Autoren wie das Betrachten des Bauplans des Labyrinths. Man kann die Komplexität des Codes in einem Sekundenbruchteil berechnen, ohne das Problem auch nur einmal auszuführen. Es spielt keine Rolle, wie groß das Problem ist oder wie viele Dimensionen es hat; es betrachtet lediglich die Struktur der Anweisungen.

Die Autoren schlagen vor, dass dieses Maß der „Code-Komplexität“ eine hilfreiche Ergänzung im Werkzeugkasten von Wissenschaftlern sein könnte, die Algorithmen entwerfen. Es ersetzt nicht die alten Wege, Probleme zu betrachten, aber es fügt eine neue, superschnelle Methode hinzu, um zu erraten, wie schwer ein Problem sein wird, noch bevor man überhaupt mit der Lösung beginnt. Es ist ein vielversprechender Schritt, um Computern zu helfen, das richtige Werkzeug für die Aufgabe zu wählen, indem sie einfach nur die Anweisungen lesen.