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

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

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

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

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

Нехай ${\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) — одна з найчастіше вживаних модифікацій алгоритму — використовує змінний крок пошуку залежно від досягненого успіху на попередніх кроках. Якщо дві послідовних ітерації дають покращення цільової функції, крок збільшується в 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 — розмірність пошукового простору.

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

Варіанти

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

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

Див. також

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

Примітки

1. Rastrigin, L.A. (1963). «The convergence of the random search method in the extremal control of a many parameter system». Automation and Remote Control 24 (10): 1337—1342.
2. Schumer, M.A.; Steiglitz, K. (1968). «Adaptive step size random search». IEEE Transactions on Automatic Control 13 (3): 270—276.
3. . Архів оригіналу за 2 листопада 2012. Процитовано 29 жовтня 2012.{{}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title ()
4. . Архів оригіналу за 24 жовтня 2012. Процитовано 29 жовтня 2012.{{}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title ()
5. Schrack, G.; Choit, M. (1976). «Optimized relative step size random searches». Mathematical Programming 10 (1): 230—244.