Czym jest Symulowane wyżarzanie (Simulated Annealing)?
Symulowane wyżarzanie, znane w literaturze jako Simulated Annealing (SA), jest techniką optymalizacji opartą na analogii do kontrolowanego ochładzania metali. W procesie wyżarzania atomy początkowo poruszają się swobodnie w wysokiej temperaturze, a następnie wraz z obniżaniem temperatury zyskują uporządkowaną, energetycznie korzystną strukturę. Algorytm przenosi tę ideę na grunt poszukiwania minimum globalnego funkcji kosztu: w początkowej fazie dopuszcza skoki do rozwiązań gorszych, a następnie stopniowo ogranicza tę swobodę, koncentrując się na coraz lepszych stanach.
Jak dokładnie działa Symulowane wyżarzanie (Simulated Annealing)
Działanie SA opiera się na trzech elementach: reprezentacji stanu, funkcji celu oraz harmonogramie chłodzenia. W każdym kroku algorytm losowo modyfikuje bieżące rozwiązanie i oblicza zmianę energii (ΔE). Jeśli nowy stan jest lepszy (ΔE < 0), zostaje przyjęty bezwarunkowo. Gdy jest gorszy, akceptacja następuje z prawdopodobieństwem p = exp(−ΔE ⁄ T), gdzie T to temperatura sterująca. Wraz z upływem iteracji T maleje zgodnie z ustalonym harmonogramem, co zmniejsza szansę przyjmowania gorszych stanów i ukierunkowuje poszukiwania na obszary optymalne.
Przykładowy przebieg algorytmu
W problemie komiwojażera losowo zamienia się kolejność dwóch miast, oblicza nową długość trasy, a następnie decyduje o akceptacji na podstawie temperatury. Przy wysokiej T algorytm chętnie eksploruje odległe permutacje, natomiast przy niskiej T doskonali już znalezione, obiecujące trasy.
Kontekst historyczny
Za prekursora uznaje się S. Černý’ego, który w 1982 roku zaproponował wykorzystanie schematu Metropolisa do problemów kombinatorycznych. Rok później badacze z IBM – Scott Kirkpatrick, Jr. C. Daniel Gelatt i Mario P. Vecchi – opublikowali w czasopiśmie Science artykuł „Optimization by Simulated Annealing”, wprowadzając nazwę oraz formalizując technikę dla szerokiej klasy zadań optymalizacji.
Zastosowania w praktyce
Symulowane wyżarzanie zostało z powodzeniem zastosowane do projektowania układów VLSI, harmonogramowania produkcji, rozmieszczania serwerów w centrach danych, doboru cech w systemach uczących się czy strojenia hiperparametrów sieci neuronowych. Przykładowo, w logistyce pozwala ono minimalizować koszty tras dostaw przy uwzględnieniu okien czasowych i ograniczeń pojazdów.
Zalety i ograniczenia
Największym atutem SA jest zdolność do ucieczki z minimów lokalnych, co odróżnia je od klasycznych metod gradientowych wymagających wypukłej funkcji celu. W zamian trzeba zaakceptować większą liczbę iteracji i konieczność doboru parametrów chłodzenia. Te same właściwości probabilistyczne, które pozwalają eksplorować przestrzeń rozwiązań, mogą przy zbyt powolnym chłodzeniu wydłużać czas obliczeń.
Na co uważać?
Niedostatecznie stroma kurtyna temperatury może prowadzić do przedwczesnej konwergencji, natomiast zbyt wolne chłodzenie wydłuża obliczenia bez gwarancji znaczącej poprawy. W praktyce zaleca się testowanie kilku harmonogramów (geometrycznego, logarytmicznego, adaptacyjnego) oraz uwzględnienie charakterystyki sprzętu, aby znaleźć równowagę między jakością a czasem działania.
Dodatkowe źródła
Więcej szczegółów można znaleźć w artykule Simulated annealing – Wikipedia, w pracy oryginalnej Optimization by Simulated Annealing oraz w przeglądzie badawczym arXiv:1704.04574.
