Symulowane wyżarzanie – jedna z technik projektowania algorytmów heurystycznych (metaheurystyka). Cechą charakterystyczną tej metody jest występowanie parametru sterującego zwanego temperaturą, który maleje w trakcie wykonywania algorytmu. Im wyższą wartość ma ten parametr, tym bardziej chaotyczne mogą być zmiany. Podejście to jest inspirowane zjawiskami obserwowanymi w metalurgii – im większa temperatura metalu, tym bardziej jest on plastyczny.

Jest to metoda iteracyjna: najpierw losowane jest pewne rozwiązanie, a następnie jest ono w kolejnych krokach modyfikowane. Jeśli w danym kroku uzyskamy rozwiązanie lepsze, wybieramy je zawsze. Istotną cechą symulowanego wyżarzania jest jednak to, że z pewnym prawdopodobieństwem może być również zaakceptowane rozwiązanie gorsze (ma to na celu umożliwienie wyjście z maksimum lokalnego).

Prawdopodobieństwo przyjęcia gorszego rozwiązania wyrażone jest wzorem e^{(f(X)−f(X'))/T} (rozkład Boltzmanna), gdzie X jest poprzednim rozwiązaniem, X' nowym rozwiązaniem, a f funkcją oceny jakości – im wyższa wartość f(X), tym lepsze rozwiązanie. Ze wzoru można zauważyć, że prawdopodobieństwo przyjęcia gorszego rozwiązania spada wraz ze spadkiem temperatury i wzrostem różnicy jakości obu rozwiązań.

REKLAMA

Opis algorytmu

Przez rozpoczęciem wykonywania algorytmu należy ustalić:

• Początkową wartość temperatury T.
• Sposób obniżania temperatury – często stosowanym rozwiązaniem jest mnożenie aktualnej temperatury przez pewien współczynnik, zazwyczaj mieszczący się w przedziale [0,8; 0,99].
• Liczbę prób przeprowadzanych w ramach jednej epoki (z tą samą temperaturą).
• Sposób wyboru nowego rozwiązania w ramach pojedynczej próby. Nowe rozwiązanie powinno znajdować się w pobliżu aktualnego. Przy wyznaczeniu nowego rozwiązania można wziąć pod uwagę aktualną temperaturę – im wyższa, tym bardziej nowe i aktualne rozwiązanie mogą się od siebie różnić.
• Warunek stopu – może to być np. osiągnięcie określonej liczby epok lub odpowiednio mała zmiana rozwiązania w trakcie ostatnio wykonanych epok.

Działanie algorytmu można opisać następująco:

1. Wylosuj rozwiązanie początkowe X.
2. Wybierz losowe rozwiązanie X' znajdujące się w pobliżu X.
3. Jeśli nowe rozwiązanie jest lepsze, przyjmij je (X=X'). W przeciwnym razie, wyznacz prawdopodobieństwo przyjęcia nowego rozwiązania używając wzoru e^{(f(X)−f(X'))/T}. Następnie wylosuj liczbę z przedziału [0,1] i jeśli jest ona mniejsza od obliczonego prawdopodobieństwa, przyjmij nowe rozwiązanie (pomimo tego, że jest gorsze).
4. Jeśli nie wykonano jeszcze odpowiedniej liczby prób w obrębie danej epoki, wróć do punktu 2.
5. Zmniejsz temperaturę.
6. Jeśli nie osiągnięto jeszcze warunku stopu, wróć do punktu 2.

Dodatkowe uwagi

Symulowane wyżarzanie jest metaheurystyką, zatem nie jest to szczegółowo opisany algorytm, a jedynie ogólna koncepcja. W zależności od problemu do rozwiązania, poszczególne elementy algorytmu mogą być zdefiniowane różnie. Przykładowo, przy rozwiązywaniu problemu komiwojażera pobliskim rozwiązaniem może być zamiana miejscami dwóch węzłów. Odległość między aktualnym a nowym rozwiązaniem w takim przypadku nie musi zależeć od temperatury.

REKLAMA

Bibliografia

• A. Debudaj-Grabysz, S. Deorowicz, J. Widuch, Algorytmy i struktury danych. Wybór zaawansowanych metod, Wydawnictwo Politechniki Śląskiej, Gliwice, 2012, ISBN 9788373359383.