Лекція 24

ІНТЕРАТИВНІ МЕТОДИ ПОШУКУ ОПТИМУМА

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

Градієнтом функції q (x), позначається grad q (x) або q (x), називається вектор, величина якого визначає швидкість зміни функції, а напрям збігається з напрямом найбільшого зростання цієї функції. Вектор - q (x), який вказує напрямок найбільшого убування функції q (x) називається антіградіентом функції q (x).

Нехай x=(x⁽ⁱ⁾, …, x⁽ⁿ⁾). Тоді градієнт функції q (x) буде представляти собою вектор-стовпець виду:

Умова того, що точка х є стаціонарною точкою функції q (x), за допомогою градієнта запишеться у вигляді:

Для обґрунтування ітераційних алгоритмів оптимізації розкладемо функцію q (x) в ряд Тейлора в околиці точки оптимуму х^*, яку вважаємо стаціонарною. Скористаємося виразом для ряду Тейлора в такій формі:

(24.1)

де Dх=х^*-х - відхилення від точки оптимуму.

(24.2)

Беручи приватні похідні від q (x) по x⁽ⁱ⁾,,знаходимо складові градієнта функції q (x) у розглянутій точці х:

(24.3)

Для градієнта функції q (x) при цьому одержуємо вираз:

(24.4)

де А - квадратна симетрична матриця розміром n ´ n, з елементами a_ki.

Вирішуючи систему рівнянь (24.4) щодо х^*, отримаємо:

(24.5)

Якби розкладання (24.1) було точним, уявленням q (x) і існували б прості методи визначення матриці А, то значення х^* можна було б знайти безпосередньо за формулою (24.5). У більшості практичних задач ці умови практично не виконуються.

Однак, якщо замінити невідому матрицю А^-1 на матицю Г з елементами g_kj, то можна сподіватися, що величина при відповідному виборі коефіцієнта g_kj дає значення, близьке до оптимального (більш, ніж х). При цьому відкривається можливість багатокрокової процедури пошуку рішення.

Позначимо x_n значення х на n-му кроці і будемо вважати, що елементи матриці Г можна вибирати на різних кроках по-різному. Тоді відповідно до (24.5) багатокрокова процедура пошуку оптимуму функції q (x) запишеться у вигляді:

(24.6)

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

Іноді алгоритм оптимізації записують у вигляді:

де - є вектором поправок.

На рис. 24.1 представлена ​​структурна схема алгоритму пошуку оптимуму за виразами (24.5)

Початок пошуку (введення вихідних даних)

ОбчисленняÑq(x)

Чи досягнений оптимум? Ñq(x)=0

Визначення матриці Г

Обчислення вектора помилок п

Визначення нової точких

Так

Припинення пошуку

Ні

Рисунок 24.1 - Структурна схема алгоритму пошуку оптимуму

Якщо цільова функція q (x) - функція двох змінних, тобто х (х (1), х (2)), то вона може бути зображена у вигляді деякої поверхні, що має вид улоговини і званої поверхнею відгуку. Профіль цієї улоговини можна зобразити на площині у вигляді ліній рівних значень q, що представляють собою перетину улоговини горизонтальними площинами. Ці лінії називаються лініями рівня.

Рис.24.2 - Поверхня відгуку (а) і її зображення у вигляді ліній рівня.

Градієнтний метод.

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

Отримана при цьому стратегія, називається градієнтним методом, буде представляти собою послідовність кроків, кожен з яких містить дві операції:

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

2) переміщення у вибраному напрямку на задану відстань.

Особливістю траєкторії при градієнтному способі є те, що кожен крок відбувається в напрямі, перпендикулярному лінії постійного рівня.

Математично стратегія градієнтного виходить, якщо переміщення Dx⁽ⁱ⁾ на кожному кроці вздовж кожної з осей буде пропорційно складової градієнта в напрямку цієї осі:

Це означає, що матриця Г_n у виразі (24.6) буде діагональною з елементами g на головній діагоналі

При цьому поправка на n-му кроці може бути представлена ​​у вигляді:

(24.7)

Стратегія, що виражається співвідношенням (24.7) визначає рух зі змінним кроком, тому що значення кроку визначається значенням градієнта. Оскільки значення градієнта зменшується на пологих схилах і поблизу оптимуму, то на деяких ділянках кроки будуть дрібними, що подовжує час пошуку.

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

що виходить з формули заміною вектора градієнта на вектор напрямку градієнта

Де - Являє собою модуль градієнта

q (x).

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

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

Метод найшвидшого спуску (підйому).

На відміну від градієнтного методу, в якому градієнт визначається на кожному кроці, в точці найшвидшого спуску градієнт визначається тільки в початковій точці і рух в знайденому напрямі триває однаковими кроками до тих пір, поки зменшується значення функції q (x). Якщо на кожному кроці q (x) зросла, то рух в даному напрямку припиняється, останній крок знімається повністю, або наполовину і обчислюється новий градієнт функції q (x), а значить, і новий напрямок руху. На рис. 24.3 показаний характер траєкторії при використанні методу найшвидшого спуску, а на рис. 24.4 наведена структурна схема алгоритму цього методу.

Рис.24.3 – Характер траєкторії алгоритму найбистрішого спуску.

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

Вичислення градієнта

Чи досягнутий оптимум

Вичислення вектора поправок Dх

Визначення нової точки х

q_n < q_n-1

Ні Так

Рисунок 24.4 - Структурна схема алгоритму пошуку мінімуму.

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

Оскільки розглянуті методи відносяться до класу локальних методів, при яких напрям і величина наступного кроку визначаються шляхом вивчення обмеженої ділянки поверхні q (x) поблизу точки, що є результатом попереднього кроку, то можливість отримання глобального оптимуму цілком залежить від вдалого вибору початкової точки. У цих умовах доцільним виявляється багаторазовий пошук екстремуму на різних початкових точках. Один з алгоритмів, що реалізують такий спосіб, може бути наступним:

Випадковим чином вибираємо х = х₁ і з цієї точки ведемо пошук локального оптимуму q₁ = q (x₁^*). Значення х₁^* і q₁ запам'ятовуємо. Потім випадковим чином вибираємо нове значення х = х₂ і відшукуємо відповідний локальний оптимум

q₂ = q (x₂^*). Якщо q₁ <q₂, то q₁ і х₁^* забуваємо і зберігаємо в пам'яті q₂ і х₁^*. Якщо ж q₂ > q₁, то вважаємо вибір точки х₂ невдалим і забуваємо результати пошуку. Потім знову виробляємо випадковий вибір точки х і пошук локального оптимуму і т.д. Знайдене в кінці кожного етапу значення q (x^*) запам'ятовуємо, якщо воно краще зберігається в пам'яті.

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

Дата добавления: 2014-01-07