7.4. Алгоритми глобального пошуку

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

Алгоритм 1

У допустимій області D випадковим чином вибирають точку Прийнявши її за вихідну точку і застосовуючи деякий детермінований метод або алгоритм направленого випадкового пошуку, виконується спуск в точку локального мінімуму (рис. 7.6).

Потім вибирають нову випадкову точку і за тією ж схемою виконують спуск в точку локального мінімуму і т. д.

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

Алгоритм 2

Нехай отримана деяка точка локального екстремуму . Після цього переходять до ненаправленого випадкового пошуку до отримання точки х₂ такої, що

Із точки х₂ за допомогою детермінованого алгоритму або направленого випадкового пошуку отримують точку локального екстремуму , в якій свідомо виконується нерівність

Далі за допомогою випадкового пошуку визначають нову точку х₃, для якої справедлива нерівність , і знову виконується спуск в точку локального екстремуму і т. д.

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

Алгоритм 3

Нехай – деяка вихідна точка пошуку в області D, із якої відбувається спуск в точку локального екстремуму зі значенням Далі із точки рухаються або у випадковому напрямку, або в напрямку до тих пір, поки функція знову не почне спадати (виходимо з "області тяжіння" ). Отримана точка приймається за початок наступного спуску. В результаті знаходимо новий локальний екстремум і значення функції (рис. 7.7).

Я кщо , то точка забувається і її місце займає точка . Якщо , то повертаємося в точку і рухаємося з неї в новому випадковому напрямку.

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

Цей метод дозволяє знаходити глобальний екстремум у випадку багатозв’язних допустимих областей.

Алгоритм 4

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

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