Випадковий пошук

Випадковий пошук – група методів числової оптимізації, які не вимагають обчислення градієнту для розв’язання задач оптимізації; отже, випадковий пошук можна використовувати для функцій, що не є неперервними або диференційованими. Подібні методи оптимізації також називаються методами прямого пошуку, методами «чорної скриньки» або методами без використання похідної.

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

Загальний алгоритм

Припустимо, що f: ℝn → ℝ це фітнес-функція або функція витрат яку потрібно мінімізувати. Позначимо через x ∈ ℝn позицію або можливий варіант розв’язку в пошуковому просторі. Тоді базовий алгоритм випадкового пошуку можна описати наступним чином:

• Ініціювати х випадковою позицією в пошуковому просторі
• До тих пір поки критерій переривання не досягнений (напр., виконано максимальну кількість ітерацій або досягнено необхідного фітнесу) повторювати наступне:
• Вибирати нову позицію у з рівномірно розподілених точок на гіперсфері заданого радіусу d що оточує поточну позицію х. Для цього потрібно зробити наступне:

1. Згенерувати n-вимірний гаусівський вектор з мат. сподіванням в точці 0 і довільною дисперсією: $\mathbf{x}=(x_1,x_2,...,x_n)$
2. Обрахувати радіус цього вектору (відстань від початку координат): $r=\sqrt{x^2_1+x^2_2+...+x^2_n}$
3. Тоді рівномірно розподілений вектор заданого радіусу d можна знайти як $\frac{d}{r}\mathbf{x}$

• Якщо (f(y) < f(x)) – переходити на нову позицію заданням x = y
• Тепер x має найкращу позицію.

Адаптивний вибір кроку

Адаптивний алгоритм випадкового пошуку - одна з найчастіше вживаних модифікацій алгоритму - використовує змінний крок пошуку залежно від досягненого успіху на попередніх кроках. Якщо дві послідовних ітерації дають покращення цільової функції, крок збільшується в a_s разів; якщо М послідовних ітерацій не дають покращення, крок зменшується в а_f разів. В загальному алгоритмі величина кроку d обчислюється наступним чином:

1. Ініціювати довільне d, наприклад, d=1 та лічильник невдалих ітерацій m=0.
2. Якщо нова позиція у є кращою за позицію х, збільшити d в a_s разів: $d=a_sd$
3. Якщо нова позиція у є гіршою за позицію х, збільшити лічильник на одиницю: $m=m+1$. Якщо виконується умова $m \geq {M}$, зменшити d в а_f разів: $d=a_fd$ та обнулити лічильник: m=0.

Допустимими є, наприклад, параметри $a_s=1.618, a_f=0.618, M=3n$ де n - розмірність пошукового простору.
Використання алгоритму випадкового пошуку з адаптивним вибором кроку можливо в найнесподіваніших ситуаціях - наприклад, при виборі оптимального розміщення туристів в автобусі.

Варіанти

В літературі існує декілька варіантів випадкового пошуку:

• Випадковий пошук із фіксованим кроком – базовий алгоритм Растригіна який обирає нові позиції із гіперсфери із заданим фіксованим радіусом
• Випадковий пошук з оптимальним кроком (Schumer and Steiglitz) – теоретична викладка з визначення оптимального радіусу гіперсфери для пришвидшеної конвергенції з оптимумом. Використання цього методу вимагає апроксимації цього оптимального радіусу шляхом багаторазової дискретизації, тому є занадто вимогливим до ресурсів для практичного застосування.
• Випадковий пошук з адаптивним кроком (Schumer and Steiglitz) – алгоритм що евристично адаптує радіус гіперсфери. Проте, алгоритм дещо ускладнений.
• Випадковий пошук із оптимізованим відносним кроком (Schrack and Choit) апроксимує оптимальний розмір кроку шляхом простого експоненційного зменшення. Проте, формула для обчислення коефіцієнту згладжування дещо ускладнена.

Див. також

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