Symulowane wyżarzanie

Tutorial
Na ten temat mamy również tutorial „Symulowane wyżarzanie”, który ilustruje działanie algorytmu krok po kroku. Zapraszamy do zapoznania się z nim!
REKLAMA

Testowanie full stack. Praktyczny przewodnik dostarczania oprogramowania wysokiej jakości
−36%56,96 zł
Algorytmy bez tajemnic
−38%33,49 zł

Symulowane wyżarzanie – jedna z technik projektowania algorytmów heurystycznych (metaheurystyka). Cechą charakterystyczną tej metody jest występowanie parametru sterującego zwanego temperaturą, który maleje w trakcie wykonywania algorytmu. Im wyższą wartość ma ten parametr, tym bardziej chaotyczne mogą być zmiany. Podejście to jest inspirowane zjawiskami obserwowanymi w metalurgii – im większa temperatura metalu, tym bardziej jest on plastyczny.

Jest to metoda iteracyjna: najpierw losowane jest pewne rozwiązanie, a następnie jest ono w kolejnych krokach modyfikowane. Jeśli w danym kroku uzyskamy rozwiązanie lepsze, wybieramy je zawsze. Istotną cechą symulowanego wyżarzania jest jednak to, że z pewnym prawdopodobieństwem może być również zaakceptowane rozwiązanie gorsze (ma to na celu umożliwienie wyjście z maksimum lokalnego).

Prawdopodobieństwo przyjęcia gorszego rozwiązania wyrażone jest wzorem e(f(X)−f(X'))/T (rozkład Boltzmanna), gdzie X jest poprzednim rozwiązaniem, X' nowym rozwiązaniem, a f funkcją oceny jakości – im wyższa wartość f(X), tym lepsze rozwiązanie. Ze wzoru można zauważyć, że prawdopodobieństwo przyjęcia gorszego rozwiązania spada wraz ze spadkiem temperatury i wzrostem różnicy jakości obu rozwiązań.

Opis algorytmu

Przez rozpoczęciem wykonywania algorytmu należy ustalić:

  • Początkową wartość temperatury T.
  • Sposób obniżania temperatury – często stosowanym rozwiązaniem jest mnożenie aktualnej temperatury przez pewien współczynnik, zazwyczaj mieszczący się w przedziale [0,8; 0,99].
  • Liczbę prób przeprowadzanych w ramach jednej epoki (z tą samą temperaturą).
  • Sposób wyboru nowego rozwiązania w ramach pojedynczej próby. Nowe rozwiązanie powinno znajdować się w pobliżu aktualnego. Przy wyznaczeniu nowego rozwiązania można wziąć pod uwagę aktualną temperaturę – im wyższa, tym bardziej nowe i aktualne rozwiązanie mogą się od siebie różnić.
  • Warunek stopu – może to być np. osiągnięcie określonej liczby epok lub odpowiednio mała zmiana rozwiązania w trakcie ostatnio wykonanych epok.

Działanie algorytmu można opisać następująco:

  1. Wylosuj rozwiązanie początkowe X.
  2. Wybierz losowe rozwiązanie X' znajdujące się w pobliżu X.
  3. Jeśli nowe rozwiązanie jest lepsze, przyjmij je (X=X'). W przeciwnym razie, wyznacz prawdopodobieństwo przyjęcia nowego rozwiązania używając wzoru e(f(X)−f(X'))/T. Następnie wylosuj liczbę z przedziału [0,1] i jeśli jest ona mniejsza od obliczonego prawdopodobieństwa, przyjmij nowe rozwiązanie (pomimo tego, że jest gorsze).
  4. Jeśli nie wykonano jeszcze odpowiedniej liczby prób w obrębie danej epoki, wróć do punktu 2.
  5. Zmniejsz temperaturę.
  6. Jeśli nie osiągnięto jeszcze warunku stopu, wróć do punktu 2.

Dodatkowe uwagi

Symulowane wyżarzanie jest metaheurystyką, zatem nie jest to szczegółowo opisany algorytm, a jedynie ogólna koncepcja. W zależności od problemu do rozwiązania, poszczególne elementy algorytmu mogą być zdefiniowane różnie. Przykładowo, przy rozwiązywaniu problemu komiwojażera pobliskim rozwiązaniem może być zamiana miejscami dwóch węzłów. Odległość między aktualnym a nowym rozwiązaniem w takim przypadku nie musi zależeć od temperatury.

Bibliografia

  • A. Debudaj-Grabysz, S. Deorowicz, J. Widuch, Algorytmy i struktury danych. Wybór zaawansowanych metod, Wydawnictwo Politechniki Śląskiej, Gliwice, 2012, ISBN 9788373359383.
Ocena: +5 Tak Nie
Liczba głosów: 9.

Dodano: 20 kwietnia 2020 19:53, ostatnia edycja: 6 maja 2020 19:25.

REKLAMA

Zobacz też

Metoda przyrostowa – technika projektowania algorytmów polegająca na dodawaniu do rozwiązania kolejnych elementów z danych wejściowych. Przykładem algorytmu opartego na tej metodzie jest sortowanie przez wstawianie, gdzie kolejne elementy są wstawiane do posortowanej części tablicy.

Jest to metoda prosta, jednak sprawdza się tylko dla niektórych problemów obliczeniowych.

→ Czytaj całość

Metoda Otsu – algorytm służący do binaryzacji obrazu, czyli przekształcenia obrazu w odcieniach szarości do obrazu binarnego. Metoda ta realizuje progowanie globalne – dla całego obrazu wyznaczany jest jeden próg jasności, a następnie wszystkim pikselom jaśniejszym od tego progu przypisywana jest jedna wartość, a ciemniejszym druga.

Algorytm jest oparty na analizie histogramu. Przygotowanie histogramu polega na zliczeniu pikseli w każdym możliwym odcieniu (zazwyczaj liczba odcieni wynosi 256, gdyż tyle da się zakodować w jednym bajcie). Następnie należy sprawdzić każdy możliwy próg jasności i wybrać ten, dla którego wariancja międzyklasowa jest największa (lub suma ważona wariancji wewnątrzklasowych jest najmniejsza).

Jeśli obrazem wejściowym jest obraz kolorowy, można go łatwo sprowadzić do odcieni szarości. W przypadku kolorów zakodowanych w RGB najprostszym rozwiązaniem jest uśrednienie dla każdego piksela wartości wszystkich trzech kanałów.

→ Czytaj całość

Algorytm Johnsona – algorytm służący do wyznaczania najkrótszych ścieżek pomiędzy każdą parą wierzchołków w grafie. Algorytm wykorzystuje algorytm Dijkstry i algorytm Bellmana-Forda. Dopuszcza krawędzie o ujemnych wagach, o ile nie tworzą ujemnych cykli.

Złożoność czasowa algorytmu (jeśli algorytm Dijkstry zostanie zaimplementowany z wykorzystaniem kopca Fibonacciego) to O(n2log n + en), gdzie n jest liczbą wierzchołków, a e jest liczbą krawędzi. Dla grafów rzadkich (ze stosunkowo małą liczbą krawędzi) jest to złożoność lepsza, niż złożoność algorytmu Floyda-Warshalla.

→ Czytaj całość
Polityka prywatnościKontakt