РОЗДІЛ 2
МАТЕРІАЛИ ТА МЕТОДИ ДОСЛІДЖЕНЬ
2.1. Пошук мінімуму функції методом деформованого багатогранника (симплекс
метод)
Метод деформованого багатогранника (його ще називають симплекс метод) – це
метод пошуку екстремальних значень функції (мінімізації функції), що не
потребує обчислення похідної. Отже, метод деформованого багатогранника не є
градієнтним методом і застосовується для оптимізації функцій, похідну яких
обчислити неможливо (або дуже складно). Симплекс-метод вирізняється двома
своїми особливостями. По-перше, він дозволяє знаходити дуже глибокі мінімуми
функцій і часто досягати найкращих серед неградієнтних методів результатів
оптимізації. Другою його особливістю є надзвичайна ресурсоємність. Ці дві
особливості визначають сферу його застосування. Якщо задача потребує одного
розрахунку, який повинен бути знайдений з високою точністю, то здебільшого
обирають саме симплекс-метод, іноді це навіть стосується задач, де можливе
застосування градієнтних методів. Особливо цікавим цей метод є, зокрема, для
задач параметризації параметрів, коли необхідно провести один точний розрахунок
підгонки параметрів під вибірку еталонних випадків і надалі просто
застосовувати знайдені оптимальні параметри для моделювання нових об’єктів.
Вперше метод деформованого багатогранника запропонований Нелдером та Мидом
[104]. Метод, який вони запропонували, виявився дуже ефективним і легко
реалізувався на обчислювальних машинах. Ідея методу полягає в моделюванні сфери
(м’яча) в d-розмірному просторі, яка буде котиться по гіперплощині утвореній
значеннями функції від d змінних. Така сфера спочатку моделювалася правильним
багатогранником. З аналітичної геометрії відомо, що в d-вимірному просторі d+1
точок, що не лежать в одній гіперплощині, визначають унікальну сферу. Для
випадку двовимірного простору таким багатогранником буде трикутник, для випадку
тривимірного простору це тетраедр і т.д. У методі деформованого багатогранника
d+1 точка задають багатогранник і відтак – сферу. Отримана сфера починає
ітеративне кочення по поверхні функції f(x). Кочення відбувається наступним
чином. Визначається точка сфери, яка лежить вище за інших, тобто така вершина х
багатогранника, де значення f(x) більше, ніж у всіх інших його вершинах. З цієї
точки через центр мас багатогранника відбувається проектування вершини на
достатню відстань. Отримана нова вершина заміщує собою вершину, з якої
проводилося проектування, центр мас багатогранника розраховується знову і
ітерація повторюється. Новий багатогранник, утворений шляхом проектування
найгіршої точки через свій центр мас, має назву відображеного багатогранника, а
сам процес називається відображенням. Для того, щоб зробити такий алгоритм
стійким до нього додають процедури запобігання циклічним флуктуаціям в
геометрії багатогранника та ізометричне зменшення багатогранника навколо свого
центру мас [105].
Ініціалізація методу відбувається шляхом побудови правильного багатогранника. З
аналітичної геометрії відомо, що правильний багатогранник задається матрицею
векторів координат вершин виду:
– матриця розміру n рядків і (n+1) стовпців,
де , . Оскільки у більшості задач відомо деяку стартову перспективну точку
(здогадка) то приведена вище матриця D є лише матрицею зміщення і до кожного
стовпця координат вершини необхідно додати вектор здогадки для сканування
рельєфу функції f(x) безпосередньо в околі перспективної ділянки простору.
Оскільки для ініціації методу використовують правильний багатогранник, який
називається симплекс, то алгоритм працює з недеформованим багатогранником.
Такий метод дуже ефективний при роботі з “добрими” функціями, але відчуває
серйозні проблеми при роботі з “поганими” функціями. “Добрі” функції мають
гарно виражений екстремум і достатньо стрімкі стінки поверхні, що ведуть до
екстремуму. “Поганими” є функції, що містять платоподібний рельєф в достатньо
великому околі від екстремуму. Для “поганих” функцій алгоритму досить складно
вибрати правильний вектор кочення і траєкторія симплекса стає близькою до
хаотичної, що значно сповільнює кількість аналізованих точок, необхідних для
вирішення задачі з заданою точністю. Для боротьби з цією проблемою
запропоновано модифікацію методу відому як метод деформованого багатогранника.
Її ідея полягає в тому, щоб дозволити багатограннику адаптуватися під рельєф
функції. Тоді обчислення центру мас та вектору кочення буде скореговане
локальними обставинами поверхні значень функції, що дозволяє суттєво поліпшити
ефективність методу у випадку “поганих” та не досить “добрих” функцій.
Деформований багатогранник на відміну від недеформованого симплексу адаптується
до топографії цільової функції, витягуючись вздовж довгих нахилених площин,
змінюючи напрям у вигнутих впадинах та стискуючись в околі мінімуму.
У методі деформованого багатогранника знову ж таки використовують d+1 вершин
для оптимізації функції d змінних. Спочатку, аналогічно методу недеформованого
багатогранника, проводиться пошук найгіршої вершини. Однак процедура
проектування точки відбувається не через центр мас симплекса, а через центр мас
всіх інших вершин крім найгіршої. Далі найгірша точка замінюється на нову кращу
і ітерація повторюється.
Більш детально такий алгоритм виглядає так. Нехай , і = 1 ... d+1 є i-тою
вершиною (точкою) в d-вимірному просторі на k-му етапі пошуку, k = 0, 1, …, і
нехай значення цільової функції в x(k)i рівно f(x(k)i). Крім того, відмітимо ті
вектори x багатогранника, які дають максимальне та мінімальне значення f(x).
Визначимо , де , та позначимо , де . Оскільки d-вимірний багатогранник
складається з (d+1) ве
- Київ+380960830922