Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Контакти
 


Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция






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

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

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

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

 

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

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

Алгоритм складається із трьох вкладених циклів. Зовнішній цикл передбачає перехід від k – го до k +1 – го етапів пошуку оптимальної точки. Перехід виконується в тому випадку, коли на k – му етапі ми не повертаємось в початкову точку пошуку Х0 (блок 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 – му етапі ми повертаємось в початкову точку пошуку Х0 і зменшуємо крок, то зменшення кроку виконується до його мінімального значення eh після якого можливий вихід із пошуку оптимальної точки (блок 15).

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

( 8.3 )

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

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

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

 

 

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

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

, де . ( 4 )

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

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

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

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

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

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

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

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

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

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

 

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

 


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

  1. Автоматизація водорозподілу на відкритих зрошувальних системах. Методи керування водорозподілом. Вимірювання рівня води. Вимірювання витрати.
  2. Агрегативна стійкість, коагуляція суспензій. Методи отримання.
  3. Адаптовані й специфічні методи дослідження у журналістикознавстві
  4. Адміністративні (прямі) методи регулювання.
  5. Адміністративні методи - це сукупність прийомів, впливів, заснованих на використанні об'єктивних організаційних відносин між людьми та загальноорганізаційних принципів управління.
  6. Адміністративні методи управління
  7. Адміністративні, економічні й інституційні методи.
  8. Адміністративно-правові (організаційно-адміністративні) методи мотивації
  9. Адміністративно-правові методи забезпечення економічного механізму управління охороною довкілля
  10. Аерометоди
  11. Активні групові методи
  12. Алгоритм розробки методичних основ бюджетування




Переглядів: 1634

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

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

 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


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