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 ...
Neugierig geworden? Der vollständige Artikel erschien in der Print-Ausgabe 07/2009 von Technology Review und steht als kostenpflichtiges pdf im Heise Kiosk zum Download bereit.
Permalink: http://heise.de/-276549
Version zum Drucken | Audio | Per E-Mail versenden | Newsletter
