Symulowane wyżarzanie
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:
- Wylosuj rozwiązanie początkowe X.
- Wybierz losowe rozwiązanie X' znajdujące się w pobliżu X.
- 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).
- Jeśli nie wykonano jeszcze odpowiedniej liczby prób w obrębie danej epoki, wróć do punktu 2.
- Zmniejsz temperaturę.
- 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.
Liczba głosów: 5.
- Algorytmy genetyczne
- Algorytmy memetyczne
- Algorytmy zachłanne
- Symulowane wyżarzanie
Dodano: 20 kwietnia 2020 19:53, ostatnia edycja: 6 maja 2020 19:25.
Zobacz też
Programowanie dynamiczne – technika projektowania algorytmów polegająca na rozwiązywaniu podproblemów i zapamiętywaniu ich wyników. W technice tej, podobnie jak w metodzie dziel i zwyciężaj, problem dzielony jest na mniejsze podproblemy. Wyniki rozwiązywania podproblemów są jednak zapisywane w tabeli, dzięki czemu w przypadku natrafienia na ten sam podproblem nie trzeba go ponownie rozwiązywać.
Wykorzystując programowanie dynamiczne można zastosować metodę zstępującą z zapamiętywaniem lub metodę wstępującą.
- Metoda zstępująca z zapamiętywaniem polega na rekurencyjnym wywoływaniu funkcji z zapamiętywaniem wyników. Metoda ta jest podobna do metody dziel i zwyciężaj – różni się od niej tym, że jeśli rozwiązanie danego problemu jest już w tabeli z wynikami, to należy je po prostu stamtąd odczytać.
- Metoda wstępująca polega na rozwiązywaniu wszystkich możliwych podproblemów, zaczynając od tych o najmniejszym rozmiarze. Wówczas w momencie rozwiązywania podproblemu na pewno są już dostępne rozwiązania jego podproblemów. W tym podejściu nie zużywa się pamięci na rekurencyjne wywołania funkcji. Może się jednak okazać, że część podproblemów została rozwiązana nadmiarowo (nie były one potrzebne do rozwiązania głównego problemu).
Algorytmy zachłanne (ang. greedy algorithms) – algorytmy podejmujące w każdym kroku taką decyzję, która w danej chwili wydaje się najkorzystniejsza. Inaczej mówiąc, algorytmy zachłanne dokonują zawsze wyborów lokalnie optymalnych licząc, że doprowadzi to do znalezienia rozwiązania globalnie optymalnego. W ogólnym przypadku algorytmy zachłanne nie zawsze znajdują rozwiązanie optymalne. Są one zatem podzbiorem algorytmów heurystycznych. Jednocześnie są to algorytmy deterministyczne – nie ma w nich losowości.
Bardzo prostym przykładem algorytmu zachłannego może być szukanie najwyższego punktu na określonym obszarze poprzez przesuwanie się zawsze w kierunku największego nachylenia (nigdy się nie cofając ani nie rozpatrując kilku wariantów drogi). Jak widać, w ten sposób prawdopodobnie dojdziemy do wierzchołka położonego najbliżej od punktu początkowego, który niekoniecznie będzie najwyższym.
Algorytm Bellmana-Forda – algorytm służący do wyznaczania najkrótszych ścieżek w grafie. Wyznacza najkrótsze ścieżki z jednego wierzchołka (zwanego wierzchołkiem źródłowym) do pozostałych wierzchołków. W odróżnieniu od algorytmu Dijkstry, algorytm Bellmana-Forda dopuszcza krawędzie o ujemnych wagach, nie mogą istnieć jednak ujemne cykle osiągalne z wierzchołka źródłowego. Algorytm może być również wykorzystywany do sprawdzania, czy w grafie występują ujemne cykle.
Algorytm występuje również pod nazwą algorytm Bellmana-Forda-Moore’a.