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

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

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

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

• стохастичне наближення^[en] за Роббінсом і Монро (1951)^[4]
• стохастичний градієнтний спуск
• скінченно-різницеве стохастичне наближення за Кіфером і Вулфовіцем (1952)^[5]
• стохастичне наближення з одночасним збуренням^[en] за Споллом (1992)^[6]
• сценарну оптимізацію^[en]

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

Див. також: Метаевристика

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

• алгоритм імітації відпалу за С. Кіркпатріком, К. Д. Гелаттом і М. П. Веккі (1983)^[8]
• квантовий відпал
• колективи ймовірностей за Д. Х. Волпертом, С. Р. Бєнявським та Д. Г. Раджнараяном (2011)^[9]
• реактивна оптимізація пошуку^[en] (англ. Reactive Search Optimization) за Роберто Баттіті^[en], Г. Теккіоллі (1994),^[10][11]
• метод перехресної ентропії за Рубінштейном і Крезе^[en] (2004)^[12]
• випадковий пошук за Анатолієм Жиглявським^[en] (1991)^[13]
• інформаційний пошук^[14]
• стохастичне тунелювання^[en][15]
• паралельне гартування^[en] або обмін репліками^[16]
• стохастичне сходження до вершини^[en]
• колективні алгоритми
• еволюційні алгоритми
  • генетичні алгоритми Холланда (1975)^[17]
  • еволюційні стратегії
• каскадний алгоритм^[en] оптимізації та модифікації об'єктів (2016)^[18]

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

Див. також

• Глобальна оптимізація
• Машинне навчання
• Сценарна оптимізація^[en]
• Гауссівський процес
• Модель простору станів
• Управління з прогнозуючими моделями
• Нелінійне програмування
• Ентропійна вартість під ризиком^[en]