Algorytm pokonywania wzniesień, który nigdy nie wykonuje ruchów „w dół” w kierunku stanów o niższej wartości (lub wyższym koszcie), jest zawsze podatny na utknięcie w lokalnym maksimum. W przeciwieństwie do tego, czysto losowe chodzenie, które przechodzi do stanu następcy bez troski o wartość, ostatecznie natknie się na globalne maksimum, ale będzie wyjątkowo nieefektywne. Dlatego rozsądne wydaje się połączenie wspinaczki pod górę z chodzeniem losowym w sposób, który zapewni zarówno efektywność, jak i kompletność. Takim algorytmem jest symulowane wyżarzanie. W metalurgii wyżarzanie jest procesem stosowanym do odpuszczania lub hartowania metali i szkła poprzez podgrzanie ich do wysokiej temperatury, a następnie stopniowe ich schładzanie, co pozwala na osiągnięcie przez materiał stanu krystalicznego o niskiej energii. Aby wyjaśnić symulowane wyżarzanie, zmieniamy nasz punkt widzenia ze wspinania się pod górę na schodzenie w dół (tj. minimalizując koszty) i wyobrażamy sobie zadanie wbicia piłki pingpongowej w najgłębszą szczelinę na bardzo wyboistej powierzchni. Jeśli po prostu pozwolimy piłce toczyć się, zatrzyma się ona na lokalnym minimum. Jeśli potrząśniemy powierzchnią, możemy wybić piłkę z lokalnego minimum – być może do głębszego lokalnego minimum, gdzie spędzi więcej czasu. Sztuką jest potrząsać wystarczająco mocno, aby wybić piłkę z lokalnych minimów, ale nie na tyle mocno, aby wybić ją z globalnego minimum. Roztwór do symulowanego wyżarzania ma rozpocząć się od mocnego wstrząsania (tj. w wysokiej temperaturze), a następnie stopniowo zmniejszać intensywność wytrząsania (tj. obniżać temperaturę). Ogólna struktura algorytmu symulowanego wyżarzania (rysunek 4.5 ) jest podobna do wspinaczki pod górę.
Jednak zamiast wybrać najlepszy ruch, wybiera losowy ruch. Jeśli posunięcie poprawia sytuację, jest zawsze akceptowane. W przeciwnym razie algorytm akceptuje ruch z pewnym prawdopodobieństwem mniejszym niż 1. Prawdopodobieństwo maleje wykładniczo wraz ze „złością” ruchu – wielkością ∆E, o którą ocena jest pogorszona. Prawdopodobieństwo maleje również wraz ze spadkiem „temperatury” T: „złe” ruchy są bardziej prawdopodobne na początku, gdy T jest wysokie, i stają się mniej prawdopodobne, gdy T maleje. Jeśli harmonogram obniży T do 0 wystarczająco wolno, to własność rozkładu Boltzmanna, e∆E/T, polega na tym, że całe prawdopodobieństwo koncentruje się na globalnych maksimach, które algorytm znajdzie z prawdopodobieństwem bliskim 1. Symulowane wyżarzanie było używane do rozwiązywania problemów z układem VLSI począwszy od lat 80-tych. Jest szeroko stosowany w harmonogramach fabrycznych i innych zadaniach optymalizacyjnych na dużą skalę.