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

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

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

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

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

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

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

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

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

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

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

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

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

,

де

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

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

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

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

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

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

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

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

.

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

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

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

де – найкраща точка в гіперквадратні на k-мy етапі.

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

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

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

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

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