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

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

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

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

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

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

  • Ініціювати х випадковою позицією в пошуковому просторі
  • До тих пір поки критерій переривання не досягнений (наприклад, виконано максимальну кількість ітерацій або досягнено необхідного фітнесу) повторювати наступне:
  • Вибирати нову позицію у з рівномірно розподілених точок на гіперсфері заданого радіусу d що оточує поточну позицію х. Для цього потрібно зробити наступне:
  1. Згенерувати n-вимірний гаусівський вектор з мат. сподіванням в точці 0 і довільною дисперсією:
  2. Обрахувати радіус цього вектору (відстань від початку координат):
  3. Тоді рівномірно розподілений вектор заданого радіусу d можна знайти як
  • Якщо (f(y) < f(x)) — переходити на нову позицію заданням x = y
  • Тепер x має найкращу позицію.

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

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

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

Допустимими є, наприклад, параметри де 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.