Global minimum optimization using Diffusion Monte Carlo approach

• Autorzy: Kazimirski J. K.

Warianty tytułu

PL

Poszukiwanie minimum globalnego metodą dyfuzyjną Monte Carlo (DMC)

• Języki publikacji: EN

Abstrakty

EN

In this preliminary study we present a new approach for a global minimum search of a continuous objective function based on the Diffusion Monte Carlo (DMC) method. In this article we suggest the simple implementation of the computer algorithm. W also test the efficiency of the DMC based approach against a pure random approach based on blind search (random sampling) and random walk algorithms. We use four test problems, namely Ackley's and Griewangk's functions in 5 and 20 dimensions. We show that in all tested cases the DMC algorithm performs significantly better than pure random methods - the optimal solutions generated by DMC method are much closer to the known global minimum of the test problems than the results obtained with blind search and random walk algorithms.

PL

W artykule przedstawiona została metoda optymalizacji globalnej dowolnej funkcji ciągłej oparta o algorytm dyfuzyjnego Monte Carlo (DMC). Proponujemy sposób prostej implementacji zaproponowanego algorytmu, a także przedstawiamy wstępne rezultaty symulacji pokazujących efektywność metody DMC w porównaniu z metodami czysto losowymi - próbkowaniem losowym i błądzeniem losowym. Jako problemy testowe w symulacjach wykorzystujemy funkcję Ackley-a i Griewangk-a w wariantach 5- i 20-wymiarowym. Rezultaty przeprowadzonych symulacji wskazują na znacznie większą efektywność metody DMC w porównaniu z pozostałymi - uzyskane za jej pomocą rozwiązania są znacznie bliższe globalnemu minimum niż wyniki uzyskane metodami czysto losowymi.

Słowa kluczowe

EN

global optimization; global minimum problem; Monte Carlo; diffusion Monte Carlo

PL

optymalizacja globalna; problem minimum globalnego; Monte Carlo; algorytm Monte Carlo dyfuzyjny

• Wydawca: Oficyna Wydawnicza Europejskiej Uczelni
• Czasopismo: Studia i Materiały / Europejska Uczelnia Informatyczno-Ekonomiczna w Warszawie
• Rocznik: 2011
• Tom: Nr 1(1)
• Strony: 63--71
• Opis fizyczny: Bibliogr. 12 poz., rys., tab.

Twórcy

autor

Kazimirski J. K.

• Europejska Wyższa Szkoła Informatyczno-Ekonomiczna w Warszawie, Wydział Informatyki, ul. Kolektorska 9/11, 01-691 Warszawa

Bibliografia

• [1] Floudas, C. A. Deterministic Global Optimization: Theory, Algorithms and Applications. Kluwer, Dordrecht, (1999).
• [2] Horst, R., Pardalos, P. M., and Thoai, N. V. Introduction to Global Optimization. Kluwer, Dordrecht, (1995).
• [3] Floudas, C. A. and Pardalos, P. M. Optimization in Computational Chemistry and Molecular Biology: Local and Global Approaches. Kluwer, Dordrecht, (2000).
• [4] Bliek, C., Jermann, C., and Neumaier, A., editors. Global Optimization and Constraint Satisfaction. Springer, Berlin, (2003).
• [5] Anderson, J. B. J. Chem. Phys. 63(4), 1499–1503 (1975).
• [6] Anderson, J. B. J. Chem. Phys. 65(10), 4121–4127 (1976).
• [7] Suhm, M. A. and Watts, R. O. Phys. Rep. 204(4), 293–329 (1991).
• [8] Kazimirski, J. K. and Buch, V. J.Phys.Chem. A 107(46), 9762–9775 (2003).
• [9] Kazimirski, J. Computational Study of Hydrogen Bonded Systems. PhD thesis, The Hebrew University, Jerusalem, (2004).
• [10] Ackley, D. H. A connectionist machine for genetic hillclimbing. Kluwer, Boston, (1987).
• [11] Bäck, T. Evolutionary algorithms in theory and practice. Oxford University Press, (1996).
• [12] Törn, A. and Pilinskas, A. In Lecture Notes in Computer Science 350. Springer-Verlag, (1989). Berlin Heidelberg.