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 змінної з допустимого інтервалу приймає в залежності від ситуації рівними верхній або нижній межі.

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

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

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

11

Лекція №7 Оптимізація та прийняття рішень