Wissenschaft beginnt mit Problemen

An den Anfang dieses Tutoriums wollen wir ein einfach verständliches, aber schwer zu lösendes Problem stellen. Dieses Problem hinterlässt uns mit der Forderung nach einem geeigneten Lösungsverfahren. Dazu wollen wir uns im Weiteren Ameisen auf der Futtersuche zuwenden und verstehen, wie es ihnen gelingt, ihr Futter auf schnellem Wege zu erreichen. Anschließend sollen die Ameisen als Vorbild für einen Computeralgorithmus herhalten, den Sie live bei der Arbeit sehen und mit dem Sie sich messen können. Zuletzt sollen in einem Ausblick weitere, praxisnähere Anwendungsbereiche für den Ameisenalgorithmus in Betrieben vorgestellt werden.

Das Handlungsreisenden-Problem

Beim Handlungsreisenden-Problem (engl. Travelling-Salesman-Problem oder kurz TSP) steht ein Vertreter vor der Aufgabe, eine vorgegebene Menge von Kunden in unterschiedlichen Städten jeweils genau einmal besuchen zu müssen. Diese Aufgabe möchte der Handlungsreisende möglichst auf der kürzesten Route erledigen und so wenig Kilometer wie möglich zurücklegen.

Die Problemanalyse

Lohnt dieses Problem einer weiteren Betrachtung oder ist es trivial zu lösen? Diese Frage muss eine Problemanalyse beantworten, in der die Anzahl der zu untersuchenden (möglichen) Routen bestimmt wird:

Bei fünf Städten hat man für den Ausgangspunkt der Route zunächst fünf Alternativen. Hat man diesen bestimmt, so verbleiben vier mögliche Orte für die erste Station der Reise usw. Es bestehen somit 5*4*3*2*1 oder 5! (sprich: Fünf Fakultät) oder 120 Möglichkeiten.

Betrachten wir ein 20-Städte-Problem. Kürzen wir die Anzahl der Städte mit n ab, so bestehen n! alternative Routen. Dies ergibt die stattliche Zahl von n! = 2 432 902 008 176 640 000 möglichen Routen.

Wenn wir nun einen Computer besäßen, der 1 000 000 Routen pro Sekunde berechnen kann, so müsste der Handlungsreisende immerhin ca. 77 140 Jahre warten, bis der Computer aus der Menge aller möglichen Routen die kürzeste bestimmt hätte.

Schlussfolgerungen für die Lösungssuche

Folgende Schlüsse können aus dieser ersten Problemanalyse für die Entwicklung eines Lösungsverfahrens gezogen werden:

Bei fünf Städten hat man für den Ausgangspunkt der Route zunächst fünf Alternativen. Hat man diesen bestimmt, so verbleiben vier mögliche Orte für die erste Station der Reise usw. Es bestehen somit 5*4*3*2*1 oder 5! (sprich: Fünf Fakultät) oder 120 Möglichkeiten.

Ein unsystematisches Probieren erscheint aussichtslos, da die Anzahl der möglichen Routen zu groß ist. Das Auffinden einer guten oder gar optimalen Rundreise wäre reiner Zufall.

Eine einfache Regel, die da lautet: Wähle immer den nächst gelegenen Ort (sog. Nearest-Neighbor-Heuristik) ist besser, kann aber auch keine wirklich guten Lösungen finden. Dies liegt an der Kurzsichtigkeit des Verfahrens. Während zu Beginn gute Teilrouten entstehen, sinken die Freiheitsgrade mit Fortschritt des Verfahrens. Zuletzt verbleiben die Städte, die weite Strecken erfordern, nun aber besucht werden müssen. Der gute Beginn wird damit zunichte gemacht.

Verbleibt die Erkenntnis, dass uns Besseres einfallen muss. Folgen wir doch dem Ratschlag Salomos und lassen uns von der Evolution leiten, die viele gute Lösungen hervorgebracht hat.