Rundreise mit Darwin

Eine Mathematikerin der TU Berlin analysiert erstmals einen erfolgreich evolutionären Algorithmus für das Handlungsreisenden-Problem.

Vielleicht wäre die Weltliteratur ärmer, wenn der griechische Sagenheld Odysseus Menschen wie Martin Grötschel oder Madeleine Theile an Bord gehabt hätte. Auf seiner zwanzig Jahre währenden Odyssee verschlug es Odysseus an 16 Orte. Dabei legte er in Luftlinie 9913 Kilometer zurück, wie Grötschel, Mathematiker am Berliner Konrad-Zuse-Institut, berechnet hat. Die kürzeste Strecke wäre allerdings, so Grötschel, nur 6859 Kilometer lang gewesen.

Mit einer solchen Aufgabe, die einer naheliegenderen Anwendung wegen Handlungsreisenden-Problem genannt wurde, tun sich selbst heutige Computer schwer. Schon die 16 Orte der Odyssee ergeben 653837184000 mögliche Routen. Wie schnell ein Rechenverfahren eine optimale Lösung findet, hängt nach bisherigen Erkenntnissen exponentiell davon ab, wie viele Städte im Spiel sind. Wenn ein Computer heutiger Bauart die Optimierung einer Rundreise durch 16 Städte in fünf Minuten bewältigen könnte, würde ein hundert Mal so schneller Superrechner in derselben Zeit vielleicht nur zwanzig Städte schaffen. "NP-schwer" ("NP" steht für "nicht-deterministisch polynomiell") heißt diese Klasse von Problemen im Mathematiker-Jargon. Die Relevanz der Aufgabe reicht weit über die Routenplanung des namensgebenden Handlungsreisenden hinaus: Wenn etwa ein Roboterarm Lötpunkte auf einer Leiterbahn platziert, sollte auch dessen Weg möglichst kurz sein.

Die Berliner Mathematikerin Madeleine Theile, Doktorandin an der TU Berlin, ist dem Handlungsreisenden-Problem nun mit einem ganz neuen Ansatz zu Leibe gerückt: Sie verwendete einen sogenannten evolutionären Algorithmus. Mit erstaunlichen Resultaten, wie Theile unlängst auf einer Tagung in Tübingen vor etwa 200 Wissenschaftlern berichten konnte. Mit ihrem Verfahren errechnete sie eine optimale Lösung für 20 Städte. Das würde bei Experten für das Handlungsreisenden-Problem zwar nur ein müdes Gähnen auslösen – der Weltrekord, gehalten von Professor William Cook von der Universität Georgia Tech in Atlanta, liegt bei 85900 Orten. Doch die wahre Relevanz von Theiles Forschung liegt woanders: Es bringt nach Ansicht ihres Doktorvaters Martin Skutella die theoretische Forschung rund um die evolutionären Algorithmen nach vorn: "Mit evolutionären Methoden wird schon seit den sechziger Jahren gearbeitet, doch die Erforschung ihrer Funktionsweise ist erst etwas mehr als ein Jahrzehnt alt", erläutert Skutella. "Bis heute weiß keiner, wie ein Problem geartet sein muss, damit man einen evolutionären Algorithmus erfolgreich darauf ansetzen kann."

Bisher werden naturinspirierte Verfahren vor allem bei Praxisproblemen eingesetzt, deren Struktur sich nur schwer durchdringen lässt. "Es gibt Ingenieurprobleme, bei denen Hunderte Faktoren den Produktionsprozess beeinflussen, die man unmöglich alle in ein Modell einbeziehen könnte", erklärt Skutella. In der industriellen Bäckerei etwa wird die Qualität eines Teiges nicht nur von den Zutaten, sondern auch von den Einstellungen der Knetmaschine und so unwägbaren Bedingungen wie Luftfeuchtigkeit und Temperatur in der Fertigungshalle beeinflusst.

Bei evolutionären Algorithmen wird dem Computer kein bestimmter Rechenweg vorgegeben, mit dem er stumpf sämtliche Kombinationen durchdekliniert. Stattdessen bildet sich die optimale Lösung für eine vorgegebene Aufgabe erst durch Versuch und Irrtum heraus. Wie in der natürlichen Evolution spielen dabei Mutation, Rekombination und Selektion die treibende Rolle: Zunächst werden zufällig erzeugte Lösungswege auf ein Problem losgelassen. Anschließend wird überprüft, welche Lösungen am besten sind. Untaugliche werden gelöscht, erfolgreiche kommen eine Generation weiter, können Teilinformationen mit anderen Kandidaten austauschen oder werden nach dem Zufallsprinzip geringfügig geändert. Die Menge aller Lösungskandidaten zu einem Zeitpunkt in dem Verfahren nennt man Population.

Das Problem dabei: Das Verfahren bleibt für den Anwender eine Blackbox. Irgendwann spuckt sie eine mehr oder minder brauchbare Lösung aus, aber niemand kann sagen, ob und warum sie wirklich die beste von allen denkbaren Möglichkeiten ist. Madeleine Theile beschreibt es so: Ein evolutionärer Algorithmus funktioniere wie "ein Wanderer, den man in eine Berglandschaft schickt, um die höchste Erhebung zu suchen", so die Mathematikerin. "Er wird auf den nächstbesten Berg klettern und sich umsehen. Wenn er von dort einen noch höheren entdeckt, klettert er wieder runter und geht den höheren hinauf." So komme man immer zu einer lokal optimalen Lösung. "Aber bei der Suche nach dem Optimum kann man auch stecken bleiben, wenn von dem Berg, auf dem ich stehe, kein höherer zu sehen ist – obwohl es ihn vielleicht gibt."

Praktiker nehmen solche Schwächen in Kauf, solange die naturinspirierten Rechenverfahren ihnen wenigstens schrittweise Fortschritte bringen. Mathematiker hingegen wollen die undurchschaubaren Verfahren verstehen, um sie besser nutzbar zu machen. "Wenn ein Algorithmus nur auf ein spezifisches Problem geeicht ist, kann er schon beim nächsten wieder scheitern", sagt Theile.

Die Mathematikerin analysierte nun das gut verstandene Handlungsreisenden-Problem, um nachzuvollziehen, durch welchen Lösungsraum ihr Algorithmus wandert und welche Gipfel er besteigt. An ihrem Rechenverfahren feilte sie so lange herum, bis sie garantieren konnte, dass der Wanderer während seiner Tour irgendwann dem höchsten Berg nahe kommt und ihn auch besteigt. Das Ganze funktioniert so: Theiles Population besteht aus einer Menge von Städtetouren. In jedem Evolutionsschritt wird eine Tour – ein Individuum – zufällig gezogen und mutiert, indem sie an mehreren wiederum zufällig gewählten Stellen aufgetrennt und neu zusammengefügt wird. Im folgenden Selektionsprozess wird die mutierte Lösung mit einem zufällig ausgewählten anderen Individuum aus der Population verglichen. Wenn die Mutation besser, das heißt die Gesamtlänge der Tour kürzer ist, ersetzt sie das Vergleichsindividuum.

Um zu garantieren, dass man sich irgendwann dem Optimum nähert, sind zwei Kniffe nötig: Erstens muss man mit der richtigen Populationsgröße anfangen, das sind nach Theiles Untersuchung bei n Städten etwa n mal zwei hoch n Individuen. Zweitens ist es entscheidend, im Mutationsprozess zu kontrollieren, an wie vielen Stellen eine Tour aufgetrennt und neu organisiert wird. Diese Erkenntnis ist durch Praxistests allein nicht zu gewinnen, sondern wurde von Theile mathematisch bewiesen. Durch diesen Beweis kann sie nun erstmals prognostizieren, wie viele Rechenschritte ein evolutionärer Algorithmus braucht, um sich dem Optimum zu nähern.

Ziel von Theiles Forschung ist es, Anwendern und Theoretikern – unabhängig vom Handlungsreisenden-Problem – ein Mittel in die Hand zu geben, mit dem sie sondieren können, in welchem Bereich evolutionäre Algorithmen überhaupt sinnvoll einsetzbar sind. In einem nächsten Schritt will Theile nun testen, ob sie die Leistungsfähigkeit ihres Algorithmus' durch Kreuzungen ihrer Individuen verbessern kann. Bislang kommt das Verfahren nur mit Mutation und Selektion aus. Auch andere kombinatorische Optimierungsprobleme hat sie bereits getestet. Bei Varianten des Problems der kürzesten Wege – das zum Beispiel bei Evakuierungssimulationen vorkommt – sehen evolutionäre Algorithmen ihren Angaben zufolge vielversprechend aus.

Weil es noch etwas dauern wird, bis ihre Resultate den Weg in die Praxis finden, stoßen Theiles Arbeiten im anwendungsorientierten Teil der Fachwelt noch auf Unverständnis. Sie hofft dennoch, "eines Tages an den Punkt zu kommen, wo ich mit meinen theoretischen Erkenntnissen einem Praktiker einen Tipp an die Hand geben kann". Ihr Doktorvater Skutella ist ebenfalls der Meinung, dass die dauerhafte praktische Nutzbarkeit natur-analoger Verfahren eine gründliche theoretische Analyse erfordert – auch wenn es viele Beispiele für Praxisanwendungen gebe. In der Gemeinde der evolutionären Programmierer werde zu wenig nach links und rechts geguckt: "Viele sind sich manchmal gar nicht bewusst, dass es für ihr Problem längst bessere Methoden gibt als evolutionäre Algorithmen." Skutella wünscht sich von allzu evolutionsbegeisterten Kollegen mehr Problembewusstsein: "Für Leute, die nur Hämmer benutzen, sieht alles wie ein Nagel aus." (bsc)