PROFILPELAJAR.COM

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

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

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

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

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

Ініціювати х випадковою точкою у просторі пошуку.
Допоки критерію переривання пошуку не досягнуто (наприклад, виконано максимальну кількість ітерацій або досягнуто необхідне наближення) повторювати таке:
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^[2]) — одна з найчастіше вживаних модифікацій алгоритму — використовує змінний крок пошуку залежно від досягненого успіху на попередніх кроках. Якщо дві послідовних ітерації дають покращення цільової функції, крок збільшується в $a s$ разів; якщо $М$ послідовних ітерацій не дають покращення, крок зменшується в $а f$ разів. У загальному алгоритмі величина кроку d обчислюється таким чином:

Ініціювати довільне $d$ , наприклад, $d=1$ та лічильник невдалих ітерацій $m=0$ .
Якщо нова позиція у є кращою за позицію х, збільшити $d$ в $a s$ разів: $d=a_{s}d$
Якщо нова позиція у є гіршою за позицію х, збільшити лічильник на одиницю: $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$ — розмірність пошукового простору^[3].

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

Варіанти

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

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

Див. також

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

Примітки

↑ 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.
↑ ^а ^б ^в Schumer, M.A.; Steiglitz, K. (1968). «Adaptive step size random search». IEEE Transactions on Automatic Control 13 (3): 270—276.
↑ Архівована копія. Архів оригіналу за 2 листопада 2012. Процитовано 29 жовтня 2012. {{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання)
↑ Архівована копія. Архів оригіналу за 24 жовтня 2012. Процитовано 29 жовтня 2012. {{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання)
↑ Schrack, G.; Choit, M. (1976). «Optimized relative step size random searches». Mathematical Programming 10 (1): 230—244.