Symulowane wyżarzanie

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

Algorytm

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

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

Zobacz też

  • algorytm ewolucyjny
  • sztuczna inteligencja
  • sztuczne życie

Linki zewnętrzne

  • Wykonanie przykładowego algorytmu krok po kroku