Podręcznik

Symulowane wyżarzanie (ang. simulated annealing, SA) to probabilistyczna technika inspirowana procesem wyżarzania w metalurgii, w którym materiał jest podgrzewany do wysokiej temperatury, a następnie powoli chłodzony, aby uzyskać stabilną strukturę krystaliczną przy minimalnej energii. Ten proces fizyczny jest analogiczny do poszukiwania globalnego minimum w problemie optymalizacji.

Podstawy teoretyczne

Funkcja energii i przestrzeń stanów

• Funkcja energii: W terminologii optymalizacyjnej energia odpowiada funkcji celu $f(x)$, którą staramy się zminimalizować.
• Przestrzeń stanów: Zbiór wszystkich możliwych rozwiązań tworzy przestrzeń stanów, w której każdy stan $x$ reprezentuje rozwiązanie dopuszczalne

Kryterium Metropolisa

W każdej iteracji nowe rozwiązanie $x'$ jest generowane z bieżącego rozwiązania $x$. Zmiana energii (wartość funkcji celu) jest obliczana jako:

$\Delta E = f(x') - f(x)$

Prawdopodobieństwo akceptacji $P$ nowego stanu $x′$ jest dane przez kryterium Metropolisa:

Gdzie $T$ jest aktualną temperaturą a $\text{exp}$ oznacza funkcję wykładniczą.

Algorytm

1. Inicjalizacja:

   • Wybierz rozwiązanie początkowe $x_0$
   • Ustaw początkową temperaturę $T_0$

2. Pojedyncza iteracja:

   • Generowanie sąsiedztwa: Generuj nowe proponowane rozwiązanie x′  z sąsiedztwa $N(x)$ aktualnego rozwiązania $x$.
   • Wyliczenie zmiany energii: Policz $\Delta E = f(x') - f(x)$
   • Decyzja o akceptacji: Akceptuj $x'$ jako nowe rozwiązanie aktualne z prawdopodobieństwem $P$ określonym przez kryterium Metropolisa.
   • Schemat schładzania: Modyfikuj temperaturę $T$ zgodnie ze schematem schładzania $T_{k+1} = \alpha T_$, where $\alpha \in (0,1)$.

3. Zakończenie:

   • Zatrzymaj algorytm, po osiągnięciu kryterium stopu, np. $T$ spadnie poniżej zadanego progu lub zostanie wykonana określona liczba iteracji.

Schematy schładzania

Schemat chłodzenia decyduje o tym, w jaki sposób temperatura ma spadać w czasie i jest kluczowy dla wydajności algorytmu.

• Geometryczny:

  $T_{k+1} = \alpha T_k$

  gdzie $\alpha$ jest stałym współczynnikiem mniejszym od 1.

• Liniowy:

  $T_{k+1} = T_k - \beta$
  
  gdzie$\beta$ jest dodatnią stałą.
  
  

• Logarytmiczny:

  $T_k = \frac{T_0}{\ln(k + c)}$

  gdzie $c$ jest stałą a $k$ jest numerem iteracji.

Struktura sąsiedztwa

The choice of neighbourhood structure $N(x)$N(x) [LaTeX: N(x)] defines how new candidate solutions are generated.

Wybór struktury sąsiedztwa $N(x)$ definiuje sposób generowania nowych rozwiązań. Np . w  problemach takich jak Problem Komiwojażera (TSP) sąsiedztwa można generować za pomocą operacji takich jak zamiana dwóch miast, odwrócenie sekwencji miast (2-opt) lub przesunięcie miasta na nową pozycję.

Zbieżność metody

Rozważania praktyczne

• Temperatura początkowa $T_0$: Powinna być wystarczająco wysoka, aby umożliwić eksplorację przestrzeni stanów.
• Temperatura końcowa $T_{\text{final}}$: Określa, kiedy algorytm się zatrzyma; często jest ustawiana blisko zera.
• Liczba iteracji w każdej temperaturze: może być stała lub dynamiczna; więcej iteracji pozwala na lepszą eksplorację na każdym poziomie temperatury.
• zybkość schładzania $\alph$: Wpływa na szybkość spadku temperatury; wartość bliska 1 spowalnia chłodzenie i pozwala na dokładniejszą eksplorację..

Zalety i ograniczenia SA

Zalety:

• Unikanie lokalnych optimów: Akceptując gorsze rozwiązania, SA może uniknąć lokalnego minimum.
• Prostota i elastyczność: łatwość implementacji i adaptacji do nowych problemów.
• Solidne podstawy teoretyczne: bazuje na solidnych prawach mechaniki statystycznej.

Ograniczenia:

• Powolna zbieżność: właszcza przy powolnym harmonogramie chłodzenia, SA może być czasochłonne.
• Wrażliwość na parametry: Wydajność zależy w dużej mierze od wyboru początkowej temperatury, harmonogramu chłodzenia i liczby iteracji.
• Brak gwarancji optymalności w praktyce: Podczas gdy teoretycznie zbieżność jest gwarantowana w pewnych warunkach, praktyczne implementacje mogą nie osiągnąć globalnego optimum z powodu ograniczeń czasowych