Optimizare stocastică
Metodele de optimizare stocastică (OS) sunt algoritmi de optimizare care încorporează elemente probabiliste (aleatorii), fie în datele problemei ( funcția obiectivă , aproximări etc.), fie în algoritmul însuși (prin valori parametrice aleatorii, alegeri aleatorii etc.). sau ambele [1] . Conceptul contrastează cu metodele de optimizare deterministe în care valorile funcției obiective sunt exacte prin ipoteză, iar calculul este complet determinat de valorile exemplificate până acum.
Metode pentru funcții stochastice
Datele de intrare parțial aleatorii apar de exemplu în estimări și controale în timp real, optimizări bazate pe simulare, unde simulările Monte Carlo sunt utilizate ca estimări ale unui sistem real [2] și probleme în care există o eroare experimentală (aleatorie) în măsurătorile criteriul. În astfel de cazuri, cunoașterea faptului că valorile funcției sunt afectate de zgomotul aleatoriu conduce în mod natural la algoritmi care utilizează instrumente de inferență statistică pentru a estima valorile adevărate ale funcției și / sau pentru a obține decizii statistice optime cu privire la pașii următori. Metodele acestei clase includ:
- aproximarea stocastică (SA) a lui Robbins și Monro (1951) [3]
- originea gradientului stochastic
- aproximarea stocastică a diferenței finite de Kiefer și Wolfowitz (1952) [4]
- Aproximarea stocastică a perturbărilor simultane a lui Spall (1992) [5]
Metode de căutare aleatorii
Pe de altă parte, chiar și atunci când datele sunt exacte, uneori este util să îi adăugați în mod deliberat aleatoriu pentru a căuta procese ca instrumente de accelerare a convergenței și pentru a face algoritmul mai puțin dependent de erorile de modelare. Mai mult, întâmplarea indusă poate oferi impulsul necesar pentru a se desprinde de o soluție limitată atunci când se caută un remediu global. De fapt, acest principiu al randomizării este cunoscut a fi o metodă simplă și eficientă pentru obținerea algoritmilor cu performanțe bune aproape sigure care traversează uniform toate seturile de date, pentru orice tip de problemă. Metodele de optimizare stocastică de acest tip includ:
- Recuperarea simulată de S. Kirkpatrick, CD Gelatt și MP Vecchi (1983) [6]
- metoda entropiei încrucișate de Rubinstein și Kroese (2004) [7]
- Căutarea aleatorie a lui Zhigljaysky (1991) [8]
- tehnica saltului bazinului , cunoscută și sub denumirea de tehnica Monte Carlo cu minimizare [9] [10]
- inserție stocastică [10] [11]
- moderare paralelă numită și schimb repetat [10] [12]
- urcând pe dealul stochastic
- algoritmii roiului
- algoritmi evolutivi
- Algoritmul genetic al lui Goldberg (1989) [13]
Notă
- ^ Spall, JC, Introducere în căutarea și optimizarea stochastică , Wiley, 2003.
- ^ Fu, MC, Optimizare pentru simulare: Teorie vs. Practica , în INFORMS Journal on Computing , (cu discuții de S. Andradóttir, P. Glynn și JP Kelly), vol. 14, 2002, pp. 192–227, DOI : 10.1287 / ijoc.14.3.192.113 .
- ^ Robbins, H., Monro, S., O metodă de aproximare stocastică , în Annals of Mathematical Statistics , vol. 22, 1951, pp. 400–407, DOI : 10.1214 / aoms / 1177729586 .
- ^ J. Kiefer , J. Wolfowitz, Stochastic Estimation of the Maximum of a Regression Function , în Annals of Mathematical Statistics , vol. 23, 1952, pp. 462–466, DOI : 10.1214 / aoms / 1177729392 .
- ^ Spall, JC, Aproximare stocastică multivariată utilizând o aproximare simultană a gradientului perturbației , în IEEE Transactions on Automatic Control , vol. 37, 1992, pp. 332–341, DOI : 10.1109 / 9.119632 .
- ^ S. Kirkpatrick, CD Gelatt; MP Vecchi, Optimization by Simulated Annealing , în Știință , vol. 220, n. 4598, 1983, pp. 671–680, DOI : 10.1126 / science.220.4598.671 , PMID 17813860 .
- ^ Rubinstein, RY, Kroese, DP, Metoda Cross-Entropy , Springer-Verlag, 2004, ISBN 978-0-387-21240-1 .
- ^ Zhigljavsky, AA,Theory of Global Random Search , Kluwer Academic, 1991.
- ^ Akbar Nayeem, Jorge Vila; Harold A. Scheraga, Un studiu comparativ al abordărilor simulate-recoacere și Monte Carlo-cu-minimizare la structurile de energie minimă ale polipeptidelor: [met] -enkefalină , în J. Comp. Chem. , vol. 12, nr. 5, 1991, pp. 594–605, DOI : 10.1002 / jcc.540120509 .
- ^ a b c W. Wenzel, Metode de optimizare stocastică , la iwrwww1.fzk.de . Adus la 24 aprilie 2009 (arhivat din original la 1 iunie 2009) .
- ^ W. Wenzel, K. Hamacher, Abordarea tunelului stochastic pentru optimizarea globală a peisajelor complexe de energie potențială , în Phys. Rev. Lett. , Vol. 82, 1999, p. 3003, DOI : 10.1103 / PhysRevLett.82.3003 .
- ^ E. Marinari, G. Parisi, Simulation tempering: A new monte carlo scheme , in Europhys. Lit. , vol. 19, 1992, p. 451, DOI : 10.1209 / 0295-5075 / 19/6/002 .
- ^ Goldberg, DE, Algoritmi genetici în căutare, optimizare și învățare automată , Addison-Wesley, 1989 (arhivat din original la 19 iulie 2006) .
- Michalewicz, Z. și Fogel, DB (2000), How to Solve It: Modern Heuristics , Springer-Verlag, New York.
