Назва «випадкова оптимізація» приписується Матіасу (англ.Matyas)[1] який початково представив ВО разом із основним математичним аналізом. ВО працює шляхом ітераційного переміщення до кращих позицій у просторі пошуку, які відбираються з використанням, наприклад, нормального розподілу навколо поточної позиції.
Алгоритм
Нехай f : ℝ n → ℝ — функція придатності або вартості, яку необхідно мінімізувати. Нехай x ∈ ℝ n позначає позицію або варіант рішення в просторі пошуку. Основний алгоритм ВО можна описати так:
Ініціалізуйте x випадковою позицією в просторі пошуку.
Поки не буде виконано критерій припинення (наприклад, кількість виконаних ітерацій або досягнута відповідна придатність), повторіть наступне:
Якщо ( f ( y ) < f ( x )), потім перейдіть на нове положення, встановивши x = y
Тепер x займає найкращу позицію.
Цей алгоритм відповідає стратегії (1+1) еволюції з постійним розміром кроку.
Збіжність і варіації
Матіас показав, що базова форма ВО сходиться до оптимуму простої унімодальної функції, використовуючи обмеження, яке показує, що збіжність до оптимуму напевно відбудеться, якщо виконується потенційно нескінченна кількість ітерацій. Однак цей доказ не є корисним на практиці, оскільки можна виконати лише скінченну кількість ітерацій. Насправді таке теоретичне обмеження також покаже, що чисто випадкова вибірка простору пошуку неминуче дасть вибірку, як завгодно близьку до оптимальної.
Математичний аналіз також проводять Баба[2] і Соліс і Ветс[3], щоб встановити, що зближення до області, що оточує оптимум, є неминучим за деяких м'яких умов для варіантів ВО з використанням інших розподілів ймовірностей для вибірки. Оцінка кількості ітерацій, необхідних для наближення до оптимуму, отримана Дореа.[4] Цей аналіз піддається критиці через емпіричні експерименти Сарма[5] який використовував варіанти оптимізатора Баби і Дореа для двох реальних проблем, показуючи, що наближення до оптимуму дуже повільне, і більше того, що методи фактично не змогли знайти відповідне рішення придатності, якщо тільки процес не був розпочатий досить близько до оптимального з початку.
Див. також
Випадковий пошук — це тісно пов'язане сімейство методів оптимізації, які використовують вибірку з гіперсфери замість нормального розподілу.
Лууса–Яаколи[en] — це тісно пов'язаний метод оптимізації, який використовує рівномірний розподіл у вибірці та просту формулу для експоненціального зменшення діапазону вибірки.
Пошук за шаблоном виконує кроки вздовж осей простору пошуку з використанням експоненціально зменшуваних розмірів кроків.
