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

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

Алгоритм 1

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

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

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

Алгоритм 2

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

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

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

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

Алгоритм 3

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

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

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

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

Алгоритм 4

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

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

 

7.5. Практична реалізація методу випадкового пошуку

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

(7.1)

Отже, для функції (7.1) розшукується сукупність параметрів, які забезпечують її мінімум за наявності обласних

і функціональних обмежень

У цих виразах – вектор параметрів, що змінюються безперервно та діють в задачі оптимізації, та який записується у вигляді

де n – кількість параметрів, що розглядаються.

Поставлена задача оптимізації (7.1) з урахуванням обласних і функціональних обмежень є складною нелінійною задачею.

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

З урахуванням функціональних обмежень вираз для цільової функції набуде вигляду

(7.2)

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

У цьому виразі , якщо і-е обмеження не порушується і , якщо і-е обмеження порушується; – додатний коефіцієнт пропорційності; – порушене функціональне обмеження; m – кількість обмежень.

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

Отже, метод штрафних функцій полягає в переході від задачі (7.1) до послідовності задач безумовної оптимізації (7.2) з наступним їх розв'язуванням яким-небудь методом безумовної оптимізації, зокрема методом випадкового пошуку.

На рис. 7.9 для прикладу наведена геометрична інтерпретація методу випадкового пошуку для задачі з однією змінною.

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

де – вектор пам’яті;

– одиничний випадковий вектор;

R – параметр більший нуля.

Числове значення параметра R будемо узгоджувати з модулем вектора пам’яті. Це обумовлено тим, що при малих значеннях модуля вектор суттєво впливає на величину зміщення оскільки навчання в цьому випадку практично немає і пошук приймає чисто випадковий характер. Тому, коли модуль стає менше величини В, числове значення параметра R приймається рівним в протилежному випадку R приймається в діапазоні від 0,3 до 0,5.

Алгоритм навчання реалізується за допомогою рекурентної залежності:

У цій залежності k – параметр забування (менше 1); – параметр швидкості самонавчання (0,35 – 0,55); – приріст функції цілі на N-му кроці пошуку; d – параметр "скептицизму", що зменшує вплив функції цілі на напрямок переміщення в багатовимірному просторі.

Приріст функції цілі на N-му кроці пошуку

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

Новий стан вектора визначають за виразом

де а – довжина робочого кроку, загальна для всіх змінних.

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

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

де – значення кроку в попередній спробі; – коефіцієнт зростання; – коефіцієнт скидання. Для стійкості пошуку необхідно, щоб

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

Для врахування співвідношення між кількістю вдалих і невдалих спроб вводиться характеристична величина k, яка збільшується на при вдалій спробі та зменшується в разів при невдалій спробі:

Якщо вдалі і невдалі спроби чергуються, то k_і коливається навколо рівноважного положення. Налаштування робочого кроку а ставиться у відповідність до величини k_і.

Для врахування обласних обмежень після визначення нового положення вектора передбачені перевірки, які виконуються для кожного з n параметрів:

При виході значення j змінної з допустимого інтервалу приймає в залежності від ситуації рівними верхній або нижній межі.

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

Цим самим передбачається, що система є повністю навченою.

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