Методи стохастичної оптимізації (CO) — це методи оптимізації, які генерують і використовують випадкові величини. Для стохастичних задач випадкові величини з'являються у формулюванні самої задачі оптимізації, що включає випадкові цільові функції або випадкові обмеження (). Методи стохастичної оптимізації також включають методи з випадковими ітераціями. Деякі методи стохастичної оптимізації використовують випадкові ітерації для вирішення стохастичних задач, поєднуючи обидва значення стохастичної оптимізації. Методи стохастичної оптимізації узагальнюють детерміновані методи для детермінованих задач.
Методи стохастичних функцій Частково-випадкові вхідні дані виникають під час процесу оцінювання та контролю у реальному часі, оптимізації на основі моделювання (при оцінюванні фактичної системи завдяки методу Монте-Карло)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. та в задачах, де присутня експериментальна (випадкова) похибка під час вимірювання критеріїв. У таких випадках знання про те, що серед значень функції присутній випадковий «шум», природньо призводить до алгоритмів, які використовують інструменти статистичного висновування для оцінки «справжніх» значень функції та/або прийняття статистично оптимальних рішень щодо наступних кроків. Методи цього класу включають:
за Роббінсом і Монро (1951) стохастичний градієнтний спуск скінченно-різницеве стохастичне наближення за Кіфером і Вулфовіцем (1952) за Споллом (1992)
Випадкові методи пошуку
З іншого боку, навіть коли набір даних складається з точних вимірювань, деякі методи вводять випадковість у процес пошуку для прискорення прогресу.Holger H. Hoos and Thomas Stützle, Stochastic Local Search: Foundations and Applications, Morgan Kaufmann / Elsevier, 2004. Така випадковість також може зробити метод менш чутливим до похибок моделювання. Крім того, введена випадковість може дозволити методу уникнути локального оптимуму і в кінцевому підсумку наблизитися до глобального оптимуму. Дійсно, цей принцип рандомізації, як відомо, є простим та ефективним способом отримання алгоритмів із майже певною ефективністю для багатьох наборів даних багатьох видів задач. До таких методів стохастичної оптимізації належать:
алгоритм імітації відпалу за С. Кіркпатріком, К. Д. Гелаттом і М. П. Веккі (1983) квантовий відпал колективи ймовірностей за Д. Х. Волпертом, С. Р. Бєнявським та Д. Г. Раджнараяном (2011) (англ. Reactive Search Optimization) за , Г. Теккіоллі (1994), метод перехресної ентропії за Рубінштейном і (2004) випадковий пошук за (1991) інформаційний пошук
або обмін репліками
колективні алгоритми еволюційні алгоритми генетичні алгоритми Холланда (1975) еволюційні стратегії оптимізації та модифікації об'єктів (2016)
Деякі автори навпаки стверджують, що рандомізація може покращити детермінований алгоритм лише в тому випадку, якщо він був погано розроблений з самого початку.http://lesswrong.com/lw/vp/worse_than_random/ стверджує, що зловживання випадковими елементами може запобігти розвитку більш розумних і кращих детермінованих компонентів. Спосіб, яким зазвичай представлені результати алгоритмів стохастичної оптимізації (наприклад, представлення лише середнього або навіть найкращого з N запусків без жодної згадки про розповсюдження), також може призвести до позитивного зміщення у бік випадковості.
Див. також
Глобальна оптимізація Машинне навчання
Гауссівський процес Модель простору станів Управління з прогнозуючими моделями Нелінійне програмування
Примітки
Література
Michalewicz, Z. and Fogel, D. B. (2000), How to Solve It: Modern Heuristics, Springer-Verlag, New York. «PSA: A novel optimization algorithm based on survival rules of porcellio scaber», Y. Zhang and S. Li
Посилання
COSP