Das Simulated Annealing (SA) ist ein randomisiertes Verfahren, das in
vielen praktischen Fällen gute Näherungslösungen für kombinatorische
Aufgabenstellungen liefert. Diese Technik wurde Anfang der 80er
Jahre entwickelt und basiert auf der Analogie zwischen dem Abkühlen
geschmolzener Körper und dem Lösen großer Optimierungsprobleme. Hier
wie dort ist der Erfolg des Prozesses stark abhängig von der
geschickten Wahl eines Kontrollparameters, der ,,Temperatur``. Um
möglichst gute ,,Kühlpläne`` für das Simulated Annealing erstellen zu
können, ist die Untersuchung des Konvergenzverhaltens des Verfahrens
eine notwendige Voraussetzung. Dieser Aufgabe haben wir uns im Rahmen
eines von der Deutschen Forschungsgemeinschaft (DFG) geförderten
Projektes gewidmet. Die Eignung des Simulated Annealing für
praktische Anwendungen konnte am Beispiel der Erstellung von
kostengünstigen Flugplänen (Abschnitt 
) unter Beweis
gestellt werden.
Beim Simulated Annealing wird mit einer zulässigen Lösung des kombinatorischen Optimierungsproblems gestartet und eine zufällig gewählte benachbarte Lösung erzeugt. Hat diese einen besseren Zielfunktionswert, geht man zu ihr über und iteriert. Andernfalls akzeptiert man die neue Lösung nur mit einer gewissen Wahrscheinlichkeit. Diese Wahrscheinlichkeit nimmt mit steigender Iterationszahl ab (Annealing). Dieses Akzeptieren auch von schlechteren Zuständen dient dazu, nicht in lokalen Optima zu verharren, sondern zu einem globalen Optimum zu gelangen.
Das sich für Simulated Annealing in natürlicher Weise anbietende mathematische Modell ist eine inhomogene Markov-Kette. Die Verteilung der Kette konvergiert unter gewissen Voraussetzungen gegen eine vom Startzustand unabhängige Grenzverteilung. Im Falle von SA soll diese auf den Zuständen gleichverteilt konzentriert sein, die bezüglich der Zielfunktion optimale Werte haben. Um die Geschwindigkeit zu untersuchen, mit der die Verteilung der Kette gegen eine solche Gleichverteilung konvergiert, betrachten wir eine strukturelle Größe, die ,,Conductance``, des der Markov-Kette zugrundeliegenden Transitionsgraphen.
Mit Hilfe von Abschätzungen der Conductance ist es Sinclair gelungen, perfekte Matchings in einem bipartiten Graphen gleichverteilt zu erzeugen und so mit hoher Wahrscheinlichkeit die Permanente einer Matrix zu berechnen. Dyer, Frieze und Kannan haben die Ergebnisse benutzt, um Punkte in ,,genügend glatten``, konvexen Körpern gleichverteilt zu erzeugen, und so deren Volumen bestimmt. Schließlich konnte Gademann mit dieser Technik einen polynomiellen, randomisierten Algorithmus entwerfen, der Lineare Programme löst. Unser Ziel ist es, diese Überlegungen, die auf eine homogene Markov-Kette und auf eine Gleichverteilung ausgerichtet waren, auf den für das SA relevanten Fall der inhomogenen Markov-Kette mit der auf die Optima konzentrierten Gleichverteilung zu erweitern. Da hier die Transitionsmatrizen zeitabhängig sind, muß die steuernde Größe jetzt eine zeitabhängige Conductance sein.
Tatsächlich sind uns selbst bei naiver Abschätzung der zeitabhängigen Conductance schon einige Konvergenzbeweise gelungen. Dabei wurden unter anderem ähnliche Resultate wie die von D.Mitra, F.Romeo und A.Sangiovanni-Vincentelli bei logarithmischen Kühlplänen erzielt und teilweise erweitert. Wie nicht anders zu erwarten, liefern diese naiven Abschätzungen der Conductance nur exponentielle Laufzeitschranken, bei denen eine Näherung an die Grenzverteilung garantiert werden kann.
Weiteres Ziel ist es daher, bei schwierigen kombinatorischen Problemen genauere Aussagen über die zeitabhängige Conductance zu erhalten, um polynomielle Laufzeitschranken zu erreichen. Man wird dabei aber nur die Approximation der Optimallösung fordern können. So konnte z.B. bei einer speziellen Version des Quadratic-Assignment-Problems die hinreichende Konvergenz bei nur polynomiellem Zeitbedarf nachgewiesen werden.
Unsere momentane Forschung konzentriert sich auf das NP-vollständige 3-Färbbarkeits-Problem. Dieses Problem scheint sehr geeignet zu sein, entsprechend gutes Konvergenzverhalten zu zeigen, da wir schon eine große Konvergenzgeschwindigkeit bei hohen Temperaturen zeigen konnten. Zur Zeit beschäftigen wir uns mit dem Entwurf von randomisierten Modellen, in denen alle 3-färbbaren Graphen anähernd gleichverteilt vorkommen. Hintergrund dieser Überlegungen ist der Versuch, die Komplexität dieses Problems zu verringern, um in polynomieller Laufzeit eine ausreichende Konvergenz von SA zu erhalten, ohne das Optimum nur approximieren zu müssen. Nächstes Ziel wird dann sein, geeignete Abschätzungen der zeitabhängigen Conductance auch für niedrige Temperaturen zu erhalten.