SA03

152

5. Unikanie lokalnych optimów

Poza tym. jak bardzo czy też o ile powinna zmaleć temperatura? O jeden procent. a może mniej? I wreszcie, kiedy algorytm powinien się zatrzymać, tzn. jaka jest temperatura zamrażania?

W większości implementacji symulowanego wyżarzania jest stosowana prosta sekwencja kroków:

KROK 1: T <— T_max

wybierz losowo v_r:

KROK 2: wybierz punkt v_n z otoczenia v_c if eval(v_n) jest lepsze od eval{y_c)

then wybierz ten punkt (v_c v_n) else wybierz go z prawdopodobieństwem e ń repeat ten krok k,T razy

KROK 3: ustaw T <— rT if T ^ T_rni_n

then goto KROK 2 else goto KROK 1

Musimy ustalić wartości parametrów T_max. k?, r i T_mi_n, które oznaczają odpowiednio: temperaturę początkową, liczbę iteracji, współczynnik schładzania i temperaturę zamrażania. Zbadajmy kilka możliwości, stosując metodę symulowanego wyżarzania kolejno do SAT, TSP i NLP.

Spears [444] zastosował symulowane wyżarzanie (ang. simulated anne-aling - SA) do trudnych problemów spełnialności. Procedurę SA-SAT opisaną w [444] przedstawiono na rys. 5.4. Jej struktura sterująca jest podobna do tej z GSAT (rozdział 3). Zmienna „t.ries” sterująca zewnętrzną pętlą SA-SAT odpowiada zmiennej i w GSAT (zob. rys. 3.5 w rozdziale 3). Zmienne te uaktualniają na bieżąco liczbę niezależnych prób rozwiązania problemu. Na początku każdej próby w SA-SAT wartość T jest ustawiana na T_rnax (ponieważ zmienna j jest ustawiona na zero) i jest losowane nowe przypadkowe wartościowanie boolowskie. Wewnętrzna pętla repeat wypróbowuje różne podstawienia przez probabilistyczne przełączanie zmiennych boolowskich. Prawdopodobieństwo przełączenia zależy od bieżącej temperatury i od ulepszenia ń, jakie daje to przełączenie. Jak zwykle, jeśli ulepszenie jest ujemne, istnieje mała szansa, że przełączenie zostanie zaakceptowane, i odwrotnie: dodatnie ulepszenie zwiększa prawdopodobieństwo akceptacji przełączenia.

Istnieje zasadnicza różnica między GSAT a SA-SAT, będąca podstawową różnicą między lokalnym poszukiwaniem a symulowanym wyżarzaniem: GSAT może wykonać ruch wstecz (tzn. zmniejszenie liczby spełnionych klauzul), jeśli inne ruchy nie są możliwe. Jednocześnie jednak GSAT nie może wykonać dwóch ruchów wstecz z rzędu, gdyż jeden ruch wstecz zakłada istnienie kolejnego ruchu ulepszającego! SA-SAT z kolei może wykonać dowolny ciąg ruchów wstecz, może więc unikać lokalnych optimów!

Pozostałe parametry SA-SAT mają takie samo znaczenie jak w innych implementacjach symulowanego wyżarzania. Parametr r wyraża szybkość spa-