Hamburg 2001 – wissenschaftliches Programm

Bereiche | Tage | Auswahl | Suche | Downloads | Hilfe

DY: Dynamik und Statistische Physik

DY 13: Statistische Physik (Allgemein) II

DY 13.10: Vortrag

Montag, 26. März 2001, 12:45–13:00, S 7

Kombination von Search Space Smoothing mit einem Threshold — •Johannes Schneider¹, Martin Ransberger² und Ingo Morgenstern² — ¹Physik-Institut, Universität Zürich-Irchel, Winterthurerstr. 190, CH-8057 Zürich — ²Fakultät für Physik, Universität Regensburg, D-93040 Regensburg

Bei Simulated Annealing und Threshold Accepting wird die Temperatur bzw. der Threshold, mit dessen Hilfe der Monte Carlo-Wanderer Barrieren in der Energielandschaft überwinden kann, schrittweise abgesenkt, bis schließlich das System in einer (quasi-)optimalen Konfiguration einfriert. Im Gegensatz dazu versucht Search Space Smoothing, ähnlich einem Katalysator, die Energielandschaft so zu glätten, daß Barrieren zwischen den einzelnen lokalen Optima abgebaut werden oder sogar gänzlich verschwinden. Mittels eines Parameters wird diese Glättung schrittweise zurückgeführt, bis man am Schluß wieder die Originallandschaft erhält. Üblicherweise wird der Greedy, der nur Verbesserungen akzeptiert, in Kombination mit Search Space Smoothing verwendet. In diesem Beitrag stellen wir einen neuen Ansatz vor, bei dem die Akzeptanzregel des Threshold Accepting verwendet wird, wobei allerdings der Threshold während der Optimierung auf einem kleinen Wert konstant gehalten wird. Mit Hilfe dieses Ansatzes lassen sich optimale Lösungen für verschiedene Instanzen des Problems des Handlungsreisenden und neue Weltrekorde für Tourenplanungsprobleme mit Zeitfenstern aus der Solomon-Library finden.