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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

Загальний алгоритм[ред.ред. код]

Припустимо, що f: ℝn → ℝ це фітнес-функція або функція витрат яку потрібно мінімізувати. Позначимо через x ∈ ℝn позицію або можливий варіант розв’язку в пошуковому просторі. Тоді базовий алгоритм випадкового пошуку можна описати наступним чином:

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

Адаптивний вибір кроку[ред.ред. код]

Адаптивний алгоритм випадкового пошуку - одна з найчастіше вживаних модифікацій алгоритму - використовує змінний крок пошуку залежно від досягненого успіху на попередніх кроках. Якщо дві послідовних ітерації дають покращення цільової функції, крок збільшується в as разів; якщо М послідовних ітерацій не дають покращення, крок зменшується в аf разів. В загальному алгоритмі величина кроку d обчислюється наступним чином:

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

Допустимими є, наприклад, параметри a_s=1.618, a_f=0.618, M=3n де n - розмірність пошукового простору[2].
Використання алгоритму випадкового пошуку з адаптивним вибором кроку можливо в найнесподіваніших ситуаціях - наприклад, при виборі оптимального розміщення туристів в автобусі[3].

Варіанти[ред.ред. код]

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

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

Див. також[ред.ред. код]

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

Посилання[ред.ред. код]

  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. http://www.theweman.info/topics/t7r4part1.html
  3. http://habrahabr.ru/post/149821/
  4. Schumer, M.A.; Steiglitz, K. (1968). "Adaptive step size random search". IEEE Transactions on Automatic Control 13 (3): 270–276.
  5. Schumer, M.A.; Steiglitz, K. (1968). "Adaptive step size random search". IEEE Transactions on Automatic Control 13 (3): 270–276.
  6. Schrack, G.; Choit, M. (1976). "Optimized relative step size random searches". Mathematical Programming 10 (1): 230–244.