Institut für Mathematik
Arbeitsgruppe Stochastische Optimierung
Das Applet
Für den Anfang einfach mal auf Start drücken! Wenn die Optimierung fertig ist, kann mit dem Algorithmus "Simulated Annealing" das Ergebnis ggf. noch einmal nachgebessert werden.
Das Applet wurde im Rahmen eines Projektseminars im Wintersemester 2002/2003 von Tobias Oetzel erstellt.
Anleitung
Die Oberfläche teilt sich in 3 große Bereiche:Links ist eine Liste mit Optionen, die zur Steuerung der Optimierung dienen.
Das große Fenster rechts zeigt die Städte. Solange die Optimierung nicht läuft, wird die bisher beste Lösung angezeigt und es können mit der Maus Städte hinzugefügt/weggenommen werden.
Während der Optimierung kann hier der Optimierungsverlauf beobachtet werden: Bei der Ameisenoptimierung wird die (relative) Pheromonintensität angegeben, beim Simulated Annealing die zuletzt angenommene Lösung. Alternativ kann hier auch die beste bisher gefundene Rundreise angezeigt werden.
Im Informationsfenster rechts unten sieht man Daten und Statistiken über den Stand der Optimierung.
Optionen
- Algorithmen: Hier stehen die beiden Algorithmen Ant Colonisation Optimization und Simulated Annealing zur Verfügung.
- Runden: Mit dieser Option kann beim ACO die Anzahl der Runden eingestellt werden, die der Algorithmus laufen soll.
- Bedeutung der Pheromone: Die eingestellte Zahl geht als Exponent in die Berechnung der Wahrscheinlichkeit ein. Je größer die Zahl ist, umso mehr orientieren sich die Ameisen an den Pheromonen
- Bedeutung der Entfernung: Auch diese Zahl geht exponentiell ein. Sie gibt an, inwieweit sich die Ameisen an der Entfernung orientieren. Durch den exponentiellen Charakter gehen tatsächlich die Zahlen (Bedeutung der Pheromine und der Entfernung) und nicht nur der Quotient der Zahlen in die Berechnung ein.
- Pheromon-Verdunstungsfaktor: Die Intensität der Pheromonspur wird jede Runde mit dieser Zahl multipliziert. Sie sollte zwischen 0 und 1 liegen - zu experimentellen Zwecken sind aber auch andere Einträge möglich.
- Nachbarschaft: Hier stehen die beiden Nachbarschaften Transposition und 2-opt zur Verfügung. Bei der Transposition werden zufällig zwei Städte vertauscht - dadurch ändern sich vier Kanten im Graphen. Beim 2-opt werden zunächst zwei Kanten entfernt und die Rundreise dann durch zwei andere Kanten wieder geschlossen.
- Anfangstemperatur: Die Anfangstemperatur für den Abkühlvorgang.
- Kühlfaktor: Nach jedem Durchlauf der inneren Schleife wird die Temperatur mit dem angegebenen Kühlfaktor multipliziert. Sinkt dadurch die Temperatur auf unter 0.01, so bricht der Algorithmus ab.
- Innere Wiederholungen: Die Temperatur wird nicht nach jedem Schritt verändert, sondern erst nach der angegebenen Anzahl von Wiederholungen.
- Zufällige Städte erzeugen: Ein Klick auf die Checkbox erzeugt die angegebene Anzahl Städte (maximal 2700).
- bisher beste Lösung zeigen: Während des Laufs wird im Anzeige-Fenster normalerweise nicht die bisher beste Lösung angezeigt, sondern algorithmenspezifische Informationen (d.h. die Pheromonintensität bzw. die zuletzt akzeptierte Lösung). Ist diese Box angekreuzt, wird auch während des Laufs die beste bisher gefundene Rundreise gezeigt.
- Pause zwischen Schritten: Mit diesem Schieberegler kann man eine Pause zwischen zwei Schritten/Runden einstellen. Die Stellung ganz links bedeutet keine Pause, die Stellung ganz rechts entspricht zwei Sekunden.
- Start/Stopp: Zum Starten/Stoppen der Optimierung. Start ist nur möglich, falls mindestens zwei Städte in der Anzeige zu sehen sind.
- Reset: Stoppt die eventuell laufende Optimierung und setzt die Städte wieder auf den Anfangszustand mit einer neuen, zufälligen Lösung.
Anzeige
- linke Maustaste: Läuft gerade keine Optimierung, so kann durch Drücken der Linken Maustaste eine Stadt gesetzt/entfernt werden. Wird dies getan, so wird beim nächsten Start der Optimierung eine neue Startlösung erzeugt. So kann - durch Setzen und Entfernen einer Stadt - auch Simulated Annealing dazu gebracht werden, mit einer zufälligen Lösung zu starten.
- rechte Maustaste: Durch Drücken der rechten Maustaste wird das Anzeigefeld gelöscht.
Information
- Schritte/Runden: Hier wird die Anzahl der Runden bzw. Schritte angezeigt.
- Laufzeit: Angabe, wie viel Zeit die aktuelle Optimierung bisher benötigt hat.
- Temperatur: (nur Simulated Annealing) Gibt die aktuelle Temperatur an.
- Anfangsdistanz: Länge der Distanz der aktuellen Tour bei betätigen des Start-Knopfes. Achtung: Wurden manuelle Städte gesetzt oder gelöscht, wird eine neue, zufällige Tour erzeugt.
- Beste Distanz: Die Länge der bisher kürzesten Rundreise.
- Verbesserung %: Angabe, um wieviel Prozent die bisher beste Tour die Anfangstour verbessert hat.
Download
Der Sourcode ist unter der GPL veröffentlicht. Er steht zusammen mit der Seminarausarbeitung hier zum download bereit.