Der Staubsaugervertreter und die Sintflut: kombinatorische Optimierung

Christoph Pöppe

Manchmal bin ich richtig froh, dass die Mathematik so schön abstrakt ist. Deswegen kann ich nämlich – zum Beispiel – gänzlich ohne schlechtes Gewissen über das Problem des Handlungsreisenden (travelling salesman problem, TSP) reden.

Und das, obgleich das Problem seinen Ursprung in einer Sumpfblüte der kapitalistischen Wirtschaftsweise hat. Natürlich hat es keinen gesellschaftlichen Nutzen, wenn der „travelling salesman“ von Dorf zu Dorf zieht, um ahnungslosen Hausfrauen überteuerte Staubsauger anzudrehen. Und dass die Aufgabe neuerdings gendergerecht „travelling salesperson problem“ heißt, macht die Sache nicht besser.

Der arme Staubsaugerverkäufer soll eine vorgegebene Menge von Stationen abklappern; es geht darum, die Reihenfolge so zu wählen, dass die Gesamtzahl der zurückzulegenden Kilometer minimal wird. Dieses Bestreben nach Kostensparen ist zwar vor allem in großen Firmen verbreitet, aber nicht von Natur aus kapitalistisch. Ich überlege mir auch, in welcher Reihenfolge ich das Geschirr aus der Spülmaschine in die Küchenschränke einräume, um möglichst schnell fertig zu werden.

Und um noch eine Abstraktionsstufe draufzusetzen: Das TSP ist nur Stellvertreter für eine ganze Klasse von Problemen, bei denen es darum geht, endlich viele Dinge in eine geeignete Reihenfolge zu bringen, sie unter gewissen Bedingungen auf mehrere Teilmengen aufzuteilen oder Ähnliches: kombinatorische Optimierungsprobleme. Es stellt sich heraus, dass Lösungsverfahren sich gut von einem Problem auf ein anderes derselben Klasse übertragen lassen.

Wie findet nun unser Klinkenputzer den kürzesten Weg über die Dörfer? Gesucht ist das Minimum einer Funktion; aber die ist nicht, wie beim verallgemeinerten Bergwandern, auf irgendeinem Vektorraum mit reellen Koordinaten definiert, sondern auf der Menge aller denkbaren Reihenfolgen der Städte oder, was auf dasselbe hinausläuft, die Menge aller Permutationen der natürlichen Zahlen von 1 bis n, wo n die Anzahl der Dörfer ist. Das klingt erst einmal angenehm, denn diese Menge ist endlich. Also könnte man deren Elemente, sprich sämtliche Touren, durchprobieren, zu jeder Tour die Länge berechnen, und unter diesen die kürzeste zu finden ist ein Kinderspiel.

Die Freude verfliegt rasch, wenn man sich die Anzahl der Reihenfolgen anschaut. Die ist nämlich gleich n! (n-Fakultät), also das Produkt aller natürlichen Zahlen von 1 bis n, und diese Zahl gerät bereits für mittelgroße Werte von n in astronomische Größenordnungen. Erschöpfendes Durchprobieren ist keine Option.

Im Gegensatz dazu muss man bei den Bergwander-Problemen zwar im Prinzip über unendlich viele potenzielle Lösungen nachdenken; aber man hat wegen der Differenzierbarkeit unserer Zielfunktion eine gewisse Struktur. Das Gebirge ist „glatt“, und das heißt insbesondere: Wenn der Wanderer von seinem Standpunkt ein bisschen abweicht, passiert nicht allzu viel, und wenn er annähernd im Minimum sitzt, erst recht nicht. Deswegen genügt es, die Lösung auf ein paar Stellen hinterm Komma zu kennen.

Hat die Menge aller Touren denn so etwas wie eine Struktur? Irgendwie schon, aber sie ist nicht so leicht zu erfassen. Man kann zwei Touren als benachbart ansehen, wenn sie sich wenig unterscheiden; zum Beispiel wenn eine Tour die Dörfer A und B (unmittelbar hintereinander) in der Reihenfolge AB anfährt, die andere in der Reihenfolge BA und beide ansonsten denselben Weg nehmen.

 

Oder es gibt vier benachbarte Dörfer A, B, C und D. Wenn die eine Tour erst AB läuft und irgendwann später CD, und die andere läuft erst AD, dann CB und im Übrigen denselben Weg wie die erste, bloß zum Teil in Gegenrichtung, dann kann man diese Touren benachbart nennen, auch wenn die Nummernfolgen das nicht unbedingt nahelegen.

An dieser Stelle kommt unser gedachter Bergwanderer wieder ins Spiel. Jede Tour ist ein Punkt in einer abstrakten Landschaft. Dessen Höhe über dem Meeresspiegel ist die Länge der Tour. Der Wanderer steht auf einem solchen Punkt; dann sind ihm alle im obigen Sinne benachbarten Punkte mit einem Schritt zugänglich. Er probiert sie alle durch und geht dann zu dem, der ihn am weitesten abwärts bringt. (Mit weniger Wandererromantik ausgedrückt: Das Minimierungsprogramm hat eine bestimmte Tour im Speicher, es berechnet die Länge aller benachbarten Touren und ersetzt dann die aktuelle Tour durch diejenige benachbarte Tour, welche die kürzeste Länge aufweist.) Dann wiederholt er das Spiel: alle Nachbarn anschauen, zu dem gehen, der am weitesten abwärts führt, und so weiter, bis man in einem lokalen Minimum landet. An dieser Stelle macht jede kleine Änderung die aktuelle Tour nur schlechter.

So oder so ähnlich war unser Wanderer im differenzierbaren Gebirge auch zum Ziel gekommen. Nur: Die abstrakte Landschaft aller Rundtouren ist nicht so freundlich wie die Alpen, sondern viel zerklüfteter. Mit dem beschriebenen Verfahren landet man zwar bei einer Tour, die durch kleine Änderungen nicht mehr zu verbessern ist, aber gleichwohl beliebig schlecht sein kann. Auf dem Weg zu besseren Lösungen muss man wohl oder übel über den Berg.

Übrigens: So etwas kann einem auch in einem differenzierbaren Gebirge passieren – so etwas wie ein idyllischer Bergsee, der aber eben viel zu hoch liegt. Entsprechend muss man auch in diesem Fall darauf vorbereitet sein, vorübergehend bergauf zu wandern. Nur sind kombinatorische Optimierungsprobleme sozusagen von Natur aus reicher an lokalen Minima, schon weil die Nachbarschaftsbeziehungen komplizierter sind.

An dieser Stelle hat unser Wanderer ein ernsthaftes Problem. Er sitzt in einem lokalen Minimum, kann vielleicht aus dessen Höhe erschließen, dass da noch ziemlich viel Luft nach unten ist, muss also noch einmal den Berg hoch – aber welchen unter den zahlreichen Bergen, die zur Auswahl stehen? Und wann soll er es gut sein lassen mit dem Aufstieg, wieder talwärts wandern und hoffen, dass er diesmal ein besseres Tal erwischt hat?

Die Antwort ist ebenso einfach wie ernüchternd. Hast du keine weiteren Informationen über die Struktur der Landschaft, dann kannst du deinen nächsten Schritt auch auswürfeln. Und genau das passiert auch: Man lässt den Zufall entscheiden. Der Wanderer tobt also irgendwie wild in der Gegend herum; nur wie will er damit zum Ziel kommen?

An dieser Stelle lernen die Optimierer von den Stahlkochern. Die „tempern“ nämlich ihren Werkstoff, das heißt, sie unterziehen ihn einem Wechselbad aus Erhitzen und Abkühlenlassen. Die Eisenatome in der Schmelze tun sich beim Abkühlen zu kleinen Kristallen zusammen, aber sehr ungeordnet. Wenn man die so entstandene Mikrokristallstruktur durch Erhitzen wieder ein bisschen aufbricht, findet das nächste Erstarren etwas geordneter statt, und durch Wiederholen dieser Prozedur gewinnt man am Ende ein Material hoher Qualität.

Das auf das Optimieren übertragen heißt simuliertes Tempern („simulated annealing“) und geht so: In der heißen Phase, das heißt wenn sich die echten Moleküle heftig bewegen, genehmigt sich der Wanderer entsprechend hohe Sprünge nach oben. Dann kommt die Abkühlung, das heißt, die Höhe der Schritte in Aufwärtsrichtung wird immer stärker beschränkt, bis auf null, womit sich der Wanderer wieder im Standardmodus befindet.

Oder man folgt einem ganz anderen Prinzip: Nicht die Höhe der Aufwärtssprünge wird begrenzt, sondern die absolute Höhe des Sprungziels. Ein Sprung wird also nicht verboten, weil er 100 Meter in die Höhe geht, sondern weil die neue Position höher als, sagen wir, 4100 Meter wäre. Diese Maximalhöhe wird im Laufe des wilden Herumspringens allmählich abgesenkt, so dass am Ende dem Wanderer nichts anderes übrigbleibt, als abwärts zu gehen.

Die Erfinder Gunter Dueck, Tobias Scheuer und Hans-Martin Wallmeier haben ihr Verfahren „Sintflut-Algorithmus“ genannt. Die Idee hinter dem Namen ist: Man stellt die ganze Landschaft auf den Kopf (das ist ganz einfach: Minuszeichen vor die Zielfunktion) und sucht entsprechend nicht nach dem tiefsten Loch, sondern nach dem höchsten Gipfel. Während der Wanderer herumtobt, wird das Gebirge allmählich geflutet, und der Wanderer darf überallhin, nur nicht ins Wasser.

Wie kann das sein, dass diese merkwürdigen Rezepte überhaupt funktionieren? Mathematisch zu beweisen gibt es da nichts, im Gegenteil: Zu jedem dieser Verfahren kann man sich eine Zielfunktion ausdenken, an der es jämmerlich scheitert. Und eine Garantie, dass der Punkt, an dem der Wanderer schließlich stehenbleibt, das absolute Minimum (die kürzeste aller denkbaren Touren) ist, gibt es auch nicht. Nur die Erfahrung zeigt, dass das Verfahren bei den meisten Versuchen fast-optimale Lösungen findet.

Eine Erklärung unterhalb des Beweisniveaus geht ungefähr so: Die Zielfunktion des travelling salesman problem ist eben nicht irgendeine wilde Funktion, sondern hat eine gewisse Struktur. Die hat zur Folge, dass es rund um das absolute Optimum eine ganze Menge fast-optimaler Lösungen gibt. Das tiefste aller Täler ist also ziemlich breit, auch wenn einzelne Gipfel im Tal die Sache sehr unübersichtlich machen. Also besteht eine gewisse Wahrscheinlichkeit, dass der Wanderer rein durch Zufall in den Einzugsbereich dieses Tals gerät, und wenn man es geschickt anstellt, springt er da nicht durch Zufall wieder heraus. Oder die fast-optimalen Punkte liegen zwar nicht zusammen, aber ihre Einzugsbereiche sind insgesamt so groß, dass man mit ziemlicher Sicherheit durch Zufall in einen von ihnen hineinfällt.

Was ist nun mit den praktischen Anwendungen dieser Lösungsverfahren? Die echten Handlungsreisenden sind ja aus der Mode gekommen; inzwischen werden die Leute mit viel raffinierteren Methoden über den Tisch gezogen. Immerhin kann an die Stelle der „travelling salesperson“ eine automatisch gesteuerte Bohrmaschine treten, die ganz viele Löcher in Leiterplatten für elektronische Geräte macht.

Unter den Leuten, die Verfahren für kombinatorische Optimierungsprobleme entwickeln, gibt es einen Wettbewerb um das beste Verfahren und dementsprechend immer wieder ein Problem, an dem die Optimierer ihre Messer wetzen können. Anfangs der 1990er Jahre war eine solche Aufgabe „Finde den kürzesten Weg durch alle Gemeinden der fünf neuen Bundesländer“. Dabei war jedes Dorf und jede Stadt durch einen geeignet bestimmten Mittelpunkt ersetzt worden, und alle Entfernungen wurden in Luftlinie berechnet. Einen besonderen Reiz erhielt diese Aufgabe dadurch, dass es in der DDR keine kommunale Neuordnung gegeben hatte; es gab also sehr viele sehr kleine Dörfer. Gunter Dueck und Kollegen haben damals eine gute Näherungslösung (rechts) gefunden; sie sieht recht eindrucksvoll aus.

Aber praktische Anwendung? Wir können sicher sein, dass kein Mensch diese Tour je gefahren ist.

The post Der Staubsaugervertreter und die Sintflut: kombinatorische Optimierung originally appeared on the HLFF SciLogs blog.