Autor
Peter Rossmanith, RWTH Aachen
Simulated Annealing könnte man mit "simuliertes langsames Abkühlen" übersetzen. Eigentlich gibt es wohl kein deutsches Wort, das dem englischen annealing entspricht. Die eigentliche Bedeutung ist "erhitzen und dann langsam abkühlen". In der Technik wird ein solches Verfahren vielfach eingesetzt. Werden erhitzte Metalle schnell oder langsam aus dem rotglühenden Zustand abgekühlt, haben sie ganz unterschiedliche Eigenschaften. Warum macht man das? Überlegen wir uns doch mal, was dabei mit den kleinen Teilchen (Atomen) passiert, aus denen das Metall besteht:
Diese Atome sind ursprünglich in ein festes Gitter eingebunden. Wenn man das Metall nun erhitzt, fangen sie an, sich aus ihren Bindungen zu lösen und zu bewegen. Die ursprüngliche Struktur wird also zerstört. Wenn man jetzt langsam abkühlt, dann suchen sich die Teilchen neue Bindungen. Erstaunlicherweise verteilen sie sich dabei oft regelmäßiger als vorher. Wenn man alles richtig macht, wird das Metall dabei weicher, flexibler und enthält weniger Unregelmäßigkeiten.
Wichtig ist dies auch bei der Herstellung von Halbleitern aus Silizium, aus welchem letztendlich die Mikroprozessoren und Speicherbausteine in Computern bestehen. Hier wird ein besonders reines Siliziumkristall benötigt, das insbesondere keine Unregelmäßigkeiten enthält.
Um den Effekt des langsamen Abkühlens besser nachvollziehen zu können, kannst Du Dir die Teilchen als kleine Kugeln vorstellen. Wenn man die einfach so in ein Gefäß wirft (so wie in dem ersten Applet hier), dann liegen sie vielleicht ziemlich unordentlich herum. Was könnte man tun, um sie zu ordnen? Schütteln! Dadurch erhöht sich natürlich erst mal die Unordnung, und die Teilchen fliegen herum - dem Schütteln entspricht das Erhitzen. Wenn man jetzt aber immer langsamer schüttelt, dann ordnen sich die Kugeln ganz von selbst!
Im folgenden Applet befindet sich ein Regler, mit dem die Kugeln stärker oder schwächer durchgeschüttelt werden können. Die Kugeln sind ein bißchen klebrig und können auch zusammengequetscht werden. Schüttele sie und siehe, wie sie mehr oder weniger kompakt gestapelt werden.
Das ist ja eine ganz erstaunliche Sache, und wir werden nachher noch ein bißchen darüber nachdenken, warum es funktioniert. Aber was hat das alles mit Informatik und Algorithmen zu tun, und warum sollte man es simulieren?
Nehmen wir mal ein typisches Problem der Informatik, das Problem des Handelsreisenden, welches in der letzten Woche behandelt wurde. Wieder will ein Handelsreisender eine Menge von Städten besuchen und dabei möglichst wenig Zeit brauchen. Es geht also darum, die Reihenfolge, in der er die Städte besucht, möglichst geschickt festzulegen, so daß der zurückgelegte Weg möglichst kurz wird. Das ist erstaunlicherweise ein sehr schwieriges Problem.
Vielleicht können wir eine möglichst gute Lösung finden, indem wir simulated annealing verwenden. Irgendeine Lösung zu finden ist ja einfach: Wir nehmen eine beliebige Reihenfolge! In dem zweiten Applet sehen wir eine Anzahl von Städten, die durch eine zufällige Tour verbunden sind. Es ist natürlich ziemlich unwahrscheinlich, daß diese Tour sehr kurz ist.
Wie können wir diese Tour verbessern, indem wir kleine Änderungen vornehmen? Nun, wir könnten einfach zufällig ein Teilstück wählen und dieses fortan in umgekehrter Reihenfolge durchlaufen:
Eine andere Möglichkeit besteht darin, eine Stadt zu einem anderen Zeitpunkt zu besuchen und die Reihenfolge aller anderen Städte beizubehalten:
Danach kann die Tour besser oder schlechter sein. Wenn sie besser ist, behalten wir die Änderung, sonst machen wir sie rückgängig. Genau dies leistet das folgende Applet bei sehr niedrigen Temperaturen.
Versuche einmal, die Temperatur auf 0 und die Anzahl der Städte auf etwa 50 zu stellen. Drücke dann den Startknopf! Du wirst sehen, daß die Lösung immer besser wird und sich dann nicht mehr verändert. Da die Temperatur klein ist, werden Veränderungen nur vorgenommen, falls sie zu einer besseren Tour führen, was irgendwann nicht mehr möglich ist. Je höher die Temperatur aber ist, desto eher werden auch Veränderungen vorgenommen, die die Lösung verschlechtern. Dies ist wichtig, um einer Lösung zu entkommen, die zwar nicht die beste ist, aber dennoch nicht durch einfache Vertauschungen verbessert werden kann.
Merke Dir die Länge der berechneten Tour und erhöhe die Temperatur wieder auf 100. Jetzt ändert sich die Tour wieder, und du kannst die Temperatur sehr, sehr langsam absenken. Wenn Du genug Geduld hast, müßtest Du eine bessere Lösung erhalten.
Dieses Optimierungsverfahren simuliert einen natürlichen Prozeß und kann nicht nur für das Problem des Handlungsreisenden benutzt werden. Tatsächlich können wir es für viele schwierige Optimierungsprobleme einsetzen, bei denen man leicht eine beliebige Lösung finden und lokal verbessern kann. Solche Verfahren, die oft sehr gut funktionieren, aber keine Garantie für eine optimale oder auch nur gute Lösung geben, nennen wir Heuristiken. Beim simulated annealing handelt es sich strenggenommen um ein Verfahren, das der Natur abgeschaut wurde. Die meisten Algorithmen haben nicht diese Eigenschaft, aber neben dem simulated annealing gibt es durchaus noch andere Verfahren dieses Ursprungs. Eines davon sind die genetischen Algorithmen.