Методи покоординатного спуску

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

Відрізняються методи варіантами пошуку оптимуму при варіюванні значень кожного окремого параметру. В одному випадку цей параметр може змінюватись з постійним кроком і значення кроку буде зменшуватись при переході на новий k + 1 -й етап пошуку. Такий метод називається методом покоординатного спуску із зменшенням кроку (рис. 8.4). В іншому випадку пошук по осі кожної координати буде виконуватись одним із методів однопараметричної оптимізації, як то – діленням відрізку пополам, золотого розтину, квадратичної апроксимації. Цей метод називається методом покоординатного спуску із одновимірною оптимізацією.

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

8.2.1. Метод покоординатного спуску із зменшенням кроку

Алгоритм методу наведений на рис. 8.5. В алгоритмі Х⁰ – це початкова точка пошуку, n- вимірний вектор значень параметрів оптимізації х_і⁰ в нульовій, початковій точці, Н – вектор початкових значень кроків пошуку h_і , де і = 1,2,...n, n – кількість параметрів оптимізації, k – номер етапу пошуку, e – задана точність, деяке задане мале число e > 0, e_h – найменший допустимий крок пошуку мінімального значення, с – коефіцієнт зменшення кроку 0 < c < 1 , s – лічильник напрямку руху до мінімуму, він дорівнює 1, коли цільова функція від однієї точки пошуку до іншої зменшується і 0, коли починає зростати.

Алгоритм складається із трьох вкладених циклів. Зовнішній цикл передбачає перехід від k – го до k +1 – го етапів пошуку оптимальної точки. Перехід виконується в тому випадку, коли на k – му етапі ми не повертаємось в початкову точку пошуку Х⁰ (блок 13) або коли ще не виконується перевірка умови заданої точності (блок 16).

( 8.2 )

При переході на k +1 – й етап поточна точка пошуку запам’ятовується як нульова, а вектор кроків пошуку зменшується на коефіцієнт зменшення кроку (блок 17). У випадку, коли після виконання пошуку по всіх параметрах повертаємось знов у початкову точку, вектор кроків пошуку також зменшується на коефіцієнт с (блок 14) і виконується повторний пошук на етапі із зменшеним кроком.

При переході на внутрішній цикл спочатку створюється n- вимірний вектор поточних значень параметрів оптимізації Х, як нульова точка, і знаходиться значення цільової функції в нульовій точці F0. На початку пошуку це ж саме значення цільової функції також буде оптимальним F_опт (блоки 2,3).

Внутрішні цикли виконуються по і- тим параметрам оптимізації. Тут значення кожного і- го параметра х_і змінюється з постійним кроком h_і (блок 6). В процесі руху вздовж осі параметра обчислюється поточне значення цільової функції F, яке порівнюється з оптимальним, із запам’ятовуванням меншого значення (блоки 7, 8, 9). Якщо напрямок руху приводить до збільшення цільової функції, то знак кроку змінюється на протилежний (блок 11). При русі вздовж осі і- го параметра, інші параметри оптимізації вектора параметрів Х не змінюються. Контроль правильності руху і вихід із самого внутрішнього третього циклу, який і забезпечує цей рух, і перехід на інший параметр оптимізації, виконується за допомогою лічильника напрямку руху s (блоки 5 і 10). Після пошуку оптимуму при змінюванні всіх параметрів оптимізації вектор параметрів запам’ятовується, як оптимальний Х_опт.

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

В алгоритмі передбачено, що якщо на k – му етапі ми повертаємось в початкову точку пошуку Х⁰ і зменшуємо крок, то зменшення кроку виконується до його мінімального значення e_h після якого можливий вихід із пошуку оптимальної точки (блок 15).

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

( 8.3 )

Рис. 8.5. Схема алгоритму оптимізації методом покоординатного спуску із зменшенням кроку

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

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

8.2.2.Метод покоординатного спуску з одновимірною оптимізацією

Для зменшення кількості етапів пошуку оптимального значення при проходженні по координаті і-го параметру можна використати методи одновимірної оптимізації. Такий метод називається методом покоординатного спуску з одновимірною оптимізацією, або метод Гаусса-Зейделя. Його краще використовувати при безумовній оптимізації, або при двосторонніх обмеженнях виду а_і < x_i < b_i. При розв’язанні задачі даним методом нам необхідно знаходити оптимальне (мінімальне) значення з використанням одного із методів однопараметричної оптимізації, як то: діленням відрізка навпіл, золотого розтину або квадратичної інтерполяції.

, де . ( 4 )

При знаходженні оптимального значення для кожного х_і параметра туди переміщується проміжне означення оптимуму і фіксується вектор координат решти параметрів оптимізації. Остання точка пошуку при проходженні всіх параметрів запам’ятовується як точка k + 1 .

Схема алгоритму методу показана на рис. 8.6.

На схемі початку вводяться: початкова точка пошуку Х⁰, і вектори двосторонніх обмежень A і B. Також вводиться точність обчислень e і максимально можливе значення числа ітерацій – k_max ( блок 1).

Далі формується вектор поточних значень параметрів оптимізації і знаходиться нульове значення цільової функції F0 (блок 2, 3).

У внутрішньому циклі виконується однопараметрична оптимізація по одному із методів по всіх і – тих параметрах оптимізації і знаходиться k + 1 – шаточка оптимуму (блоки 4, 5, 6). Координати параметрів цієї точки запам’ятовуються, як Х_опт.

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

Якщо точність не досягнута і лічильник кроків не перевищив свого обмеження, то вектор параметрів оптимізації поточної точки оптимуму запам’ятовується як нульовий, а номер кроку зростає (блок 10).

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

Рис. 8.6. Схема алгоритму оптимізації методом покоординатного спуску із одновимірною оптимізацією

8.3. Методи випадкового пошуку

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

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
	\|	Метод випадкового пошуку з перерахунком

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.004 сек.