Entsprechend der Temperatur schwingen die Moleküle zunächst mehr, später weniger stark. Dementsprechend werden je nach Temperatur mehr oder weniger starke Verschlechterungen der aktuellen Lösung akzeptiert. Veränderungen, die zu einer Verbesserung führen, werden immer akzeptiert. Neben der Temperatur und der Differenz der Kosten der Lösungen hängt die Akzeptanz einer Veränderung auch noch vom Zufall ab. Dieser sorgt dafür, dass es sich beim Simulated Annealing um einen stochastischen, nicht-deterministischen Algorithmus handelt. Je geringer die Temperatur ist, desto geringer ist auch die Wahrscheinlichkeit, dass eine Verschlechterung akzeptiert wird. Je stärker sich die Kosten erhöhen, desto unwahrscheinlicher wird die Akzeptanz dieser Veränderung. Meistens wird dieser Zusammenhang durch die Boltzmann-Wahrscheinlichkeitsfunktion exp((NeueKosten-AlteKosten) / (k*Temperatur)) modelliert, wobei k die Boltzmann-Konstante ist.
Im Allgemeninen wird die letzte bekannte beste Lösung noch einmal seperat abgespeichert.