Symulowane wyżarzanie

Do czytelników : artykuł ten jest głównie adresowany do kolegów i koleżanek z kierunku, jednak powinien zainteresować każdego szukającego informacji o tym algorytmie metaheurystycznym.

Jako że wczoraj nie poszedłem na wykład dr. Cabana z systemów operacyjnych i męczą mnie z tego powodu wyrzuty sumienia, postanowiłem swój czas poświęcić na czyn społeczny i napisać krótki, acz konkretny artykuł na temat symulowanego wyżarzania. Przedstawione tutaj informacje będą trochę miksem notatek z wykładu dr. Kozika i moich własnych doświadczeń.

Algorytm symulowanego wyżarzania jest algorytmem wyszukującym przybliżone rozwiązanie konkretnej instancji jakiegoś problemu NP-trudnego. Jak wie każdy mniej więcej ogarnięty, przestrzeń możliwych rozwiązań problemów NP-trudnych jest z reguły na tyle duża, że odpada jej dokładne przebadanie, tj. sprawdzanie każdego możliwego rozwiązania po kolei. Dla problemu komiwojażera na przykład mamy \frac{(n-1)!}{2} rozwiązań, co już dla 20 miast daje liczbę na tyle dużą, że wykonanie takiego algorytmu zajmie niewiarygodnie dużo czasu. Wykorzystując algorytmy przybliżone jesteśmy w stanie znaleźć rozwiązanie, które może i nie będzie najlepszym (optymalnym), jednak będzie „wystarczająco dobrym”, a do tego zostanie ono znalezione w czasie w miarę rozsądnym.

Algorytmy metaheurystyczne zawsze działają inaczej, ponieważ w swoim działaniu opierają się na losowości – najbardziej ogólny algorytm metaheurystyczny będzie wyglądał tak :

while(i < limit_iteracji)
{
	wylosuj nowe rozwiązanie;
	jeśli jest lepsze od poprzednio wylosowanego, zapisz je;
	++i;
}

Taki „naiwny” algorytm jednak działa bardzo kiepsko, ponieważ za każdym razem przeskakuje w zupełnie inny punkt obszaru możliwych rozwiązań, a możliwe jest, że jeśli jesteśmy w jakimś punkcie, to rozwiązanie, które będzie od niego lepsze znajduje się zaraz obok niego – dlatego zdefiniujemy coś takiego jak otoczenie rozwiązania jako rozwiązanie mu sąsiadujące na przykład przez zamieniony jeden element. Czyli sąsiedztwem permutacji { 3, 7, 1, 2, 4, 5, 6 } może być permutacja { 3, 7, 1, 4, 2, 5, 6 }. Pierwszym pomysłem powinno być, by algorytm dostawał „jakieś” rozwiązanie początkowe (chociażby wylosowane) i działał tak długo, aż w sąsiedztwie nie znajdują się żadne lepsze rozwiązania. Jest z tym związany jeden mankament – aby to zobrazować, powiedzmy, że chcemy zminimalizować poniższą funkcję na obszarze ograniczonym wykresem.

Na pierwszy rzut oka widać, że funkcja ma globalne minimum w x=1 i lokalne minimum w okolicach x=-0.8. Jeśli rozwiązaniem początkowym naszego algorytmu będzie na przykład x = -0.25, to nie ma możliwości, by kiedykolwiek dotarł on do globalnego minimum, ponieważ nigdy nie będzie się ono znajdowało w sąsiedztwie badanego rozwiązania.

Modyfikacją takiego „naiwnego” algorytmu jest właśnie symulowane wyżarzanie, w którym zezwalamy na zmianę rozwiązania z pewnym prawdopodobieństwem, nawet wtedy, gdy jest ono gorsze – bo możliwe, że w sąsiedztwie gorszego będą lepsze niż te, które mamy w sąsiedztwie rozwiązania aktualnie rozpatrywanego. Dzięki temu symulowane wyżarzanie potrafi „unikać” problemów minimum lokalnego. Poza tym, cytując dr. Kozika „Własność losowości jest taka, że po pewnym czasie daje dobre wyniki”, co tutaj ma chyba jakiś sens.

Algorytm cechuje się następującymi parametrami :

  • początkową temperaturą T,
  • końcową temperaturą Tmin,
  • funkcją prawdopodobieństwa P,
  • funkcją obniżania temperatury G.

Funkcja prawdopodobieństwa określa, z jakim prawdopodobieństwem będziemy zmieniać rozwiązanie na gorsze. W „oryginalnej” odmianie symulowanego wyżarzania funkcja ta była zależna od oceny rozwiązania nowego, starego i aktualnej temperatury. Bierze się to z analogii tego algorytmu do procesu metalurgicznego – póki temperatura jest wysoka, akceptujemy zmiany na rozwiązania początkowo gorsze, ale potencjalnie lepsze. Zakładamy, że w miarę postępowania algorytmu i obniżania temperatury dojdziemy do rozwiązania „w miarę dobrego”, tak więc „ryzykowne” zmiany na rozwiązania początkowo gorsze nie będą już potrzebne. Z tego wynika też funkcja obniżania temperatury – wykonywana jest ona po każdej iteracji algorytmu i w oryginalnej odmianie była zależna od aktualnej temperatury i aktualnego numeru iteracji.

Po przeczytaniu tego wszystkiego poniższy pseudokod powinien być w miarę oczywisty.

i = 0
wybierz losowo rozwiązanie A
while(T > Tmin)
{
	stwórz rozwiązanie B przez zamianę dwóch losowych elementów w A
	if(Kryterium(B) < Kryterium(A)) A = B
	else if(random(0,1) < P()) A = B
	T = G()
	i = i+1
}

Jak widać, sama idea algorytmu jest bardzo prosta, jeszcze prostsze jest to, jak to zastosować w przypadku problemów przez nas rozpatrywanych – zarówno w przypadku komiwojażera, jak i szeregowania wystarczy po prostu zamienić ze sobą dwa elementy aktualnie rozpatrywanej permutacji i przeliczyć dla nich kryterium. I to wszystko.

Jedynym problemem jest dobranie funkcji P i G tak, aby algorytm dawał dobre rozwiązania. W przypadku P odpowiedź jest prosta :

P = e^{-\frac{f(S') - f(S)}{T}}

Zakładając, że e to stała Eulera, f() to funkcja określająca kryterium rozwiązania, S’ to „nowe” rozwiązanie, S to „stare” rozwiązanie, a T to aktualna temperatura. Natomiast funkcja G :

G = \frac{\Gamma}{\log(k + k_0)} lub G = \alpha T_k

Gdzie gamma, alpha i k0 to „jakieś stałe” (twierdzenie, z którego pochodzi ten wzór mówi tylko tyle, że „istnieją”), k to aktualna iteracja algorytmu, a Tk to aktualna temperatura.

Dla zainteresowanych jako „further reading” polecam :

Mam nadzieję, że coś rozjaśniłem. Proszę rzucać pytania, jeśli się pojawią.

Informacje o Daniel

freezingly cold soul
Ten wpis został opublikowany w kategorii komputer. Dodaj zakładkę do bezpośredniego odnośnika.

8 odpowiedzi na „Symulowane wyżarzanie

  1. fleg pisze:

    http://s.fl9.eu/7 – masz, podgoń sobie z systemów :D i dzięki za wpis.

  2. Moojziak pisze:

    Ten artykul jest bardzo dobry :), rozjasnil mi i stwierdzam ze to banal jest!!

    z tym ze Xav, jak rozstrzygnoles problem „istniejacych” stalych funkcji G?

  3. marverix pisze:

    nie wiem czy wiesz, ale jesteś na 1. stronie Google jak wpiszesz „symulowane wyżarzanie” lol

  4. Dominik pisze:

    Dzięki za rozjaśnienie tematu, bo wcześniej czytałem dwa inne artykuły i nie mogłem zczaić za bardzo tego algorytmu.

  5. Jakub pisze:

    Witam. Chciałem zaprosić na mojego devbloga, gdzie opisałem symulowane wyżarzanie dla problemów dyskretnych:
    http://jakubniwa.pl/PL/artykuly/Ewolucja%20metod%20Hill%20Climbing%20-%3E%20Settled%20Hill%20Climbing%20-%3E%20Simmulated%20Annealing

  6. sprzedamsanki pisze:

    Wykres dupa.png rządzi :D

  7. Primosz pisze:

    Świetny, zwięzły i łopatologiczny opis! Tego szukałem.

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s