PL 
EnglishDomyślny
Українська🌡️ Symulowane wyżarzanie — ucieczka z minimów lokalnych
Rozwiąż problem komiwojażera symulowanym wyżarzaniem: gorsze ruchy są akceptowane z prawdopodobieństwem e^(−ΔE/T), gdy temperatura spada, co pozwala uciec z minimów lokalnych przed osiągnięciem krótkiej trasy.
O symulowanym wyżarzaniu
Symulowane wyżarzanie (SA) to probabilistyczna metaheurystyka wprowadzona przez Kirkpatricka, Gelatta i Vecchiego w 1983 roku, inspirowana fizycznym procesem kontrolowanego chłodzenia w metalurgii: powolne studzenie stopionego materiału pozwala atomom osiąść w kryształowych sieciach o niskiej energii, podczas gdy szybkie hartowanie uwięzia je w amorficznych stanach o wysokiej energii. W optymalizacji SA zaczyna od wysokiej „temperatury” T i akceptuje gorsze rozwiązania z prawdopodobieństwem e−ΔE/T (kryterium Metropolis), pozwalając uciec z minimów lokalnych; wraz ze spadkiem T zgodnie z harmonogramem chłodzenia algorytm coraz bardziej zachowuje się jak wspinaczka po wzgórzu i zbiega do rozwiązania. SA może znaleźć niemal optymalne rozwiązania dla problemów NP-trudnych, takich jak problem komiwojażera (TSP), gdzie wyczerpujące przeszukiwanie jest niewykonalne.
Ta symulacja stosuje SA do TSP na losowym zbiorze miast: obserwuj, jak trasa poprawia się wraz z chłodzeniem temperatury, obserwuj zaakceptowane gorsze ruchy podświetlone na pomarańczowo oraz porównaj ostateczną długość trasy z zachłannym najbliższym sąsiadem. Konfigurowalne parametry obejmują temperaturę początkową, tempo chłodzenia i liczbę miast, pozwalając bezpośrednio zbadać kompromis jakość-czas działania.
Najczęściej zadawane pytania
Dlaczego symulowane wyżarzanie akceptuje gorsze rozwiązania?
Akceptowanie gorszych rozwiązań z prawdopodobieństwem e−ΔE/T pozwala algorytmowi uciec z minimów lokalnych — konfiguracji, w których każda mała zmiana pogarsza rozwiązanie, ale które nie są globalnie optymalne. Przy wysokiej temperaturze T niemal wszystkie gorsze ruchy są akceptowane (algorytm szeroko eksploruje); w miarę spadku T akceptowanych jest mniej gorszych ruchów, a algorytm skupia się na eksploatacji. Ta równowaga między eksploracją a eksploatacją to podstawowy mechanizm odróżniający SA od prostej wspinaczki po wzgórzu.
Jaki harmonogram chłodzenia daje najlepsze wyniki?
Chłodzenie logarytmiczne (T(t) = T₀/ln(1+t)) jest teoretycznie gwarantowane, że znajdzie optimum globalne, gdy t→∞, ale jest niepraktycznie wolne. W praktyce standardem jest chłodzenie geometryczne T(t+1) = α·T(t) z α ∈ [0,95, 0,999]: chłodzi wystarczająco szybko, by być praktyczne, ale wystarczająco wolno, by umożliwić ucieczkę z minimów lokalnych. Optymalne α i początkowe T₀ zależą od problemu; T₀ jest często dobierane tak, by początkowo akceptowanych było 80% gorszych ruchów, zapewniając dokładną wczesną eksplorację.
Jak symulowane wyżarzanie stosuje się do problemu komiwojażera?
Stan TSP to trasa (permutacja miast); sąsiedztwo definiowane jest przez zamiany 2-opt (odwrócenie segmentu trasy) lub ruchy 3-opt (ponowne połączenie trzech segmentów trasy). Energia E to całkowita długość trasy. Każda iteracja proponuje losowego sąsiada: jeśli jest krótszy, akceptuj go; jeśli jest dłuższy o ΔL, akceptuj go z prawdopodobieństwem e−ΔL/T. Po milionach iteracji ze spadającym T, SA zwykle znajduje trasy w granicach 1–3% optimum dla setek miast.
Czy symulowane wyżarzanie gwarantuje znalezienie optimum globalnego?
Przy chłodzeniu logarytmicznym (T(t) = c/ln(t+2)) SA zbiega do optimum globalnego z prawdopodobieństwem 1 w nieskończonym czasie — wynik zawdzięczany Hajekowi (1988). W praktyce skończone przebiegi z chłodzeniem geometrycznym nie gwarantują optimum globalnego. Dla TSP z n miastami optimum globalne jest NP-trudne do obliczenia, ale SA z dobrymi ruchami 2-opt lub Lin-Kernighan konsekwentnie znajduje rozwiązania w granicach kilku procent optimum dla n ≤ 1000 miast w sekundach.
Czym jest kryterium Metropolis i skąd pochodzi?
Kryterium Metropolis e−ΔE/T pochodzi z mechaniki statystycznej: w zespole kanonicznym o temperaturze T prawdopodobieństwo, że system zajmuje stan o energii E, jest proporcjonalne do e−E/kT (rozkład Boltzmanna). Współczynnik akceptacji e−ΔE/T dla ruchu zwiększającego energię o ΔE zapewnia, że łańcuch Markowa zbiega do rozkładu Boltzmanna przy ustalonym T — własność gwarantująca, że SA odwiedza rozwiązania o niskiej energii (dobre) najczęściej przy niskich temperaturach.
Jak symulowane wyżarzanie wypada w porównaniu z algorytmami genetycznymi?
Obie są metaheurystykami inspirowanymi populacją do optymalizacji NP-trudnej. SA utrzymuje pojedyncze bieżące rozwiązanie i używa temperatury do kontroli różnorodności; algorytmy genetyczne utrzymują populację rozwiązań i używają krzyżowania oraz mutacji. SA jest prostsze do zaimplementowania i dostrojenia; algorytmy genetyczne mogą wykorzystywać strukturę rozwiązania poprzez krzyżowanie. W praktyce SA często przewyższa podstawowe algorytmy genetyczne dla TSP przy umiarkowanej liczbie miast, podczas gdy algorytmy genetyczne (zwłaszcza z przeszukiwaniem lokalnym — „algorytmy memetyczne”) lepiej skalują się do bardzo dużych instancji.
Czym jest ponowne rozgrzanie i kiedy powinno się je stosować?
Ponowne rozgrzanie okresowo zwiększa T z powrotem do wyższej wartości, jeśli algorytm utknął w tym, co wygląda na minimum lokalne, przez wiele iteracji. Może to pomóc SA uciec z głębokich lokalnych basenów, z których samo chłodzenie geometryczne nie potrafi uciec. Jednak ponowne rozgrzanie komplikuje analizę zbieżności i może marnować czas obliczeniowy. Adaptacyjne harmonogramy chłodzenia monitorujące wskaźniki akceptacji i dynamicznie dostosowujące T (np. utrzymując docelowy wskaźnik akceptacji na poziomie 20%) są często bardziej zasadnymi alternatywami.
Jakie rzeczywiste problemy wykorzystują symulowane wyżarzanie?
SA jest używane w projektowaniu układów VLSI (rozmieszczanie elementów obwodu, by zminimalizować długość przewodów — IBM użyło go dla chipu, który stał się oryginalnym Makiem), zwijaniu białek (minimalizacja energii swobodnej), planowaniu (harmonogramy egzaminów, planowanie załóg lotniczych), projektowaniu sieci telekomunikacyjnych oraz rekonstrukcji obrazu w tomografii. Nowoczesne implementacje SA są często hybrydyzowane z heurystykami przeszukiwania lokalnego, by dramatycznie poprawić jakość rozwiązania w ramach tego samego budżetu CPU.
Jak wybiera się temperaturę początkową T₀?
Popularna heurystyka: próbkuj zbiór losowych ruchów, oblicz średni wzrost energii ΔE̅ dla tych, które pogarszają rozwiązanie, a następnie ustaw T₀ = −ΔE̅ / ln(χ₀), gdzie χ₀ to pożądane początkowe prawdopodobieństwo akceptacji (zwykle 0,8). Zapewnia to, że algorytm zaczyna wystarczająco „gorąco”, by zaakceptować 80% gorszych ruchów, gwarantując szeroką początkową eksplorację. Alternatywnie, T₀ można ustawić jako odchylenie standardowe wartości funkcji celu na losowych rozwiązaniach, przeskalowane przez stałą.
Jaka jest różnica między symulowanym wyżarzaniem a basin-hopping?
Basin-hopping (Wales i Doye, 1997) łączy kroki losowej perturbacji z lokalną minimalizacją: każdy „krok” SA wykonuje pełny spadek gradientowy do najbliższego minimum lokalnego przed zastosowaniem kryterium Metropolis. Przekształca to krajobraz energii w uproszczony krajobraz „basenów” (płaski wewnątrz każdego basenu, nieciągły na granicach basenów), co jest znacznie łatwiejsze dla SA do nawigacji. Basin-hopping jest standardem w chemii obliczeniowej do znajdowania struktur białek i klastrów.