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]

Kroki algorytmu w klasycznym podejściu podczas minimalizacji funkcji

  1. Losowy wybór punktu startowego . Przyjęcie temperatury ,
  2. Wyznaczenie wartości funkcji w punkcie ,
  3. Wyznaczenie , gdzie jest realizacją zmiennej losowej o rozkładzie normalnym z medianą w punkcie i średnią wariancją równą ,
  4. Wyznaczenie wartości funkcji w nowym punkcie,
  5. Podstawienie wartości do z prawdopodobieństwem danym rozkładem Boltzmanna ,
  6. Zmniejszenie temperatury , gdzie jest stałą z przedziału ,
  7. Spełnienie kryterium stopu lub powrót do kroku 3.

Zobacz też[edytuj]