Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
РТ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2008
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Методи синтезу та оптимізації
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
Національний університет “Львівська політехніка”
Дослідження методів багатопараметричної оптимізації на прикладі методів прямого пошуку
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи № 4
з курсу “Методи синтезу та оптимізації”
для студентів базового напряму 6.08.04 “Компютерні науки”
ЗАТВЕРДЖЕНО
На засіданні кафедри САПР
Протокол № 1 від 28.08. 2008 р.
ЛЬВІВ 2008
Дослідження методів багатопараметричної оптимізації на прикладі методів прямого пошуку. Методичні вказівки до лабораторної роботи № 4 з курсу “Методи синтезу та оптимізації” для студентів базового напряму 6.08.04 “Компютерні науки” /Укл. Теслюк В. М., Андрійчук М. І. – Львів: НУ “ЛП”, 2008 р.
Укладачі: Теслюк Василь Миколайович, к.т. н., доцент; Андрійчук Михайло Іванович, к. ф.-м. в., доцент.
Відповідальний за випуск: Ткаченко С. П., к.т. н., доцент
Рецензенти: Каркульовський В. І., к.т. н., доцент,
Стех Ю. В., к.т. н., доцент
1. МЕТА РОБОТИ
Вивчити основні методи багатопараметричної оптимізації на основі алгоритмів прямого пошуку
2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Прямі методи
Прямі методи, або методи нульового порядку не вимагають знання цільової функції в явному вигляді. Вони не вимагають регулярності і неперервності цільової функції й існування похідних. Це є істотною перевагою при розв’язуванні складних технічних і економічних задач. При реалізації прямих методів істотно скорочується етап підготовки рішення задачі, тому що немає необхідності у визначенні перших і других похідних. Прямі методи в основному носять евристичний характер. До прямих методів відноситься цілий ряд алгоритмів, що відрізняються по своїй ефективності. Методи призначені для рішення безумовних задач оптимізації
.
Алгоритм Гауса
Це найпростіший алгоритм, що полягає в тому, що на кожному кроці (кожній ітерації) мінімізація здійснюється тільки по одній компоненті вектора змінних .
Нехай нам дане початкове наближення . На першій ітерації знаходимо значення мінімуму функції при першій координаті, що змінюється, і фіксованих інших, тобто
.
Рис. 1.
У результаті одержуємо нову точку . Далі з точки шукаємо мінімум функції, змінюючи другу координату і вважаючи фіксованими всі інші координати. У результаті одержуємо значення
і нову точку . Продовжуючи процес, після кроків одержуємо точку , починаючи з якої процес відновлюється.
Як умови припинення пошуку можна використовувати наступні два критерії:
.
, .
Метод дуже простий, але не дуже ефективний. Проблеми можуть виникнути, коли лінії рівня сильно витягнуті і "еліпсоїди" орієнтовані, наприклад, уздовж прямих виду . У подібній ситуації пошук швидко застряє на дні такого яру, а якщо початкове наближення виявляється на осі "еліпсоїда", то процес так і залишиться в цій точці.
Найбільш прийнятні результати виходять у тих випадках, коли цільова функція являє собою опуклу сепарабельну функцію виду
.
Метод пошуку по симплексу ( метод)
Робота симплексного методу починається з побудови регулярного симплекса в просторі незалежних змінних і оцінювання цільової функції в кожній з вершин симплекса. При цьому визначається вершина, якій відповідає найбільше значення цільвої функції.
а б
Рис. 2. Побудова нового симплекса.
а – початковий симплекс ; б – новий симплекс .
Після цього знайдена вершина проектується через центр ваги інших вершин симплекса в нову точку, яка використовується як вершина нового симплекса. Якщо функція спадає достатньо плавно, ітерації продовжуються доти, поки або не буде накрита точка мінімуму, або не почнеться циклічний рух по двох чи більше симплексах. В таких ситуаціях можна скористатись наступними трьома правилими.
Правило 1. “Накриття” точки мінімуму.
Якщо вершина, якій відповідає найбільше значення цільової функції, побудована на попередній ітерації, то замість неї береться вершина, якій відповідає наступне по величині значення цільової функції.
Правило 2. Циклічний рух.
Якщо деяка вершина симплекса не виключається на протязі більше ітерацій, то необхідно зменшити розміри симплекса з допомогою коефіцієнта редукції і побудувати новий симплекс, вибравши за базову точку ту, якій відповідає мінімальне значення цільової функціїх. Спендлі, Хекст і Хімсворт запропонували обраховувати по формулі
,
де - розмірність задачі, а заокруглюється до найближчого цілого числа. Для застосування даного правила вимагається встановлювати величину коефіцієнта редукції.
Правило 3. Критерій закінчення пошуку.
Пошук завершується, коли або розмір симплекса, або різниця між значеннями функції у вершинах стають достатньо малими. Щоб можна було застосувати це правило, необхідно задати величину параметра закінчення пошуку.
Реалізація даного алгоритму грунтується на обчисленнях двох типів: (1) побудові регулярного симплекса при заданих базовій точці і масштабному множнику та (2) розрахунку координат відображуваної точки. Побудова симплексу є достатньо простою процедурою, оскільки з елементарної геометрії відомо, що при заданих початковій (базовій) точці і масштабному множнику координати інших вершин симплекса в -вимірному просторі обчислюються за формулою
, .
Прирости і , що залежать тільки від і вибраного масштабного множника , визначаються за формулами
, .
Зауважимо, що величина масштабного множника вибирається дослідником, виходячи з особливостей задачі, яка розв”язується. При ребра регулярного симплекса мають одиничну довжину.
Обчислення другого типу, пов”язані з відображенням відносно центра ваги, також не є складної процедурою. Нехай - точка, яку потрібно відобразити. Центр ваги інших точок розміщений в точці
.
Всі точки прямої, яка проходить через і , задаються формулою
.
При отримуємо вихідну точку , тоді як значення відповідає центру ваги . Для того, щоб побудований симплекс володів властивістю регулярності, відображення повинно бути симетричним. Отже, нова вершина отримується при . Таким чином,
.
Проілюструємо обчислювальну схему методу наступним прикладом.
Приклад. Обчислення у відповідності з симплекс-методом.
Мінимізувати функцію .
Розв”язок. Для побудови початкового симплекса задомо початкову точку і масштабний множник. Нехай і . Тоді
, .
Використовуючи ці два параметри, обчислимо координати двох інших вершин симплекса:
,
,
яким відповідають значення цільової функції, рівні і . Оскільки, , то необхідно відобразити точку відносно центра ваги двох інших вершин симплекса
.
Використовуючи формулу для , отримаємо
,
.
В отриманій точці , тобто спостерігається зменшення цільової функції. Новий симплекс створюється точками , і . У відповідності з алгоритмом, необхідно відобразити точку , якій відповідає найбільше значення цільової функції, відносно центра ваги точок і . Ітерації продовжуються до тих пір, поки не виникне потреба застосування правил 1, 2 і 3, які були сформульовані вище.
Викладений вище алгоритм -методу має декілька очевидних переваг.
1. Розрахунки і логічна структура методу є досить простими, отже, відповідна програма для ПК виявляється досить простою.
2. Рівень вимог до обсягу пам”яті ПК невисокий, масив має розмірність .
3. Використовується порівняно невелика кількість наперед заданих параметрів: масштабний множник , коефіцієнт зменшення множника (якщо застосовується правило 2) і параметри закінчення пошуку.
4. Алгоритм виявляється ефективним навіть у тих випадках, коли похибка обчислення значень функції велика, оскільки при його реалізації оперують найбільшими значеннями функції у вершинах, а не найменшими.
Алгоритм володіє рядом суттєвих недоліків.
1. Не виключено виникнення труднощів, пов”язаних з масштабуванням, оскільки всі координати вершин симплекса залежать від одного і того ж масштабного множника . Щоб позбутися цих труднощів, в практичних задачах необхідно промасштабувати всі змінні з тим, щоб їх значення були порівняльні за величиною.
2. Алгоритм працює досить повільно, оскільки отримана на попередніх ітераціях інформація не використовується для прискорення пошуку.
3. Не існує простого способу розширення симплекса, який не вимагає перерахунку значень цільової функції у всіх точках зразка. Таким чином, якщо по якій-небудь причині зменшується (наприклад, якщо зустрічається область з вузьким “яром” або “хребтом”), то пошук повинен продовжуватись із зменшеною величиною кроку.
Алгоритм Хука і Джівса
У даному алгоритмі пропонується логічно проста стратегія пошуку, у якій використовуються апріорні знання про топологію функції і, у той же час, відкидаються уже застаріла інформація про цю функцію. В інтерпретації Вуда алгоритм включає два основних етапи:
пошук, що досліджує, навколо базисної точки ;
пошук по "зразку", тобто в напрямку, обраному для мінімізації.
Задається початкова точка пошуку і початкове збільшення (крок) , після чого починається пошук, що досліджує.
Пошук, що досліджує:
Робимо спробний крок по змінній , тобто визначаємо точку й вираховуємо значення функції для точки .
Якщо значення функції в даній точці більше, ніж значення функції , то робимо пробний крок по цій же змінній, але в протилежному напрямку. Якщо значення функції в точці також більше, ніж , то залишаємо точку без змін. Інакше заміняємо точку на чи на в залежності від того, де значення функції менше вихідного. Зі знову отриманої точки робимо пробні кроки по координатах, що залишилися, використовуючи той же самий алгоритм.
Якщо в процесі пошуку, що досліджує, не вдається зробити жодного вдалого пробного кроку, то необхідно скорегувати (зменшити). Після чого знову переходимо до пошуку, що досліджує.
Якщо в процесі пошуку, що досліджує, зроблений хоч один вдалий пробний крок, то переходимо до пошуку за зразком.
Пошук за зразком:
Після пошуку, що досліджує, ми одержуємо точку . Напрямок визначає напрямок, в якому функція зменшується. Тому проводимо мінімізацію функції в зазначеному напрямку, вирішуючи задачу
.
У пошуку по "зразку" величина кроку по кожній змінній пропорційна величині кроку на етапі пошуку, що досліджує. Якщо вдається зробити вдалий крок у пошуку по "зразку", то в результаті знаходимо нове наближення , де
.
З точки начинаем новий пошук, що досліджує, і т. д.
Рис. 3.
Існують модифікації алгоритму, у яких у процесі пошуку, що досліджує, шукається мінімум по кожної змінній чи в процесі пошуку за зразком шукається не мінімум функції, а просто робиться крок у заданому знайденому напрямку з фіксованим значенням параметра .
Максимізація функції двох змінних методом Хука-Джівса (приклад)
Приклад. Знайти максимум функції
,
початкове значення , .
Значення в початковій точці
I. Здійснюємо досліджуючий пошук типу I для визначення вдалого напрямку. (Така процедура називається досліджуючим пошуком типу I на відміну від досліджуючого пошуку типу II, який слідує за пошуком по зразку. Після проведення досліджуючого пошуку типу II приймається рішення з приводу того, чи був попередній пошук по зразку успішним, чи ні).
, , (неуспішно),
, , (успішно),
, , (неуспішно),
, , (успішно),
Досліджуючий пошук виявився успішним. Зауважимо, що при кожному пошуку вибирається останній вдалий вектор . Новим базисним вектором буде .
Тепер з точки проводимо пошук по зразку у відповідності із правилом акселерації
,
де - попередній базисний вектор . Вданому випадку, це початковий вектор
,
,
.
Нарешті, проводиться досліджуючий пошук типу II: успіх чи неуспіх його оцінюється шляхом порівняння з :
, , (неуспішно),
, , (успішно),
, , (неуспішно),
, , (успішно).
Щоб визначити, чи виявився пошук по зразку успішним, порівнюють з . Оскільки пошук по зразку є успішним то новою базисною точкою буде ; при цьому стара базисна точка представлена вектором .
Потім знову проводиться пошук по зразку
,
,
.
Після цього проводиться досліджуючий пошук типу I
, , (неуспішно),
, , (неуспішно),
, . (успішно).
Оскільки > , пошук по зразку вважається вдалим, і стає новою базисною точкою, а - старою базисною точкою.
Ця послідовність пошуків продовжується до тих пір, поки не буде досягнута ситуація, при якій в кінці досліджуючого пошуку типу II значення виявиться меншим, ніж значення в останній базисній точці. Тоді якщо навіть досліджуючий пошук типу II є успішним при одній або більше змінах , то вважається, що останній пошук по зразку невдалий і проводять з попередньої базисної точки досліджуючий пошук типу I для визначення нового вдалого напрямку.
З ілюстративною метою, продовжимо пошук з .
Пошук по зразку
,
,
.
Досліджуючий пошук типу II
, , (успішно),
, , (успішно),
Але, оскільки < , то, не дивлячись на те, що досліджуючий пошук типу II виявився успішним, пошук по зразку вважається невдалим, і з точки починається досліджуючий пошук типу I.
Коли досягається ситуація, при якій ні досліджуючий пошук типу I, ні пошук по зразку (разом з досліджуючим пошуком типу II ) не є успішними в довільному координатному напрямку, вважається що вони обоє невдалі і приріст зменшують наступним чином
,
де - число послідовних невдалих спроб в досліджуючих пошуках при заданій величині кроку, починаючи від останнього успішного досліджуючого пошуку.
(В цьому прикладі при і ).
Симплексний метод Нелдера-Міда чи пошук по деформуючому багатограннику
У процесі пошуку по симплексу здійснюється робота з регулярними симплексами. Регулярні багатогранники в просторі називаються симплексами. Для регулярний симплекс являє собою рівносторонній трикутник; при - тетраедр і т.д.
Координати вершин регулярного симплекса в -мірному просторі можуть бути визначені наступною матрицею D, у якій стовпці являють собою вершини симплекса, пронумеровані від 1 до ( ), а рядки – координати вершин, . Матриця має розмірність :
,
де:
; ;
– відстань між вершинами.
Рис. 4.
У найпростішому виді симплексний алгоритм полягає в наступному. Будується регулярний симплекс. З вершини, у якій максимальна (т.1) проводиться пряма, що проектує, через центр ваги симплекса. Потім т.1 виключається і будується новий відбитий симплекс зі старих точок, що залишилися, і однієї нової, розташованої на прямій, що проектує, на належній відстані від центра ваги.
Продовження цієї процедури, у якій щораз виключається вершина, де цільова функція максимальна, а також використання правил зменшення розміру симплекса і запобігання циклічного руху в околиці екстремуму дозволяє досить ефективно визначати мінімум для "гарних" функцій. Але для функцій типу “яру” такий пошук неефективний.
У симплексному алгоритмі Нелдера і Міда мінімізація функцій змінних здійснюється з використанням деформуючого багатогранника.
Рис. 5. Розтяг і стиск симплекса.
а – нормальне відображення , ; б – розтяг , ; в – стиск , , ; г – стиск , .
Будемо розглядати -у ітерацію алгоритму. Нехай , , є -ою вершиною в на -м етапі пошуку, , і нехай значення цільової функції у вершині . Відзначимо вершини з мінімальним і максимальним значеннями. І позначимо їхній у такий спосіб:
и.
Багатогранник у складається з вершин . Позначимо через - центр ваги вершин без точки з максимальним значенням функції. Координати цього центра обчислюються по формулі:
, . (1)
Початковий багатогранник звичайно вибирається у виді регулярного симплекса (з вершиною в початку координат). Можна початок координат помістити в центр ваги. Процедура відшукання вершини у , у якій має краще значення, складається з наступних операцій: 1) відображення; 2) розтягання; 3) стиску; 4) редукції.
1. Відображення. Відображення – проектування точки через центр ваги у відповідності з наступним співвідношенням:
, (2)
де - коефіцієнт відображення.
Обчислюємо значення функції в знайденій точці . Якщо значення функції в даній точці , то переходимо до четвертого пункту алгоритму – операції редукції.
Якщо , то виконуємо операцію розтягання.
2. Розтягання. Ця операція полягає в наступному. Якщо (менше мінімального значення на -м етапі), то вектор розтягується відповідно до співвідношення
, (3)
де - коефіцієнт розтягання.
У протилежному випадку, якщо , то виконується операція стиску.
Якщо , то заміняється на і процедура продовжується з операції 1) при . У противному випадку заміняється на і переходимо до операції відображення 1).
3. Стиск. Якщо для , то вектор стискується відповідно до формули
,
де - коефіцієнт стиску. Після цього, точка заміняється на , і переходимо до операції відображення 1) на кроці.
4. Редукція. Якщо , то усі вектори , де зменшуються в два рази з відліком від точки по формулі
,
і переходимо до операції відображення (на початок ітераційної процедури – Крок 1. Відображення).
Як критерій зупинки можуть бути узяті ті ж критерії, що й в інших алгоритмах. Можна також використовувати критерій зупинки наступного виду:
.
Вибір коефіцієнтів звичайно здійснюється емпірично. Після того, як багатогранник відповідним чином промасштабований, його розміри повинні підтримуватися незмінними, поки зміни в топології задачі не зажадають багатогранника іншої форми. Найчастіше вибирають , , .
Початок
Обчислити початкові значення
і початкового симплекса
Визначити
Відображення: обчислити
Обчислити
для
Розтяг: обчислити Замінити на
Обчислити Стиск: обчислити
Обчислити
Замінити
на
Замінити
на
Замінити
на Редукція: замінити
всі на
Кінець
Рис.6. Інформаційна блок-схема пошуку методом Нелдера-Міда.
Мінімізація функції двох змінних методом Нелдера-Міда
Приклад. Знайти мінімум функції
.
(Функція має мінімум в точці ).
Візьмемо наступні три початкові точки
, і . Початкові точки можна, звичайно, вибирати стандартно, як описано в методичних вказівках.
На нульовому етапі пошуку обчислимо значення функції в початкових точках , і . Після цього відображаємо точку через центр ваги точок і за формулою
тобто (позначимо цю точку ). Тоді нова відображена точка рахується за формулою
,
тобто , .
. Оскільки , то ми переходимо до операції розтягу
,
або
,
тобто , .
.
Оскільки , ми заміняємо на і покладаємо на наступному етапі пошуку.
Нарешті, оскільки , де - задана точність, то починаємо етап пошуку . Наприклад, для досягнення заданої точності необхідно виконати 32 ітерації.
Для ілюстрації, розглянемо, як здійснюються обчислення при операції стиску. (Ця операція здійснюється у випадку, коли було б більше за .
Операція стиску
,
або
,
тобто , ,
і . Отже, в даній ситуації операція стиску не є успішною.
На завершення, на рис. 7 показано геометричне розміщення точок в процесі знаходження оптимальної точки на початковій ітерації.
Рис. 7. Розміщення точок пошуку мінімуму функції на початковій ітерації.
3. КОНТРОЛЬНІ ЗАПИТАННЯ
3.1. Вкажіть на основні переваги симплекс-методу.
3.2. Якими недоліками володіє симплекс-метод.
3.3. Вкажіть на відмінності симплексів методу Нелдера-Міда від стандартних симплексів.
3.4. Вкажіть два типи пошуку в алгоритмі Хука і Джівса.
4. ЛАБОРАТОРНЕ ЗАВДАННЯ
4.1. Набрати, скомпілювати та запустити програму, задану викладачем.
4.2. Пояснити дії, які виконує програма.
4.3. Перевірити достовірність одержаного результату.
5. ЗМІСТ ЗВІТУ
5.1. Титульний лист.
5.2. Мета роботи, теоретичні відомості.
5.3. Лабораторне завдання.
5.4. Програма і результат її роботи.
5.5. Висновок.
6. ЛІТЕРАТУРА
1. Д. Химмельблау. Прикладное нелинейное программирование. Пер. с англ. М.: Мир, 1975. – 536 с.
2. Г. Реклейтис, А. Рейвиндран, К. Рэгсдел. Оптимизация в технике: В 2-х кн. Кн. 1. Пер. с англ. – М.: Мир, 1986. – 352 с.
3. Г. Реклейтис, А. Рейвиндран, К. Рэгсдел. Оптимизация в технике: В 2-х кн. Кн. 2. Пер. с англ. – М.: Мир, 1986. – 320 с.
17.07.2020 15:07-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора