73051 stat Paget resize

74

5.2 Zagadnienie optymalizacji metodą MC

Najprostszym rozwiązaniem problemu (5.10) przy założeniu zwartości przestrzeni stanów X jest wygenerowanie próby Xo, X\,X2,..., X_n z rozkładu jednostajnego na X. Wtedy trywialny estymator

h_mAX = max {k(Xi)}    (5-11)

jest naturalnym estymatorem rozwiązania dla zadania optymalizacji (5.10).

Oczywiście także i dla problemu (5.10), podobnie jak dla problemu całkowania funkcji, możliwe jest zastosowanie szeroko znanych, deterministycznych metod numerycznych (chociażby np. metody Newtona, metody siecznych czy ich uogólnień). Jednak jeśli rozpatrywana funkcja k(x) posiada kilka maksimów lokalnych, zastosowanie metody deterministycznej może zaowocować „uwięźnię-ciem” algorytmu, tzn. znalezieniem tylko jednego z ekstremów lokalnych, a nie prawdziwego maksimum globalnego. Ponadto w przypadku deterministycznych metod numerycznych częstokroć konieczne są dodatkowe założenia co do szczególnych własności funkcji h(x), jak np. jej różniczkowalność, lub co do odpowiednio regularnej postaci jej dziedziny X.

Remedium na takie problemy może być zastosowanie metody MC zwanej symulowanym wyżarzaniem (w j. ang. simidated annealing) z modyfikacją zaproponowaną przez Metropolisa.

Metoda ta wymaga wprowadzenia dodatkowej zmiennej skalującej T > 0, tradycyjnie nazywanej temperaturą, ze względu na historyczne zastosowania symulowanego wyżarzania w fizyce. Startując z pewnej wartości xo, metoda polega na generacji kolejnych wartości X_n z wykorzystaniem następującego algorytmu:

1.    Wylosuj proponowaną wartość Y_n z pewnego rozkładu prawdopodobieństwa na otoczeniu wartości poprzedniego kroku X_n-\ = x_n_i, np. z rozkładu jednostajnego na otoczeniu tego punktu. W ogólności losowanie nastąpić może z dowolnego rozkładu o gęstości postaci <?(|x_n_ i — Yi,|)).

2.    Wybierz kolejny punkt X_n według następującego przepisu:

x_n= ^Yn z prawd, p — rain{exp(A/ł/7'),l} x_n_i z prawd. 1 — p

gdzie Ah = k(Y_n) - h(x_n-i).

Jak widzimy z (5.12), jeśli funkcja h(x) ma większą wartość w nowo wylosowanym punkcie Y_n, to zostanie on na pewno zaakceptowany i stanie się zmienną X_n. Jednocześnie, nawet gdy wartość funkcji jest niższa w nowym punkcie Y_n, to punkt ten może zostać zaakceptowany na X_n z niezerowym prawdopodobieństwem p = exp(A/i/T). Umożliwia to ucieczkę z ewentualnego maksimum lokalnego i daje szansę na znalezienie maksimum globalnego.

Powyższy algorytm jest zazwyczaj implementowany z dodatkowym warunkiem monotonicznej zbieżności T —► 0. Zmniejszanie się parametru temperatury ma celu stopniowe „zamrażanie” kroków algorytmu, który najpierw szybko przeszukuje całą dziedzinę, aby stopniowo zatrzymać się w ekstemum. Jak z tego wynika, na odpowiednie zachowanie się procedury, a więc i na znalezienie z dużym prawdopodobieństwem globalnego ekstremum, olbrzymi wpływ ma sposób zbiegania parametru temperatury T do zera.