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

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

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

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

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

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

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

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

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

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