SA02

151

5.1. Symulowane wyżarzanie

chastyczna czy probabilistyczny algorytm wymiany, jest oparte na analogii zaczerpniętej z termodynamiki. Żeby wyhodować kryształ, ogrzewa się najpierw szereg materiałów do stanu ciekłego. Następnie obniża się temperaturę tego kryształowego wytopu dopóty, dopóki struktura kryształu nie zostanie zamrożona. Niedobrze jest, jeśli chłodzenie postępuje zbyt szybko. W strukturze kryształu pojawiają się pewne nieregularności. a poziom uwięzionej energii jest znacznie wyższy niż w idealnie uformowanym krysztale¹. Analogia między tym fizycznym procesem a problemem optymalizacji powinna być oczywista. Podstawowe „odpowiadające sobie*’ pojęcia są wymienione w tab. 5.3.

Tabela 5.3. Analogie między procesem fizycznym a problemem optymalizacji

Proces fizyczny	Problem optymalizacji
stan energia stan kryształu szybkie schładzanie temperatura ostrożne wyżarzanie	dopuszczalne rozwiązanie funkcja oceny optymalne rozwiązanie poszukiwanie lokalne parametr sterujący T symulowane wyżarzanie

Podobnie jak w wypadku dowolnego algorytmu poszukiwania, symulowane wyżarzanie wymaga znalezienia odpowiedzi na następujące pytania, bezpośrednio związane z rozważanym problemem (zob. rozdział 2):

•    Jakie jest rozwiązanie?

•    Jacy są sąsiedzi rozwiązania?

•    Jaki jest koszt rozwiązania?

•    Jak ustalić początkowe rozwiązanie?

Odpowiedzi na te pytania dostarczają nam strukturę przestrzeni przeszukiwania wraz z definicją otoczenia, funkcję oceny oraz punkt początkowy. Zauważmy jednak, że symulowane wyżarzanie wymaga także odpowiedzi na dodatkowe pytania:

•    Jak ustalić początkową „temperaturę” T?

•    Jak ustalić współczynnik schładzania g(T,t)7

•    Jak ustalić warunek zakończenia iteracji?

•    Jak ustalić kryterium zatrzymania algorytmu?

Temperatura początkowa T musi być ustalona przed wykonaniem procedury. Czy powinniśmy zacząć od T — 100, T — 1000, czy może od jeszcze innej wartości? W jaki sposób powinniśmy ustalić warunek zakończenia iteracji, po którym temperatura maleje i procedura wyżarzania powtarza się? Czy powinniśmy wykonać pewną liczbę iteracji, czy zastosować w zamian jakieś inne kryterium?

'Podobny problem występuje w metalurgii podczas ogrzewania i schładzania

metali.