Ненаправлений випадковий пошук

Простий випадковий пошук

Передбачається, що шуканий мінімум знаходиться в деякому n-вимірному паралелепіпеду. В цьому паралелепіпеді за рівномірним законом вибирають випадковим чином N пробних точок і розраховують в них цільову функцію. Точку, в якій функція має мінімальне значення, беруть як рішення задачі. Проте навіть при дуже великій кількості пробних точок ймовірність того, що хоча б одна точка попаде в невеликій окіл локального мінімуму, мізерно мала. Дійсно, нехай N = 106 і діаметр котловини околу мінімуму становить 10 % від лімітів зміну кожної координати. Тоді об’єм цієї котловини становить 0,1n частину n-вимірного паралелепіпеда. Вже при числі n > 6 практично жодна точка в котловину не попаде.

Тому беруть невелику кількість точок N = (5…20)n і кожну точку розглядають як нульове наближення. З кожної точки здійснюють спуск, швидко попадаючи в найближчий яр або котловину; коли кроки спуску швидко вкорочуються, його припиняють, не домагаючись високої точності. Цього вже достатньо, щоб зробити висновки про величину функції в найближчому локальному мінімуму з задовільною точністю. Порівнюючи остаточні значення функції на всіх спусках, можна з’ясувати розташування локальних мінімумів і заставити їх величини. Після цього можна відібрати потрібні за змістом задачі мінімуми і провести в них додаткові спуски для отримання координат точок мінімуму з більш високою точністю.

При розв’язанні екстремальних задач на областях зі складною геометрією зазвичай цю область вписують n-вимірний гіперпаралелепіпед, в якому генерують випадкові точки за рівномірним законом розподілу, залишаючи тільки ті, які попадають в допустиму область (рис. 7.1). На цьому рисунку А і В – границі паралелепіпеда.

Розрізняють направлений і ненаправлений випадковий пошук.

Ненаправлений випадковий пошук

Всі випадкові іспити будують цілковито незалежно від результатів попередніх. Збіжність такого пошуку дуже мала, але є важлива перевага: можливість розв’язувати багатоекстремальні задачі (шукати глобальний екстремум). Прикладом є розглянутий вище простий випадковий пошук.

 
  Ненаправлений випадковий пошук - student2.ru

7.3. Направлений пошук

У цьому випадку окремі іспити пов’язані між собою. Результати проведених іспитів використовують для формування наступних. Швидкість збіжності таких методів, як правило, вище, але самі методи зазвичай приводять до локальних екстремумів.

Розглянемо простіші алгоритми направленого випадкового пошуку.

7.3.1. Алгоритми парної проби

У цьому алгоритмі чітко розділені пробний і робочий кроки. Нехай хk – знайдене на – кроці найменше значення функції f(x), що мінімізується. За рівномірним законом розподілу генерується випадковий одиничний вектор ξ і по обидві сторони від вихідної точки хk виконуються дві проби: проводять розрахунки функції в точках Ненаправлений випадковий пошук - student2.ru , де g – величина пробного кроку (рис. 7.2). Робочий крок виконується в напрямку найменшого значення цільової функції. Чергове приближення визначається співвідношенням

Ненаправлений випадковий пошук - student2.ru ,

де Ненаправлений випадковий пошук - student2.ru

 
  Ненаправлений випадковий пошук - student2.ru

Особливістю цього алгоритму є його підвищена тенденція до "блукання". Навіть знайшовши екстремум, алгоритм уводить систему в бік.

7.3.2. Алгоритм найкращої проби

 
  Ненаправлений випадковий пошук - student2.ru

На k-му кроці маємо точку Ненаправлений випадковий пошук - student2.ru . Генеруються m випадкових одиничних векторів Ненаправлений випадковий пошук - student2.ru . Виконуються пробні кроки в напрямках Ненаправлений випадковий пошук - student2.ru і в точках Ненаправлений випадковий пошук - student2.ru розраховуються значення функції (рис. 7.3). Вибирається той крок, який призводить до найбільшого зменшення функції Ненаправлений випадковий пошук - student2.ru . У даному напрямку робиться крок Ненаправлений випадковий пошук - student2.ru . Параметр може визначатися як результат мінімізації за визначеним напрямком або вибирається за визначеним законом.

Зі збільшенням кількості спроб вибраний напрямок наближається до напрямку антиградієнта Ненаправлений випадковий пошук - student2.ru .

Якщо функція Ненаправлений випадковий пошук - student2.ru близька до лінійної, то є можливість прискорити пошук, вибираючи разом з найкращою і найгіршу пробу. Тоді робочий крок можна зробити або в напрямку найкращої проби, або в напрямку, протилежному найгіршій пробі.

7.3.3. Метод статистичного градієнта

З вихідного стану хk виконуються m незалежних проб Ненаправлений випадковий пошук - student2.ru і розраховуються в цих точках відповідні значення функції, що мінімізується (рис. 7.4). Для кожної проби запам’ятовуються прирости функції

 
  Ненаправлений випадковий пошук - student2.ru

Ненаправлений випадковий пошук - student2.ru

Після цього формується векторна сума Ненаправлений випадковий пошук - student2.ru Ненаправлений випадковий пошук - student2.ru В межі при Ненаправлений випадковий пошук - student2.ru вона збігається з напрямком градієнта цільової функції. При скінченому m вектор Δf є статистичною оцінкою напрямку градієнта. Робочий крок робиться в напрямку Δf. Чергове наближення визначається співвідношенням

Ненаправлений випадковий пошук - student2.ru .

При виборі оптимального значення , яке мінімізує функцію в заданому напрямку, отримують випадковий варіант методу найшвидшого спуску. Суттєвою перевагою перед детермінованими алгоритмами є можливість прийняття рішення про напрямок робочого кроку при Ненаправлений випадковий пошук - student2.ru . При Ненаправлений випадковий пошук - student2.ru і невипадкових ортогональних робочих кроках, направлених вздовж осей координат, алгоритм вироджується в градієнтний метод.

7.3.4. Алгоритм найкращої проби з напрямним гіперквадратом

Всередині допустимої області будується гіперквадрат. В цьому гіпеквадраті випадковим чином розкидаються m точок Ненаправлений випадковий пошук - student2.ru , в яких розраховують значення функції (рис. 7.5). Серед побудованих точок вибирають найкращу. Спираючись на цю точку, будують новий гіперквадрат. Точка, в якій досягається мінімум функції на k-мy етапі, береться за центр нового гіперквадратна на (k + 1)-мy етапі. Координати вершин гіперквадрата на (k + 1)-мy етапі визначаються співвідношеннями

Ненаправлений випадковий пошук - student2.ru

 
  Ненаправлений випадковий пошук - student2.ru

де Ненаправлений випадковий пошук - student2.ru – найкраща точка в гіперквадратні на k-мy етапі.

В новому гіперквадраті виконують ту ж послідовність дій, випадковим чином розкидаючи m точок, і т. д.

Таким чином, на 1-му етапі координати випадкових точок задовольняють нерівностям Ненаправлений випадковий пошук - student2.ru і Ненаправлений випадковий пошук - student2.ru – точка з мінімальним значенням цільової функції.

В алгоритмі з навчанням сторони гіперквадратна можуть регулюватися відповідно зі зміною параметра за деяким правилом. У цьому випадку координати вершин гіперквадраа на (k + 1)-мy етапі будуть визначатися співвідношеннями

Ненаправлений випадковий пошук - student2.ru

Добре вибране правило регулювання сторони гіперквадратна приводить до достатньо ефективного алгоритму пошуку.

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

Наши рекомендации