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

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

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

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

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

Нехай $f\colon \mathbb {R} ^{n}\to \mathbb {R}$ — це функція втрат яку потрібно мінімізувати. Позначимо через $\mathbf {x} \in \mathbb {R} ^{n}$ точку (позицію) або можливий варіант розв'язку у просторі пошуку. Тоді базовий алгоритм випадкового пошуку можна описати наступним чином:

1. Ініціювати х випадковою точкою у просторі пошуку.
2. До тих пір поки критерій переривання пошуку не досягнуто (наприклад, виконано максимальну кількість ітерацій або досягнуто необхідне наближення) повторювати наступне:
   1. Вибрати нову позицію у з рівномірно розподілених точок на гіперсфері заданого радіусу d з центром у поточній точці х. Для цього потрібно зробити наступні кроки:
      1. Згенерувати n-вимірний гаусівський вектор з мат. сподіванням в точці 0 і довільною дисперсією: $\mathbf {x} =(x_{1},x_{2},...,x_{n})$.
      2. Обрахувати радіус цього вектору (відстань від початку координат): $r={\sqrt {x_{1}^{2}+x_{2}^{2}+...+x_{n}^{2}}}$. Тоді рівномірно розподілений вектор заданого радіусу d знаходиться як ${\frac {d}{r}}\mathbf {x}$.
   2. Якщо f(y) < f(x) — переходити на нову позицію заданням x = y.

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

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

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

Допустимими є, наприклад, параметри $a_{s}=1.618,a_{f}=0.618,M=3n$, де n — розмірність пошукового простору.

Використання алгоритму випадкового пошуку з адаптивним вибором кроку можливо в найнесподіваніших ситуаціях — наприклад, при виборі оптимального розміщення туристів в автобусі.

Варіанти

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

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

Див. також

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