Simuliertes Glühen
Simuliertes GlühenDer Algorithmus ist ein allgemeiner probabilistischer Algorithmus, der verwendet wird, um die optimale Lösung für eine Aussage in einem großen Suchraum zu finden.
Prinzip
Wenden Sie die Theorie der Thermodynamik auf die Statistik an und stellen Sie sich jeden Punkt im Suchraum als ein Molekül in der Luft vor. die Energie eines Moleküls ist seine eigene kinetische Energie; und jeder Punkt im Suchraum trägt, wie ein Luftmolekül, „Energie“, um den Grad der Eignung des Punktes für den Vorschlag anzuzeigen.
Der Algorithmus beginnt mit einem beliebigen Punkt im Suchraum: Bei jedem Schritt wird ein „Nachbar“ ausgewählt und dann die Wahrscheinlichkeit berechnet, den „Nachbarn“ von der aktuellen Position aus zu erreichen.
Grundelemente
Zustandsraum und Zustandserzeugungsfunktion
1) Der Suchraum wird auch Zustandsraum genannt und besteht aus der Menge der codierten möglichen Lösungen.
2) Die Zustandsgenerierungsfunktion (Nachbarschaftsfunktion) sollte sicherstellen, dass die generierten Kandidatenlösungen möglichst über den gesamten Lösungsraum verteilt sind. Es besteht normalerweise aus zwei Teilen, nämlich der Methode zum Generieren von Kandidatenlösungen und der Wahrscheinlichkeitsverteilung der Kandidatenlösungen.
3) Kandidatenlösungen werden im Allgemeinen durch zufällige Stichprobenziehung des Lösungsraums gemäß einer bestimmten Wahrscheinlichkeitsdichtefunktion erhalten.
4) Die Wahrscheinlichkeitsverteilung kann eine Gleichverteilung, Normalverteilung, Exponentialverteilung usw. sein.
Zustandsübergangswahrscheinlichkeit
1) Die Zustandsübergangswahrscheinlichkeit bezieht sich auf die Wahrscheinlichkeit des Übergangs von einem Zustand in einen anderen.
2) Das allgemeine Verständnis ist die Wahrscheinlichkeit, eine neue Lösung als aktuelle Lösung zu akzeptieren.
3) Es hängt mit dem aktuellen Temperaturparameter T zusammen und nimmt mit sinkender Temperatur ab.
4) Das Metropolenkriterium wird grundsätzlich übernommen.
Kriterien für die Beendigung der inneren Schleife
1) Überprüfen Sie, ob der Mittelwert der Zielfunktion stabil ist.
2) Der Zielwert ändert sich über mehrere aufeinanderfolgende Schritte hinweg kaum.
3) Stichprobenentnahme nach einer bestimmten Anzahl von Schritten.
Kriterien für die Beendigung der äußeren Schleife
1) Stellen Sie den Grenzwert für die Beendigungstemperatur ein.
2) Legen Sie die Anzahl der Iterationen der äußeren Schleife fest.
3) Der vom Algorithmus gesuchte optimale Wert bleibt über mehrere aufeinanderfolgende Schritte hinweg unverändert.
4) Überprüfen Sie, ob die Systementropie stabil ist.
Wichtige Schritte
Neue Zustandsgenerierungsfunktion → Neue Zustandsakzeptanzfunktion → Sampling-Stabilitätskriterium → Abkühlfunktion → Annealing-Endkriterium
Vorteile des Simulated Annealing
Der Simulated-Annealing-Algorithmus kann schnell die annähernd optimale Lösung des Problems finden. Unter der Voraussetzung einer geeigneten Parametereinstellung weist der Simulated-Annealing-Algorithmus eine hohe Suchleistung auf.