Metaheurystyki — Symulowane Wyżarzanie i Tabu Search
Pojęcia wspólne — sąsiedztwo i przeszukiwanie lokalne
| Symbol | Znaczenie |
|---|---|
| ui ∈ U | Bieżące rozwiązanie dopuszczalne |
| N: U → 2U | Odwzorowanie generujące sąsiedztwo |
| Ui ⊂ U | Sąsiedztwo rozwiązania ui |
| Ruch | Działanie: ui → uj ∈ Ui |
Problem: Czysty Local Search (akceptuj tylko poprawę) utyka w lokalnym optimum, które może być dalekie od globalnego. Metaheurystyki rozwiązują ten problem.
Symulowane Wyżarzanie (Simulated Annealing — SA)
Inspirowane procesem wyżarzania kryształów: podgrzewanie (swobodne poruszanie cząsteczek) → powolne chłodzenie → stan minimalnej energii.
Mechanizm akceptacji — rozkład Boltzmanna
\[ P(\text{akceptacja}) = \begin{cases} 1 & Q(u_j) \leq Q(u_i) \\ e^{-\Delta Q / T_k} & Q(u_j) > Q(u_i) \end{cases} \]
Schemat algorytmu SA
u = u₀ // rozwiązanie startowe
T = T₀ // temperatura początkowa
WHILE nie_stop:
FOR k = 1 TO L(T):
u_j = generate_neighbor(u)
ΔQ = Q(u_j) - Q(u)
IF ΔQ ≤ 0 OR rand() < exp(-ΔQ/T):
u = u_j // akceptuj
T = α·T // schładzaj (0.9 ≤ α ≤ 0.99)
RETURN u_best
T = T₀ // temperatura początkowa
WHILE nie_stop:
FOR k = 1 TO L(T):
u_j = generate_neighbor(u)
ΔQ = Q(u_j) - Q(u)
IF ΔQ ≤ 0 OR rand() < exp(-ΔQ/T):
u = u_j // akceptuj
T = α·T // schładzaj (0.9 ≤ α ≤ 0.99)
RETURN u_best
Parametry SA
| Parametr | Rola | Typowe wartości |
|---|---|---|
| T₀ | Temperatura początkowa | P ≈ 0.8 dla typowego ΔQ |
| α | Współczynnik chłodzenia | 0.90–0.99 (geometryczne) |
| L(T) | Długość epoki | Stała lub rosnąca |
| Tmin | Temperatura końcowa | Bardzo niska |
Przeszukiwanie Tabu (Tabu Search — TS)
Deterministyczne przeszukiwanie sąsiedztwa z listą tabu blokującą ostatnio odwiedzane ruchy.
Kluczowe pojęcia
| Pojęcie | Opis |
|---|---|
| Lista tabu (TL) | Zbiór zabronionych ruchów z ostatnich t iteracji |
| Kadencja | Liczba iteracji, przez które ruch jest zakazany |
| Kryterium aspiracji | Ruch tabu dozwolony gdy prowadzi do lepszego niż u_best |
| Intensyfikacja | Koncentracja wokół obiecujących regionów |
| Dywersyfikacja | Wymuszanie eksploracji nowych obszarów |
Schemat algorytmu TS
u = u₀; TL = []
WHILE nie_stop:
cand = generate_neighborhood(u)
FOR u_j IN cand:
IF move(u→u_j) ∉ TL OR aspiration(u_j):
allowed.add(u_j)
u = argmin{Q(u_j) : u_j ∈ allowed}
TL.add(last_move); IF len(TL)>kadencja: TL.pop()
RETURN u_best
WHILE nie_stop:
cand = generate_neighborhood(u)
FOR u_j IN cand:
IF move(u→u_j) ∉ TL OR aspiration(u_j):
allowed.add(u_j)
u = argmin{Q(u_j) : u_j ∈ allowed}
TL.add(last_move); IF len(TL)>kadencja: TL.pop()
RETURN u_best
Typy pamięci w TS
| Typ | Zastosowanie |
|---|---|
| Short-term | Lista tabu — unikanie cykli |
| Intermediate-term | Cechy obiecujących rozwiązań — intensyfikacja |
| Long-term (frequency) | Częstość wizyt w regionach — dywersyfikacja |
Porównanie SA vs TS
| Cecha | SA | TS |
|---|---|---|
| Przeszukiwanie | Losowe | Deterministyczne |
| Ucieczka z lok. optimum | Losowa akceptacja gorszych | Lista tabu wymusza nowe obszary |
| Pamięć | Brak (tylko T) | Short/long-term memory |
| Implementacja | Prosta | Bardziej złożona |
| Zastosowania | TSP, szeregowanie, ciągłe | TSP, szeregowanie, dyskretne |