Einführung
Es soll eine möglichst optimale Route durch alle Städte gefunden werden. Es wird mit einer zufälligen Route gestartet und in jedem Schritt werden zufällig zwei Kanten ausgewählt. Jetzt werden die Verbindungen zwischen den vier Knoten übers Kreuz getauscht und überprüft, ob diese Route nicht länger als die aktuelle Route plus die Temperatur ist. Man nimmt also eine maximal um die aktuelle Temperatur schlechtere Route in Kauf.
Während der Simulation nimmt die Temperatur kontinuierlich ab und die Route pendelt sich ein. In der rechten Hälfte der Simulation wird die bis anhin optimalste Route dargestellt.
Bedienung
- Taste 'R: Restart, startet die Berechnung mit den gleichen Städten neu.
- Taste 'N': Neustart, es wird eine neue Serie von Städten generiert.
Variation der Route
Beim Variieren der Route bei zwei zufälligen Kanten (Verbindungen): die Kanten werden übers Kreuz getauscht und der mittlere Teil der Route wird in umgekehrter Richtung durchlaufen. Dieses Vorgehen wird 2-OPT-Heuristik genannt. Aus der Dreiecksungleichung kann gefolgert werden, dass wenn zwei sich kreuzende Kanten aufgehoben werden, die Gesamtlänge der beiden neuen Kanten kleiner als jene der beiden bisherigen Kanten ist.
Problem des Handlungsreisenden
Die optimale Route durch eine Anzahl von Orten zu finden, ist als Problem des Handlungsreisenden bekannt (Travelling Salesman Problem = TSP). Das TSP ist ein schwieriges Problem, da der Aufwand um alle möglichen Routen zu berechnen mit der Anzahl der Städte immens anwächst. Die folgende Simulation zeigt diesen so genannten Brute-Force Ansatz anschaulich. Am unteren Rand der Simulation ist die systematische Variation der Route ersichtlich und die geschätzte Laufzeit angezeigt: City Trip Interactive aus dem "Computer Science Field Guide".
Komplexität des TSP
Wie aufwändig ist das TSP? Die untenstehende Skizze mit vier Städten zeigt, dass bereits sechs Routen möglich sind.
Kommt ein fünfter Knoten hinzu, so wird er mit 5-1 = 4 Kanten mit dem bisherigen Netzwerk verbunden. Es resultieren also 4-mal mehr möglich Routen als bisher – bei 5 Knoten bereits 6*4=24.
Formal ausgedrückt sind Fakultät von n minus 1 Routen möglich: (n-1)!.
Der Aufwand wächst faktoriell und ist bereits ab einer mittleren Anzahl Städte nicht mehr in vernünftiger Zeit lösbar. Sicherlich haben Sie in der Abbildung festgestellt, dass die drei unteren Touren nur Umkehrungen der oberen drei Routen sind. Trotzdem wächst der Aufwand immer noch faktoriell mit 0.5*(n-1)!
Aufwand Tabelle
| # Städte | mögliche Rundreisen 0.5 *(n-1)! | mögliche Rundreisen 0.5 *(n-1)! |
|---|---|---|
| 3 | 1 | - |
| 4 | 3 | - |
| 5 | 12 | - |
| 6 | 60 | - |
| 7 | 360 | - |
| 8 | 2'520 | - |
| 9 | 20'160 | - |
| 10 | 181'440 | - |
| 15 | 43'589'145'600 | 4.36E+10 |
| 20 | 60'822'550'204'416'000 | 6.08E+16 |
| 25 | 310'224'200'866'620'000'000'000 | 3.10E+23 |
| 30 | 4'420'880'996'869'850'000'000'000'000'000 | 4.42E+30 |
| 35 | 147'616'399'519'802'000'000'000'000'000'000'000'000 | 1.48E+38 |
| 40 | 10'198'941'040'598'700'000'000'000'000'000'000'000'000'000'000 | 1.02E+46 |
| 45 | 1'329'135'787'394'220'000'000'000'000'000'000'000'000'000'000'000'000'000 | 1.33E+54 |
| 50 | 304'140'932'017'134'000'000'000'000'000'000'000'000'000'000'000'000'000'000'000'000 | 3.04E+62 |
Grundidee "Simulated Annealing"
Die Idee ein langsames Abkühlen zu simulieren (simulated Annealing) kennt man z.B. aus der Stahlindustrie. Durch kontrolliertes Abkühlen und erneutes Temperieren entsteht Stahl mit besonderen Eigenschaften.
Bei der Lösung des TSP wird Simulated Annealing als schnelle und effektive Heuristik eingesetzt. Sie liefert zwar nicht zwingend die optimalste Route, aber eine sehr gute Näherung an die optimale Route und v.a. innert nützlicher Frist.