Стохастична оптимізація

Методи стохастичної оптимізації (CO) — це методи оптимізації, які генерують і використовують випадкові величини. Для стохастичних задач випадкові величини з'являються у формулюванні самої задачі оптимізації, що включає випадкові цільові функції або випадкові обмеження (англ. constraints). Методи стохастичної оптимізації також включають методи з випадковими ітераціями. Деякі методи стохастичної оптимізації використовують випадкові ітерації для вирішення стохастичних задач, поєднуючи обидва значення стохастичної оптимізації.[1] Методи стохастичної оптимізації узагальнюють детерміновані методи для детермінованих задач.

Методи стохастичних функцій

Частково-випадкові вхідні дані виникають під час процесу оцінювання та контролю у реальному часі, оптимізації на основі моделювання (при оцінюванні фактичної системи завдяки методу Монте-Карло)[2][3] та в задачах, де присутня експериментальна (випадкова) похибка під час вимірювання критеріїв. У таких випадках знання про те, що серед значень функції присутній випадковий «шум», природньо призводить до алгоритмів, які використовують інструменти статистичного висновування для оцінки «справжніх» значень функції та/або прийняття статистично оптимальних рішень щодо наступних кроків. Методи цього класу включають:

Випадкові методи пошуку

З іншого боку, навіть коли набір даних складається з точних вимірювань, деякі методи вводять випадковість у процес пошуку для прискорення прогресу.[7] Така випадковість також може зробити метод менш чутливим до похибок моделювання. Крім того, введена випадковість може дозволити методу уникнути локального оптимуму і в кінцевому підсумку наблизитися до глобального оптимуму. Дійсно, цей принцип рандомізації, як відомо, є простим та ефективним способом отримання алгоритмів із майже певною ефективністю для багатьох наборів даних багатьох видів задач. До таких методів стохастичної оптимізації належать:

Деякі автори навпаки стверджують, що рандомізація може покращити детермінований алгоритм лише в тому випадку, якщо він був погано розроблений з самого початку.[19] Фред В. Гловер[20] стверджує, що зловживання випадковими елементами може запобігти розвитку більш розумних і кращих детермінованих компонентів. Спосіб, яким зазвичай представлені результати алгоритмів стохастичної оптимізації (наприклад, представлення лише середнього або навіть найкращого з N запусків без жодної згадки про розповсюдження), також може призвести до позитивного зміщення у бік випадковості.

Див. також

Примітки
  1. Spall, J. C. (2003). Introduction to Stochastic Search and Optimization. Wiley. ISBN 978-0-471-33052-3.
  2. Fu, M. C. (2002). Optimization for Simulation: Theory vs. Practice. INFORMS Journal on Computing 14 (3): 192–227. doi:10.1287/ijoc.14.3.192.113.
  3. M.C. Campi and S. Garatti. The Exact Feasibility of Randomized Solutions of Uncertain Convex Programs. SIAM J. on Optimization, 19, no.3: 1211—1230, 2008.
  4. Robbins, H.; Monro, S. (1951). A Stochastic Approximation Method. Annals of Mathematical Statistics 22 (3): 400–407. doi:10.1214/aoms/1177729586.
  5. J. Kiefer; J. Wolfowitz (1952). Stochastic Estimation of the Maximum of a Regression Function. Annals of Mathematical Statistics 23 (3): 462–466. doi:10.1214/aoms/1177729392.
  6. Spall, J. C. (1992). Multivariate Stochastic Approximation Using a Simultaneous Perturbation Gradient Approximation. IEEE Transactions on Automatic Control 37 (3): 332–341.
  7. Holger H. Hoos and Thomas Stützle, Stochastic Local Search: Foundations and Applications, Morgan Kaufmann / Elsevier, 2004.
  8. S. Kirkpatrick; C. D. Gelatt; M. P. Vecchi (1983). Optimization by Simulated Annealing. Science 220 (4598): 671–680. Bibcode:1983Sci...220..671K. PMID 17813860.
  9. D.H. Wolpert; S.R. Bieniawski; D.G. Rajnarayan (2011). Probability Collectives in Optimization. Santa Fe Institute.
  10. Battiti, Roberto; Gianpietro Tecchiolli (1994). The reactive tabu search. ORSA Journal on Computing 6 (2): 126–140. doi:10.1287/ijoc.6.2.126.
  11. Battiti, Roberto; Mauro Brunato; Franco Mascia (2008). Reactive Search and Intelligent Optimization. Springer Verlag. ISBN 978-0-387-09623-0.
  12. Rubinstein, R. Y.; Kroese, D. P. (2004). The Cross-Entropy Method. Springer-Verlag. ISBN 978-0-387-21240-1.
  13. Zhigljavsky, A. A. (1991). Theory of Global Random Search. Kluwer Academic. ISBN 978-0-7923-1122-5.
  14. Kagan E.; Ben-Gal I. (2014). A Group-Testing Algorithm with Online Informational Learning. IIE Transactions 46 (2): 164–184. doi:10.1080/0740817X.2013.803639.
  15. W. Wenzel; K. Hamacher (1999). Stochastic tunneling approach for global optimization of complex potential energy landscapes. Phys. Rev. Lett. 82 (15): 3003. Bibcode:1999PhRvL..82.3003W. arXiv:physics/9903008. doi:10.1103/PhysRevLett.82.3003.
  16. E. Marinari; G. Parisi (1992). Simulated tempering: A new monte carlo scheme. Europhys. Lett. 19 (6): 451–458. Bibcode:1992EL.....19..451M. arXiv:hep-lat/9205018. doi:10.1209/0295-5075/19/6/002.
  17. Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley. ISBN 978-0-201-15767-3. Архів оригіналу за 19 липня 2006.
  18. Tavridovich, S. A. (2017). COOMA: an object-oriented stochastic optimization algorithm. International Journal of Advanced Studies 7 (2): 26–47. doi:10.12731/2227-930x-2017-2-26-47.
  19. http://lesswrong.com/lw/vp/worse_than_random/
  20. Glover, F. (2007). Tabu search—uncharted domains. Annals of Operations Research 149: 89–98.

Література

Посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.