Методичні вказівки. До лабораторних робіт з дисципліни

БАГАТОВИМІРНІ МЕТОДИ ОПТИМІЗАЦІЇ

до лабораторних робіт з дисципліни

«Математичні методи оптимізації та дослідження операцій»

для студентів

напряму підготовки 6.050103 “Програмна інженерія”

всіх форм навчання

Багатовимірні методи оптимізації. Методичні вказівки до лабораторних робіт з дисципліни «Математичні методи оптимізації та дослідження операцій» для студентів напряму підготовки 6.050103 “Програмна інженерія” всіх форм навчання / Укладачі: В.І. Дубровін, Л.Ю. Дейнега. – Запоріжжя: ЗНТУ, 2009. – 40 с.

Укладачі: В.І. Дубровін, Л. Ю. Дейнега

Рецензент: А.В. Притула

Відповідальний за випуск: В.І. Дубровін

Затверджено

на засіданні кафедри “Програмних засобів”

Протокол №8 від 25.03.2009 р.

ЗМІСТ

ВСТУП. 4

ЛАБОРАТОРНА РОБОТА № 1 Методи прямого пошуку в задачах багатовимірної безумовної оптимізації. Модифікована процедура пошуку по симплексу Недлера-Міда 5

1.1 Короткі теоретичні відомості 5

1.2 Порядок виконання роботи. 13

1.3 Зміст звіту. 15

1.4 Контрольні питання. 15

ЛАБОРАТОРНА РОБОТА № 2. МЕТОД ПОШУКУ ХУКА-ДЖИВСА. МОДИФІКАЦІЇ ПРОЦЕДУРИ ХУКА-ДЖИВСА. 17

2.1 Короткі теоретичні відомості 17

2.2 Порядок виконання роботи. 21

2.3 Зміст звіту. 21

2.4 Контрольні питання. 21

ЛАБОРАТОРНА РОБОТА № 3 Метод спряжених напрямків Пауелла 22

3.1 Короткі теоретичні відомості 22

3.2 Порядок виконання роботи. 26

3.3 Зміст звіту. 26

3.4 Контрольні питання. 27

ЛАБОРАТОРНА РОБОТА № 4 Градієнтні методи багатовимірної оптимізації 28

4.1 Короткі теоретичні відомості 28

4.2 Порядок виконання роботи. 39

4.3 Зміст звіту. 39

4.4 Контрольні питання. 39

ЛІТЕРАТУРА. 40

ВСТУП

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

Ефективність методів оптимізації, що дозволяють здійснити вибір найкращого варіанта без перевірки всіх можливих варіантів, тісно пов’язана з використанням тріади „модель-алгоритм-програма”.

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

Оскільки вимоги до задач оптимізації являються загальними та носять абстрактний характер, область використання методів оптимізації може бути доволі широкою. У зв’язку з цим в провідних університетах світу введені учбові дисципліни “Engineering Optimization” та “Operation Research”, які викладаються на рівні бакалаврата, а в деяких випадках – на рівні магістратури. Така тенденція спостерігається і в вищих навчальних закладах України.

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

ЛАБОРАТОРНА РОБОТА № 1 Методи прямого пошуку в задачах багатовимірної безумовної оптимізації. Модифікована процедура пошуку по симплексу Недлера-Міда

Мета роботи - вивчити метод безумовної багатовимiрної оптимiзацiї Нелдера-Мiда.

1.1 Короткі теоретичні відомості

Метод пошуку по симплексу (s² - метод)

При вирішенні задач з двома змінними можна скористатися квадратним зразком. Найкраща (F_min) з 5 досліджуваних точок вибирається як наступна базова точка, навколо якої будується наступний зразок. Якщо жодна з кутових точок не має переваг перед базовою, розміри зразка слід зменшити, після чого продовжити пошук. Цей тип еволюційної оптимізації був використаний для аналізу функціонування промислових підприємств, коли ефект варіювання значень змінних, що описують виробничі процеси, вимірюється з помилкою. У задачі великої розмірності обчислення значень цільової функції проводиться у всіх вершинах, а також в центрі тяжіння гіперкуба, тобто в точках так званого кубічного зразка. Гіперкубом називається куб в N-вимірному евклідовому просторі, тобто безліч X=(X1, X2., XN)Є N, a_i ≤ x_i≤ b_i, i=1, N, де а і b - задані числа.

Якщо кількість змінних (розмірність простору, в якому ведеться пошук) рівна N, то пошук за кубічним зразком вимагає 2N+1 обчислень значення функції для даного зразка. При збільшенні розмірності задачі необхідна кількість обчислень значення цільової функції зростає надзвичайно швидко. Таким чином, не дивлячись на логічну простоту пошуку за кубічним зразком, виникає необхідність використання ефективніших методів прямого пошуку для вирішення задач оптимізації, що виникають на практиці.

Одна із стратегій пошуку покладена в основу методу пошуку по симплексу. Процедура симплексного пошуку базується на тому, що експериментальним зразком, який містить найменшу кількість точок, є регулярний симплекс. Регулярний симплекс в N-мірному просторі- багатогранник, утворений N+1 рівновіддаленими одна від одної точками (вершинами). В разі двох змінних, симплексом є рівносторонній трикутник, в тривимірному просторі, симплекс є тетраедром. У алгоритмі симплексного методу використовується властивість симплексу, згідно якій новий симплекс можна побудувати на будь-якій грані початкового симплексу шляхом перенесення обраної вершини на належну відстань вздовж прямої, проведеної через центр тяжіння решти вершин початкового симплексу. Отримана таким чином точка є вершиною нового симплексу, а обрану при побудові початкового симплексу вершину виключають. Потрібне одне обчислення значення цільової функції (при переході до нового симплексу).

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

Правило 1. «Накриття» точки мінімуму.

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

Правило 2. Циклічний рух.

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

Запропоновано обчислювати М за формулою:

М=1.65*N+0.05*N² (1.1)

де N - розмірність задачі;

М - округляється до найближчого цілого.

Для застосування даного правила потрібно встановити величину коефіцієнта редукції.

Правило 3. Критерій закінчення пошуку.

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

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

2. Розрахунку координат віддзеркаленої точки.

При заданій початковій точці Х(0) і масштабному множнику α координати решти N вершин симплексу в N-мірному просторі обчислюються за формулою(1.2)

x_j⁽⁰⁾+ δ ₁, якщо i¹ j,

x⁽ⁱ⁾= (1.2)

x_j⁽⁰⁾+ δ ₂, якщо i=j

для i, j=1, 2, …, N,

де i - номер вершини;

j - номер координати.

Прирости δ ₁ і δ ₂, які залежать тільки від N і вибраного множника α, обчислюються за наступними формулами (1.3) і (1.4).

(1.3)

(1.4)

Значення масштабного множника α вибирається виходячи з характеристик вирішуваного завдання.

При α =1 ребра регулярного симплексу мають одиничну довжину. Центр тяжіння решти N точок розташований в точці х_с:

(1.5)

Всі точки прямої, яка проходить через х^(j) і х_с, задаються формулою:

x_c=x^(j)+λ *(x_c-x^(j)) (1.6)

При λ =1 отримуємо вихідну точку х^(j), тоді як значення λ =1 відповідає центру тяжіння х_с. Для того, щоб побудований симплекс мав властивість регулярності, віддзеркалення має бути симетричним. Отже, нова вершина отримується при λ =2.

x^(j) _нова=2*х_с-х^(j) _{попередня}

Приклад. Обчислення відповідно до методу пошуку по симплексу.

Мінімізувати f(x)=(1-x₁)²+(2-x₂)².

Розв’язок:

1. Для побудови початкового симплексу потрібно задати початкову точку і масштабувальний множник.

Хай х⁽⁰⁾=[0; 0]^T, α =2, тоді

;

.

2.Використовуючи ці два параметри, обчислимо координати двох основних вершин симплексу:

x⁽¹⁾=[0+0.5176; 0+1.9318]T=[0.5176; 1.9318]T;

x⁽²⁾=[0+1.9318; 0+0.5176]T=[1.9318; 0.5176]T.

3.Даним точкам х⁽¹⁾ і х⁽²⁾ відповідають значення цільової функції:

f(x⁽¹⁾) =0.2374;

f(x⁽²⁾) =3.0658.

4.Оскільки f(x⁽⁰⁾)=5, необхідно відобразити точку х⁽⁰⁾ через центр тяжіння решти двох вершин.

(1.7)

5.Використовуючи формулу (1.6), отримуємо:

x⁽³⁾=x⁽¹⁾+x⁽²⁾-х⁽⁰⁾

х⁽³⁾=[0.5176+1.9318-0; 1.9318+0.5176-0]^T=[2.4494; 2.4494]^T

У отриманій точці f(x⁽³⁾)=2, 3027.

Тобто, спостерігається зменшення цільової функції. Новий симплекс утворений точками х⁽¹⁾, х⁽²⁾, х⁽³⁾. Відповідно до алгоритму, слід відобразити точку х⁽²⁾, якій відповідає найбільше значення цільової функції, через центр тяжіння точок х⁽¹⁾ і х⁽³⁾. Ітерації продовжуються, поки не буде потрібно застосування сформульованих вище правив 1, 2, 3.

Викладений вище алгоритм S²-методу має декілька очевидних переваг:

1. Розрахунки і логічна структура методу відрізняються порівняльною простотою, і, отже, відповідна програма виявляється відносно короткою.

2. Рівень вимог до обсягу пам'яті невисокий. Масив має розмірність (N+1, N+2).

3. Використовується порівняно невелике число заздалегідь встановлених параметрів (α, коефіцієнт редукції і параметр закінчення пошуку).

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

Алгоритм має ряд недоліків:

1. Не виключено виникнення складностей, пов'язаних з масштабуванням, оскільки всі координати вершин симплексу залежать від одного і того ж масштабованого множника α. Щоб обійти складності такого роду в практичних завданнях, слід промасштабувати всі змінні для того, щоб їх значення були порівнянними за величиною.

(1.8)

2. Алгоритм працює дуже повільно, оскільки отримана на попередніх ітераціях інформація не використовується для прискорення пошуку.

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

Таким чином, якщо α з якої-небудь причини зменшується, наприклад, якщо зустрічає зону з вузькою западиною або хребтом, то пошук повинен продовжуватися із зменшеною величиною кроку.

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