Випадкова оптимізація

Випадкова оптимізація (ВО, англ. RO) — це сімейство методів чисельної оптимізації, які не вимагають оптимізації градієнта задачі, і тому ВО можна використовувати для функцій, які не є безперервними або диференційованими. Такі методи оптимізації також відомі, як методи прямого пошуку, без похідних чи методів чорної коробки.

Назва «випадкова оптимізація» приписується Матіасу (англ. Matyas)^[1] який початково представив ВО разом із основним математичним аналізом. ВО працює шляхом ітераційного переміщення до кращих позицій у просторі пошуку, які відбираються з використанням, наприклад, нормального розподілу навколо поточної позиції.

Алгоритм

Нехай f : ℝ ⁿ → ℝ — функція придатності або вартості, яку необхідно мінімізувати. Нехай x ∈ ℝ ⁿ позначає позицію або варіант рішення в просторі пошуку. Основний алгоритм ВО можна описати так:

• Ініціалізуйте x випадковою позицією в просторі пошуку.
• Поки не буде виконано критерій припинення (наприклад, кількість виконаних ітерацій або досягнута відповідна придатність), повторіть наступне:
  • Випробуйте нову позицію y, додавши до поточної позиції x нормально розподілений випадковий вектор
  • Якщо ( f ( y ) < f ( x )), потім перейдіть на нове положення, встановивши x = y
• Тепер x займає найкращу позицію.

Цей алгоритм відповідає стратегії (1+1) еволюції з постійним розміром кроку.

Збіжність і варіації

Матіас показав, що базова форма ВО сходиться до оптимуму простої унімодальної функції, використовуючи обмеження, яке показує, що збіжність до оптимуму напевно відбудеться, якщо виконується потенційно нескінченна кількість ітерацій. Однак цей доказ не є корисним на практиці, оскільки можна виконати лише скінченну кількість ітерацій. Насправді таке теоретичне обмеження також покаже, що чисто випадкова вибірка простору пошуку неминуче дасть вибірку, як завгодно близьку до оптимальної.

Математичний аналіз також проводять Баба^[2] і Соліс і Ветс^[3], щоб встановити, що зближення до області, що оточує оптимум, є неминучим за деяких м'яких умов для варіантів ВО з використанням інших розподілів ймовірностей для вибірки. Оцінка кількості ітерацій, необхідних для наближення до оптимуму, отримана Дореа.^[4] Цей аналіз піддається критиці через емпіричні експерименти Сарма^[5] який використовував варіанти оптимізатора Баби і Дореа для двох реальних проблем, показуючи, що наближення до оптимуму дуже повільне, і більше того, що методи фактично не змогли знайти відповідне рішення придатності, якщо тільки процес не був розпочатий досить близько до оптимального з початку.

Див. також

• Випадковий пошук — це тісно пов'язане сімейство методів оптимізації, які використовують вибірку з гіперсфери замість нормального розподілу.
• Лууса–Яаколи^[en] — це тісно пов'язаний метод оптимізації, який використовує рівномірний розподіл у вибірці та просту формулу для експоненціального зменшення діапазону вибірки.
• Пошук за шаблоном виконує кроки вздовж осей простору пошуку з використанням експоненціально зменшуваних розмірів кроків.
• Стохастична оптимізація

Примітки

1. I. Mátyáš, “Random Optimization”, Avtomat. i Telemekh., 26:2 (1965), 246–253. www.mathnet.ru. Архів оригіналу за 28 січня 2022. Процитовано 28 січня 2022.
2. Baba, N. (1 квітня 1981). Convergence of a random optimization method for constrained optimization problems. Journal of Optimization Theory and Applications (англ.). Т. 33, № 4. с. 451—461. doi:10.1007/BF00935752. ISSN 1573-2878. Процитовано 28 січня 2022.
3. Solis, Francisco J.; Wets, Roger J.-B. (1 лютого 1981). Minimization by Random Search Techniques. Mathematics of Operations Research. Т. 6, № 1. с. 19—30. doi:10.1287/moor.6.1.19. ISSN 0364-765X. Архів оригіналу за 28 січня 2022. Процитовано 28 січня 2022.
4. Dorea, C. C. Y. (1 лютого 1983). Expected number of steps of a random optimization method. Journal of Optimization Theory and Applications (англ.). Т. 39, № 2. с. 165—171. doi:10.1007/BF00934526. ISSN 1573-2878. Процитовано 28 січня 2022.
5. Sarma, M. S. (1 серпня 1990). On the convergence of the Baba and Dorea random optimization methods. Journal of Optimization Theory and Applications (англ.). Т. 66, № 2. с. 337—343. doi:10.1007/BF00939542. ISSN 1573-2878. Процитовано 28 січня 2022.