Das Problem des Handelsreisenden
Das Problem des Handelsreisenden (travelling salesman problem, TSP) ist einfach zu beschrieben: Ein Handelsreisender möchte eine Rundreise durch n verschiedene Städte machen. Dabei soll der Weg, den er zurücklegt, durch jede Stadt genau einmal führen und dabei möglichst kurz sein.
Leider erweist sich die Lösung dieses Problems als außerordentlich schwierig. Es handelt sich nämlich um ein sogenanntes NP-schwieriges Problem. Nach heutigem Wissensstand exisitert kein Lösungsalgorithmus der eine Optimallösung für ein NP-schwieriges Problemin vernünftiger Zeit bestimmen kann.
Sogenannte Lösungsheuristiken versuchen in verträglicher Zeit möglichst gute Lösung zu erzeugen. Zwei dieser Optimierungsalgorithmen werden im folgenden Java-Applet vorgestellt. Beide Algorithmen haben eins gemeinsam: Sie sind von Vorgängen in der Natur motiviert.
Ameisenalgorithmen (ACO)
Ameisenalgorithmen wurden dem Verhalten realer Ameisen bei der Futtersuche nachempfunden. Ameisen auf der Futtersuche scheiden Duftstoffe die sog. Pheromon aus, von denen andere Ameisen angezogen werden. Gibt es zwischen Nest und Futterquelle mehrere mögliche Wege, so wird mit der Zeit auf dem kürzesten Pfad die höchste Pheromonkonzentration einstellen, so dass dieser Weg von den Ameisen bevorzugt wird. Ameisenalgorithmen simuliert das Verhalten von Ameisen auf der Suche nach Futter um schwierige Optimierungsprobleme zu lösen.
Simulated Annealing
Beim "simulierten Abkühlen" (Simulated Annealing) handelt es sich um ein Optimierungsverfahren, dass an einen Abkühlprozess aus der Metallurgie angelehnt ist. Dabei wird ein erhitztes Metall langsam abgekühlt, so dass auf atomarer Ebene ein energie-idealer Zustand eintritt. Dabei nehmen zwischendurch die Atome immer wieder energiereichere Zustände ein.Simulated Annealing sucht in der Nachbarschaft einer vorhandenen Lösung nach besseren Lösungen, akzeptiert mit einer gewissen, allmählich abnehmenden Wahrscheinlichkeit aber auch schlechtere Lösungen, um so aus lokalen 'Tälern' herauszufinden.
Das Applet
Das folgende Applet wurde im Rahmen eines Projektseminars im Wintersemester 2002/2003 von Tobias Oetzel erstellt.
Der Sourcode des Applets ist unter der GPL veröffentlicht. Er steht zusammen mit der Seminarausarbeitung hier zum download bereit.