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

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

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

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

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

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

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

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

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

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

Допустимими є, наприклад, параметри $a_s=1.618,a_f=0.618,M=3n$, де Шаблон:Math — розмірність пошукового простору.

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

Варіанти

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

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

Див. також

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