SA01

150

5. Unikanie lokalnych optimów

5.1. Symulo*

Tabela 5.2. Prawdopodobieństwo akceptacji jako funkcja eval{v_n) dla T = 10 i eval(v_c) = 107

eval{wn)	eval(vc) — eval(vn)	eval{vc.) — eval(-v.n)	P
		e io
80	27	14,88	0,06
100	7	2,01	0,33
107	0	1,00	0,50
120	-13	0,27	0,78
150	-43	0,01	0,99

Główną różnicą między stochastycznym wspinaniem się a symulowanym wyżarzaniem jest to, że druga z tych metod zmienia parametr temperatury T w trakcie działania. Rozpoczyna się ona z dużą wartością T, co czyni procedurę zbliżoną do czysto losowego poszukiwania, a następnie stopniowo obniża wartość T. Pod koniec działania wartości T są całkiem małe, więc ostatnie etapy symulowanego wyżarzania przypominają zwyczajne wspinanie się. Co więcej, zawsze akceptujemy nowe punkty, jeśli są one lepsze od punktu bieżącego. Procedurę symulowanego wyżarzania pokazano na rys. 5.3 (ponownie założyliśmy, że mamy do czynienia z problemem maksymalizacji).

procedurę symulowane wyżarzanie begin t<- 0 inicjuj T

wybierz losowo bieżący punkt v_c oceń v_c repeat repeat

wybierz nowy punkt v_n w otoczeniu v_c if eval(v_c) < eval(v_n) then v_c v_ri

eval(v_n)-cval(v_c)

else ii ranaom[0,1) < e t then v_c v_n

until (warunek zakończenia)

T <— g(T,t) t*-t + l

until (kryterium zatrzymania) end

Rysunek 5.3. Struktura symulowanego wyżarzania

Symulowane wyżarzanie, znane również jako wyżarzanie typu Monte Carlo, schładzanie statystyczne, probabilistyczne wspinanie się, relaksacja sto-

chastyczna < zaczerpnięty pierw szereg tego bryt ri mrożona. N kryształu < znacznie fizycznym : stawowe .. *

Tabela 5.3

Pr o

stan

enerj

star.

szyb

temp

ostr D

Pod q : ne wyżarz średnio z a

•    Jak

•    J ay

•    Jajn

•    Jak

Odpowie id nia wraz z 1 jednak, że si tania:

•    Jak

•    -Jak

•    Jak

•    Jak

Temper;-.' i Czy powinn ści? W jak: temperatur J konać pewni

¹P<

metali.