Symulowane wyżarzanie

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Symulowane wyżarzanie to rodzaj algorytmu heurystycznego przeszukującego przestrzeń alternatywnych rozwiązań problemu w celu wyszukania rozwiązań najlepszych. Sposób działania symulowanego wyżarzania nieprzypadkowo przypomina zjawisko wyżarzania w metalurgii.

Algorytm[edytuj | edytuj kod]

Kroki algorytmu w klasycznym podejściu podczas minimalizacji funkcji  \displaystyle F(w)

  1. Losowy wybór punktu startowego \displaystyle w. Przyjęcie temperatury \displaystyle T=T_{max},
  2. Wyznaczenie wartości funkcji \displaystyle F(w) w punkcie \displaystyle w,
  3. Wyznaczenie \displaystyle w' = w + \Delta w, gdzie \displaystyle \Delta w jest realizacją zmiennej losowej o rozkładzie normalnym z medianą w punkcie \displaystyle \Delta w i średnią wariancją równą \displaystyle T ,
  4. Wyznaczenie wartości funkcji \displaystyle F(w') w nowym punkcie,
  5. Podstawienie wartości  \displaystyle w' do  \displaystyle w z prawdopodobieństwem danym rozkładem Boltzmanna \displaystyle b(E(w')-E(w),T),
  6. Zmniejszenie temperatury \displaystyle T=nT, gdzie  \displaystyle n jest stałą z przedziału  \displaystyle (0,1),
  7. Spełnienie kryterium stopu lub powrót do kroku 3.

Zobacz też[edytuj | edytuj kod]