Simulated Annealing — Probabilistische Optimierung
- Jahr
- 1983
- Typ
- Probabilistic metaheuristic / local search
Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen
Was leistet sie?
Simulated Annealing (SA) ist eine probabilistische lokale Such-Metaheuristik, die 1983 von Kirkpatrick, Gelatt und Vecchi eingeführt wurde.
Sie modelliert den physikalischen Ausglühprozess in der Metallurgie – bei dem ein Material erhitzt und dann langsam abgekühlt wird, um einen kristallinen Zustand niedriger Energie zu erreichen – und nutzt diese Analogie, um lokale Optima in kombinatorischen und kontinuierlichen Optimierungsproblemen zu umgehen.
Die Intuition hinter der Methode
Stellen Sie sich vor, Sie versuchen, den tiefsten Punkt in einer hügeligen Landschaft zu finden, während Sie die Augen verbunden haben. Eine rein gierige Suche bewegt sich immer bergab und bleibt im ersten Tal stecken, das sie findet – welches möglicherweise nicht das tiefste ist. Simulated Annealing führt eine kontrollierte Zufälligkeit ein: Anfangs, wenn die 'Temperatur' hoch ist, ist der Algorithmus bereit, gelegentlich bergauf zu gehen und zufällig eine schlechtere Lösung zu akzeptieren. Wenn die Temperatur gemäß einem Abkühlplan sinkt, wird der Algorithmus zunehmend selektiver und konvergiert zu einer Lösung. Diese Bereitschaft, bei hoher Temperatur schlechtere Züge zu akzeptieren, ermöglicht es der Methode, flache lokale Optima zu verlassen und die Landschaft gründlicher zu erkunden.
Geschichte
Simulated Annealing wurde von Kirkpatrick, Gelatt und Vecchi in ihrer wegweisenden Arbeit von 1983 in Science eingeführt, die eine explizite Analogie zwischen dem thermodynamischen Ausglühen von Festkörpern und der kombinatorischen Optimierung zog. Dieselbe Idee wurde unabhängig von Cerny (1985) im Kontext des Problems des Handlungsreisenden vorgeschlagen. Van Laarhoven und Aarts (1987) lieferten die erste rigorose theoretische Behandlung und bewiesen Konvergenzeigenschaften unter verschiedenen Abkühlplänen. Seitdem hat sich die Methode zu einer der am weitesten verbreiteten und angewandten Metaheuristiken entwickelt, die in den Bereichen Ingenieurwesen, Operations Research, VLSI-Layout und Hyperparameter-Tuning für maschinelles Lernen eingesetzt wird.
Wann wird sie eingesetzt?
Simulated Annealing ist auf jedes Problem anwendbar, bei dem eine Nachbarschaftsstruktur über den Lösungsraum definiert werden kann, unabhängig davon, ob die Zielfunktion differenzierbar, konvex oder sogar analytisch ausdrückbar ist. Es eignet sich besonders gut für kombinatorische Probleme (Planung, Routenfindung, Graphenprobleme) und kontinuierliche Black-Box-Optimierung. Es sind keine Trainingsdaten oder Normalitätsannahmen erforderlich. Der Abkühlplan und die Nachbarschaftsstruktur müssen auf das Problem abgestimmt werden; weniger als etwa 1.000 Iterationen laufen zu lassen, birgt die Gefahr einer vorzeitigen Konvergenz zu einem lokalen Optimum, in welchem Fall eine einfachere deterministische lokale Suche bevorzugt werden sollte.
Grenzen und Hinweise
- Die Lösungsqualität ist empfindlich gegenüber dem Abkühlplan; ein schlechter Plan kann Ergebnisse liefern, die nicht besser sind als eine Zufallssuche.
- Die Nachbarschaftsstruktur muss für jede Problemklasse entworfen werden, was Fachkenntnisse erfordert.
- Die Konvergenz zum globalen Optimum erfordert in der Praxis extrem langsames Abkühlen, was die Laufzeit für hochwertige Garantien lang macht.
- Nutzt keine Gradienten- oder Strukturinformationen, daher übertreffen gradientenbasierte Methoden sie bei glatten, differenzierbaren Problemen.
Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.
Stärken
- Kann lokale Optima durch probabilistische Akzeptanz schlechterer Lösungen verlassen, im Gegensatz zum reinen Hill-Climbing.
- Anwendbar auf praktisch jeden Problemtyp – kombinatorisch, kontinuierlich, gemischt –, solange eine Nachbarschaftsstruktur definiert ist.
- Benötigt keine Gradienteninformationen und ist unempfindlich gegenüber der mathematischen Struktur der Zielfunktion.
- Hat eine theoretische Garantie der Konvergenz zum globalen Optimum unter ausreichend langsamem Abkühlen (Hajek 1988).
- Wenige Hyperparameter: Anfangstemperatur, Abkühlrate und Nachbarschaftsstruktur.
Anwendungen
- Kombinatorische Planungs- und Stundenplanprobleme, bei denen der Lösungsraum für eine erschöpfende Suche zu groß ist.
- Probleme des Handlungsreisenden und der Fahrzeugroutenplanung in Logistik und Operations Research.
- VLSI-Schaltungsentwurf und Chip-Floorplanning im Elektrotechnik.
- Proteinfaltung und Molekülkonformationsprobleme in der computergestützten Biologie.
- Hyperparameter-Optimierung für Modelle des maschinellen Lernens, wenn Gradienteninformationen nicht verfügbar sind.
- Ressourcenallokations- und Zuweisungsprobleme in Ingenieurwesen und Managementwissenschaft.
So funktioniert es
So funktioniert es
Der Algorithmus beginnt mit einer Startlösung – einem beliebigen zulässigen Punkt im Suchraum – und einer hohen Anfangstemperatur. Die Startlösung kann zufällig oder problemspezifisch sein; die Anfangstemperatur wird typischerweise so hoch gewählt, dass fast jede benachbarte Lösung zu Beginn akzeptiert würde.
Eine benachbarte Lösung wird durch eine kleine zufällige Änderung (einen 'Zug') an der aktuellen Lösung erzeugt. Die Nachbarschaftsstruktur muss auf das Problem zugeschnitten sein: Bei einem Planungsproblem könnte ein Zug zwei Aufgaben vertauschen; bei einer kontinuierlichen Funktion könnte er eine kleine zufällige Störung zum aktuellen Parametervektor hinzufügen.
Die Differenz im Zielfunktionswert zwischen der neuen und der aktuellen Lösung wird berechnet. Wenn die neue Lösung besser ist, wird sie immer akzeptiert. Wenn sie schlechter ist, wird sie mit einer Wahrscheinlichkeit akzeptiert, die mit der Größe der Verschlechterung und der aktuellen Temperatur abnimmt – typischerweise exp(−ΔE / T). Diese probabilistische Akzeptanz ist der Kernmechanismus, der eine vorzeitige Konvergenz verhindert.
Nach jeder Iteration (oder nach einer festen Anzahl von Zügen bei gleicher Temperatur) wird die Temperatur gemäß einem Abkühlplan reduziert – üblicherweise ein geometrischer Plan T ← α·T, wobei α knapp unter 1 liegt. Die Wahl des Abkühlplans beeinflusst die Lösungsqualität stark: Zu schnelles Abkühlen fängt die Suche in einem lokalen Optimum ein; zu langsames Abkühlen verschwendet Rechenzeit.
Der Algorithmus stoppt, wenn die Temperatur einen minimalen Schwellenwert unterschreitet, eine maximale Anzahl von Iterationen erreicht ist oder sich die Lösung über eine bestimmte Anzahl von Schritten nicht verbessert hat. Die beste während des gesamten Laufs gefundene Lösung – nicht nur der Endzustand – wird als Ergebnis zurückgegeben.
Häufige Fallstricke
- Zu wenige Iterationen (etwa unter 1.000) laufen zu lassen, verhindert, dass der Abkühlplan ordnungsgemäß funktioniert, und lässt die Suche in einem lokalen Optimum stecken – bevorzugen Sie Tabu-Suche oder eine deterministische lokale Suche, wenn die Laufzeit stark begrenzt ist.
- Die Anfangstemperatur zu niedrig einzustellen bedeutet, dass der Algorithmus sofort wie ein gieriges Hill-Climbing agiert und seine Fähigkeit verliert, lokale Optima zu verlassen.
- Die Abkühlrate zu aggressiv einzustellen (z. B. α unter 0,9) verursacht vorzeitige Konvergenz; überprüfen Sie die endgültige Lösungsqualität durch Neustarts von mehreren Startlösungen.
- Eine Nachbarschaftsverschiebung, die für einen Problemtyp entwickelt wurde, auf einen anderen Problemtyp anzuwenden, kann Züge unzulösbar oder bedeutungslos machen – überprüfen Sie immer, ob jeder erzeugte Nachbar eine gültige Lösung ist.
- Nur den Endzustand zu berichten, anstatt die beste jemals während des Laufs gesehene Lösung, kann das wahre Optimum verpassen, das in einem Zwischenschritt gefunden wurde.
Häufig gestellte Fragen
Wie wähle ich den Abkühlplan?
Der geometrische Plan T ← α·T mit α zwischen 0,90 und 0,99 ist der häufigste Ausgangspunkt. Ein praktischer Ansatz ist, die Anfangstemperatur so hoch einzustellen, dass etwa 80 % der Züge zu Beginn akzeptiert werden, und sie dann zu reduzieren, bis weniger als 1 % der Aufwärtszüge akzeptiert werden. Wenn die endgültige Lösungsqualität schlecht ist, verlangsamen Sie die Abkühlrate (erhöhen Sie α); wenn die Laufzeit zu lang ist, beschleunigen Sie sie. Führen Sie den Algorithmus immer mehrmals von verschiedenen Startlösungen aus, um die Robustheit zu bewerten.
Wie unterscheidet sich Simulated Annealing von genetischen Algorithmen oder Particle Swarm Optimization?
Simulated Annealing verwaltet eine einzelne Lösung und erkundet die Nachbarschaft durch zufällige Störungen, wobei schlechtere Lösungen probabilistisch akzeptiert werden. Genetische Algorithmen und Particle Swarm Optimization verwalten eine Population von Lösungen und verwenden Kreuzung, Mutation oder Schwarmbewegung, um die Population zu entwickeln. Simulated Annealing ist im Allgemeinen einfacher zu implementieren für Probleme mit einer natürlichen Nachbarschaftsstruktur, während populationsbasierte Methoden für hochdimensionale kontinuierliche Probleme effektiver sein können.
Ist das globale Optimum garantiert?
Theoretisch ja, unter der Bedingung, dass die Temperatur ausreichend langsam abnimmt (logarithmisches Abkühlen). In der Praxis ist ein solches Abkühlen rechnerisch nicht durchführbar, sodass der Algorithmus eine nahezu optimale Lösung findet. Die Qualität des Ergebnisses verbessert sich mit langsamerem Abkühlen und mehr Iterationen, aber es gibt keine Garantie für endliche Zeit. Das mehrmalige Ausführen von Neustarts und das Beibehalten der besten gefundenen Lösung ist eine praktische Methode, um die Zuversicht zu erhöhen.
Wann sollte ich stattdessen Tabu-Suche oder einen genetischen Algorithmus bevorzugen?
Wählen Sie Tabu-Suche, wenn Sie eine deterministische, speichergeführte Suche benötigen, die das erneute Besuchen kürzlicher Lösungen vermeidet und die Problemstruktur effizient in kürzerer Laufzeit nutzen kann. Wählen Sie einen genetischen Algorithmus oder Particle Swarm Optimization, wenn das Problem hochdimensional und kontinuierlich ist oder wenn eine Population vielfältiger Lösungen benötigt wird, um die optimale Landschaft abzubilden. Simulated Annealing ist eine starke Standardwahl für kombinatorische Probleme mit einer klaren Nachbarschaftsstruktur und wenn die Einfachheit der Implementierung wichtig ist.
Verwandte Methoden
Quellen
Kirkpatrick, S., Gelatt, C.D. & Vecchi, M.P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671-680.
DOI-Referenz öffnenKopiert.van Laarhoven, P.J.M. & Aarts, E.H.L. (1987). Simulated Annealing: Theory and Applications. Springer.
ISBN: 9789027725431Kopiert.