Jan Kazimirski

Celem globalnej minimalizacji jest znalezienie najniższej wartości funkcji (globalnego minimum) w obecności wielu innych minimów lokalnych. Podobny problem polegający na znalezieniu wartości najwyższej (maksimum globalne) może być łatwo przekształcony w minimalizację. Problemy tego typu generalnie określane są jako Problemy Optymalizacji Globalnej (ang. Global Optimization Problems - GOP). Możemy je znaleźć w wielu dziedzinach nauki i inżynierii. Przykłady zastosowania GOP obejmują chemię i fizykę obliczeniową, biologię molekularną, projektowanie leków, planowanie struktur sieci komputerowych i przesyłowych, logistykę, a także zagadnienia z ekonomii i finansów.

Wśród metod szukania minimum globalnego możemy rozróżnić dwie grupy: metody deterministyczne i stochastyczne. Przykładami metod deterministycznych są techniki wyliczeniowe, metody podziału płaszczyzny, analiza interwałowa, metody siatki i inne. Metody te zwykle gwarantują znalezienie najlepszego rozwiązania, jednak ich praktyczne zastosowanie ogranicza się do problemów o niewielkich rozmiarach i specyficznych własnościach.

Druga grupa metod rozwiązywania GOP wykorzystuje algorytmy stochastyczne. Metody te nie gwarantują znalezienia optymalnego minimum, ale mogą zlokalizować sub-optymalne rozwiązania bardzo bliskie do minimum globalnego. Z drugiej strony metody te mogą być stosowane do znacznie bardziej złożonych problemów, które ze względu na rozmiar lub/i własności nie mogą być rozwiązywane metodami deterministycznymi. Przykładami metod stochastycznych są różnorodne metody Monte Carlo (MC), Symulowane wyżarzanie (SA), algorytmy genetyczne i inne metody ewolucyjne.

W ramach moich badań rozwijam algorytm stochastyczny szukania minimum globalnego oparty o metodę Dyfuzyjnego Monte Carlo (Diffusion Monte Carlo - DMC). Metoda DMC stosowana jest w fizyce i chemii kwantowej do rozwiązywania równania Schrodingera zależnego od czasu. W oryginalnej metodzie DMC symulacja obejmuje chmurę replik (kopii badanego systemu). W każdym kroku symulacji repliki są losowo przesuwane a następnie chmura jest modyfikowana zgodnie z określonym algorytmem. Algorytm DMC w zmodyfikowanej formie może być również wykorzystany do poszukiwania minimum globalnego układu. Algorytm ten nazwałem DMCOPT.

Algorytm DMC zwykle implementowany jest w dwóch różnych wersjach. W wariancie ze stałą liczbą replik (Continuous Weight DMC - CWDMC) każda replika niesie ze sobą dodatkowy parametr, tzw. wagę. W każdym kroku symulacji repliki są losowo przesuwane a następnie wagi replik są modyfikowane. Modyfikacja wag polega na zwiększeniu wag replik reprezentujących rozwiązania lepsze niż uśredniony wynik całej populacji, oraz zmniejszeniu wag dla replik, które reprezentują rozwiązania gorsze od średniej. Repliki, których wagi osiągnęły bardzo niską wartość, są zastępowane kopiami replik reprezentujących najlepsze rozwiązania.

Drugi z wariantów to wariant ze zmienną liczbą replik (Discrete Weight DMC - DWDMC). Wariant ten różni się od poprzedniego metodą modyfikacji populacji. Przede wszystkim zamiast średniej energii chmury używa się pewnej wartości odniesienia liczonej na podstawie średniej, ale przesuniętej zależnie od wielkości populacji. Po wyliczeniu rozwiązań dla każdej repliki, są one porównywane z wartością odniesienia. Repliki których wynik jest lepszy będą klonowane, a gorsze - usuwane. Prawdopodobieństwo klonowania i usunięcia zależy od różnicy między wynikiem danej repliki a wartością odniesienia. W tym wariancie, w odróżnieniu od poprzedniego, liczba replik będzie ulegać zmianie w trakcie symulacji, aczkolwiek fluktuacje te będą wygaszane poprzez odpowiednie przesuwanie wartości odniesienia. W algorytmie tym repliki nie posiadają wag. Z drugiej strony mamy repliki żywe i martwe, dla których można przyjąć odpowiednio wagi 0 i 1. Wariant ten możemy więc traktować jako modyfikację algorytmu CWDMC, ale dla którego wagi mogą przyjmować tylko te dwie wartości

W obu implementacjach algorytmu DMC występują dwa istotne procesy. Jednym z nich jest błądzenie losowe - w każdym kroku replika jest przesuwana o wektor generowany z rozkładem normalnym o określonej wartości sigma. Proces ten jest odpowiedzialny za eksplorację przestrzeni rozwiązań. Im większa jest wartość sigma, tym bardziej agresywnie jest ona przeszukiwana. Drugim procesem jest modyfikacja populacji. Ten proces jest odpowiedzialny za "heurystykę" algorytmu. Kontroluje on przesuwanie się chmury w kierunku obiecujących obszarów przestrzeni rozwiązań, unika przeszukiwania obszarów nieinteresujących (wysokie wartości funkcji), oraz powoduje zwiększanie się gęstości chmury w pobliżu najlepszych znalezionych punktów. Procesem tym sterują określone parametry kontrolne (różne w zależności od wariantu algorytmu) których wartości wpływają na intensywność tego procesu.

Poniższy applet demonstruje działanie algorytmu DMCOPT wykorzystującego obie implementacje DMC: CWDMC i DWDMC. Jako przykładowe funkcje użyłem sumy kwadratów (square), oraz problemy często stosowane jako testy w badaniach różnych metod optymalizacji globalnej - funkcje Ackleya, Griewangka, Solomona i Rastrigina. Dla wszystkich przepadków użyłem wersji funkcji dla dwóch wymiarów. Główny obszar appletu przedstawia przestrzeń rozwiązań danej funkcji - im jaśniejsza zieleń, tym niższa wartość funkcji w danym punkcie. Czerwony punkt w centrum obszaru to minimum globalne dla danej funkcji. Wartości N, MIN, AVG oznaczają aktualną liczbę replik oraz najniższą i średnią wartość funkcji dla chmury replik w danym kroku symulacji. Używając myszy można nanieść repliki w dowolnym miejscu przestrzeni rozwiązań. Przyciski START i STOP pozwalają uruchomić i zatrzymać symulację. Przycisk RESET usuwa wszystkie repliki. Pola wyboru CWDMC i DWDMC pozwalają wybrać stosowany wariant algorytmu. Ponieważ applet jest tylko demonstracją, większość parametrów algorytmu ustawiona jest "na stałe". Wyjątkiem jest parametr sigma, którego wartość może być zmieniana za pomocą suwaka. Aby uzyskać sensowne działanie algorytmu należy użyć przynajmniej kilkunastu replik (symulacje "produkcyjne" powinny używać znacznie większej ich liczby).

Wykorzystując powyższy applet można zaobserwować jak działają oba procesy składające się na DMCOPT, tj. błądzenie losowe i modyfikacja populacji. Dla efektywnej pracy algorytmu intensywność obu tych procesów musi być odpowiednio zrównoważona. Duże wartości sigma powodują bardzo agresywną eksplorację przestrzeni rozwiązań, ale efektywnie blokują "heurystykę" algorytmu - przekształcając go w czysty algorytm typu "random search". Z drugiej strony, małe wartości sigma powodują małą mobilność chmury i algorytm "utyka" w minimach lokalnych.

Algorytm sprawuje się dobrze w przypadku wielu funkcji posiadających dużą liczbę minimów lokalnych (przy odpowiednim doborze parametrów sterujących), wymaga jednak aby wartość funkcji w minimum globalnym była znacząco niższa niż w minimach lokalnych. Dla funkcji posiadających wiele minimów lokalnych o wartościach zbliżonych do minimum globalnego efektywność algorytmu jest znacznie gorsza. Przykładami takich funkcji mogą być funkcje Griewangka i Rastrigina.