Розділ 2
Методи оптимізації і їх використання для побудови макромоделей
2.1. Коротка характеристика методів оптимізації
Задача оптимізації полягає в знаходженні екстремуму деякої функції мети на
деякій області , на якій функція вважається неперервною й диференційованою.
Використовувані методи розв'язку даної задачі поділяються на методи глобальної
й локальної оптимізації у залежності від того, чи розраховані вони на пошук
екстремуму для функції мети, що є багатоекстремальною (методи глобальної
оптимізації), чи функції мети, що має лише один екстремум (методи локальної
оптимізації). Глобальна оптимізація є більш загальним випадком, оскільки
включає в себе локальну оптимізацію як завершальну стадію, проте є набагато
складнішим завданням і на даний час не завжди успішно вирішується на практиці.
2.1.1. Детерміновані методи оптимізації
В детермінованих методах оптимізації кожен крок жорстко детемінований
попередніми:
, (2.4)
де - деякий функціонал.
До переваг цих методів слід віднести їх прогнозованість, а також відносно
швидке знаходження розв'язку для певного класу функцій. Основним їх недоліком є
чутливість до різного роду "пасток", в тому числі і висока чутливість до
похибок округлення, швидке зростання затрат при зростанні розмірності задачі та
складність застосування для глобальної оптимізації.
До детермінованих методів належать:
Градієнтний спуск. На кожній ітерації відбувається пошук мінімуму в напрямку,
протилежному до напрямку градієнта. Даний метод ефективно працює на відносно
невеликому класі функцій, а також вимагає розрахунку значення градієнта, що
приводить до значних обсягів обчислень.
Метод Ньютона. Екстремум знаходиться як розв'язок системи нелінійних рівнянь:
(), (2.5)
яка розв'язується методом ітерацій Ньютона.
Даний метод володіє кращою збіжністю ніж метод градієнтного спуску, зокрема, в
області, близькій до розв'язку, проте вимагає знаходження значень других
похідних, що вимагає значних обчислювальних затрат. Крім того, він є
малоефективний в областях, далеких від точки мінімуму.
Метод важкої кульки. В цьому методі моделюється рух кульки з деякою масою з
врахуванням тертя в потенціальному полі, що задається функцією мети.
Вважається, що кулька повинна зупинитися в точці мінімуму.
Метод важкої кульки має досить непогані властивості як алгоритм глобальної
оптимізації, оскільки "кулька" має здатність "проскакувати" локальні мінімуми,
проте швидкість збіжності даного методу не є високою.
У методі покоординатного спуску пошук мінімуму відбувається шляхом послідовної
оптимізації вздовж однієї з координат. При цьому решта параметрів залишається
сталими. Після того як було знайдено мінімуми вздовж кожної з координатних
осей, цикл повторюється. Такий алгоритм працює повільно, якщо присутня взаємна
кореляція параметрів функції мети, що практично завжди має місце на практиці.
Метод обертання координат (Розенбока) є продовженням методу покоординатного
спуску і полягає в переорієнтації координатних осей перед кожним циклом таким
чином, щоб одна з координат у новій системі була спрямована вздовж дна яру.
Метод деформованого багатогранника (Недлера-Міда). Мінімізація проводиться з
використанням вершини багатогранника. На кожній ітерації вершина, в якій
значення функції мети максимальне, проектується через центр ваги решти вершин.
У випадку деформованого багатогранника, якщо в новій точці на ітерації функція
мети виявилася меншою за її значення в усіх інших точках, то багатогранник
витягується в даному напрямку, а якщо вона виявилася більшою за значення
функції мети в 2-х або більше інших точках багатогранника, то він стискується в
даному напрямку. Таким чином форма й розміри багатогранника змінюються в
залежності від локальних властивостей функції мети.
Як показує практика, детерміновані методи оптимізації ефективні при знаходженні
локальних екстремумів в умовах відсутності крутих і довгих ярів. Як уже
згадувалося раніше, саме наявність крутих і довгих ярів є характерною
особливістю оптимізаційних задач, що виникають при побудові макромоделей
електромеханічних об'єктів із використанням оптимізації.
2.1.2. Стохастичні методи оптимізації
Стохастичні методи оптимізації базуються на використанні випадкової
послідовності при побудові послідовності кроків:
, (2.3)
де - деякий функціонал, - випадкова величина. Введення випадкової величини
робить стохастичні алгоритми набагато менш чутливими до всякого роду "пасток".
Другою великою перевагою статистичних методів оптимізації є їх відносно легке
використання для проведення глобальної оптимізації, а також їх придатність для
розв'язування задач високої розмірності.
Розглянемо спочатку найпростіші методи статистичної оптимізації, які не
використовують передісторії пошуку. До таких методів слід віднести наступні:
Метод хаотичного пошуку, в якому ітерації робляться хаотично з рівномірним
законом розподілу. Теоретично, цей метод придатний для розв'язання будь-якої
оптимізаційної задачі, проте практичного застосування він не має внаслідок
надто повільної збіжності.
Алгоритм з парною пробою. На кожному кроці робиться пара проб у протилежних
напрямках відносно біжучої точки:
, (2.4)
де – випадковий одиничний вектор.
Робочий крок робиться в напрямі найменшого значення функції мети. Основним
недоліком даного методу є його здатність "блукати" в околі мінімуму.
Алгоритм із перерахунком. У просторі параметрів робиться крок у випадковому
напрямі. Якщо значення функції мети в новому стані зменшилось, крок
приймається, в протилежному випадку – відкидається.
Випадковий спуск. У просторі параметрів робиться крок у випадковому напрямі.
Якщо значення функції мети в но
- Київ+380960830922