Дослідження роботи методів одновимірної оптимізації. Методичні вказівки до лабораторної роботи з Методи синтезу та оптимізації. Робота № 531316

Перехід до торгівельного партнера Binance

Дослідження роботи методів одновимірної оптимізації

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Комп’ютерні науки

Кафедра:

Не вказано

Інформація про роботу

Рік:

2008

Тип роботи:

Методичні вказівки до лабораторної роботи

Предмет:

Методи синтезу та оптимізації

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ Національній університет "Львівська політехніка" Дослідження роботи методів одновимірної оптимізації МЕТОДИЧНІ ВКАЗІВКИ до лабораторної роботи №1 з курсу "Методи синтезу та оптимізації" для студентів базового напряму 6.08.04 "Комп'ютерні науки" ЗАТВЕРДЖЕНО на засіданні кафедри САП Протокол № 1 від 28.08 2008 р. ЛЬВІВ 2008 Дослідження роботи методів одновимірної оптимізації. Методичні вказівки до лабораторної роботи №1 з курсу " Методи синтезу та оптимізації " для студентів базового напряму 6.08.04 "Комп'ютерні науки" /Укл. Андрійчук М. І., Теслюк В.М. - Львів: НУ "ЛП", 2008 р. Укладачі: Андрійчук Михайло Іванович, к. ф.-м. н., доц., Теслюк Василь Миколайович, к.т.н., доц. Відповідальний за випуск: Ткаченко С.П., к.т.н., доц. Рецензенти: Каркульовський В. І., к.т.н., доц., Стех Ю.В, к.т.н., доц. 1. МЕТА РОБОТИ Вивчити основні алгоритми розв’язку одновимірних оптимізаційних задач. 2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ 2.1. Методи виключення інтервалів Методи пошуку, які дозволяють визначити оптиум функції однієї змінної шляхом зменшення інтервалу пошуку, носять назву методів виключення інтервалів. Усі методи одновимірної оптимізації базуються на припущенні, що цільова функція, в допустимій області принаймі володіє властивістю унімодальності, оскільки для унімодальної функції F(х) порівняння значень (F(х1) та F(х2))в двох різних точках (x1 і x2) інтервалу пошуку дозволяє визначити в якому із заданих підінтервалів точка оптиуму відсутня. 2.1.1. Правило виключення інтервалів. Нехай F(х) унімодальна функція на відрізку [a, b], а її мінімум досягається в точці х*. Розглянемо точки x1 і x2, які розташовані а<x1<x2<b. Якщо F(x1)>F(x2), то точка мінімуму F(х) не лежить в інтервалі (a, x1), тобто х*Є (x1, b). Якщо F(x1)<F(x2), то точка мінімуму F(х) не лежить в інтервалі (x2, b), тобто х*Є (a, x2). Це правило дозволяє реалізувати процедуру пошуку шляхом послідовного виключення частин початкового обмеженого інтервалу. Пошук завершується тоді, коли підінтервал, що залишився меншає до досить малих розмірів. Основна перевага пошукових методів – вони базуються на обчисленні тільки значень функції і, отже, не вимагають виконання умови диференційованості і запису в аналітичному вигляді. Остання властивість особливо цінна при імітаційному моделюванні. Процес застосування методів пошуку на основі виключення інтервалів включає два етапи: етап встановлення границь інтервалу; етап зменшення інтервалу. 2.1. 2. Метод поділу інтервалу пошуку наполовину. Метод поділу інтервалу пошуку наполовину дозволяє зменшити інтервал пошуку наполовину при кожній ітерації. Знайти F(х) на відрізку [a, b]. Крок 1. xm=(а+b)/2; L=b-a; обчислити F(xm). Крок 2. x1=а+L/4; x2=b-L/4; обчислити F(x1) і F(x2). Крок 3. Якщо F(x1)<F(xm), то виключити (xm, b], тобто b=xm, xm=x1. Перейти до кроку 5. Якщо F(x1)> F(xm), то перейти до кроку 4. Крок 4. Якщо F(x2)<F(xm), то виключити [a, xm), тобто а=xm, xm=x2. Перейти до кроку 5. Якщо F(x2)> F(xm), то виключити [a, x1)][ і (x2, b], тобто а=x1, b=x2. Перейти до кроку 5. Крок 5. L=b-a. ЯкщоL|е то закінчити пошук. В іншому випадку повернутися до кроку 2. Як слідує з алгоритму, з кожних трьох значень цільової функції F(х), обчислених в інтервалі пошуку, надалі використовується тільки дві, а третя не дає додаткової інформації і надалі не використовується. У методі золотого січення цільова функція обчислюється в точках інтервалу, розташованих таким чином, щоб кожне обчислене значення цільової функції давало б нову корисну інформацію. 2.1. 3. Метод золотого січення. Основна суть методу. Інтервал пошуку ділиться на дві рівні частини так, щоб відношення довжини великого відрізка до довжини всього інтервалу було таке, що дорівнює відношенню =. Враховуючи, що z1+z2=z, будемо мати F(x) z z12=z z2 = (z1+z2)z2 = z1z2 + z22; z1 z2 z1z2 + z22 - z12 = 0, звідки =. а x b x Знайти F(х) на відрізку [a, b]. Крок 1. Обчислюємо коефіцієнт дроблення відрізка [a, b] k=(- 1)/2. Крок 2. x1=а+(1-k)(b-a), обчислити F(x1). Крок 3. x2=а+k(b-a), обчислити F(x2). Крок 4. Якщоx2-x1| <  де - задана точність, то xm = (x1+x2)/2, обчислити F(xm) і закінчити пошук. Якщоx2-x1| >   то перейти до кроку 5. Крок 5. Якщо F(x1)>F(x2), то а=x1, x1=x2 і F(x1)=F(x2). Перейти до кроку 3, потім до кроку 4. Якщо F(x1) < F(x2), то b=x2, x2=x1 і F(x1)=F(x2). Перейти до кроку 2 і 4. Таким чином, застосування методів виключення інтервалів накладає єдине обмеження на цільову функцію, яка досліджується - унімодальність. Отже, розглянуті методи можна використати для аналізу як безперервних, так і розривних та дискретних функцій. Логічна структура пошуку базується на простому порівнянні значень функції в двох пробних точках. 2.2. Методи поліноміальної апроксимації 2.2.1. Основний зміст методу. Згідно теореми Вейєрштрасса про апроксимацію, неперервну функцію в деякому інтервалі можна апроксимувати поліномом досить високого порядку. Отже, якщо функція унімодальна і знайдений поліном, який досить точно її апроксимує, то координати точки оптиуму функції можна оцінити шляхом обчислення координати точки оптиуму полінома. Найпростіший випадок базується на тому факті, що функція, яка приймає мінімальне значення у внутрішній точці інтервалу, має бути принаймні квадратична. Якщо цільова функція F(х) в точках x1, x2, x3 приймає відповідні значення F1, F2, F3, то можна визначити коефіцієнти а0, a1, a2 таким чином, що значення квадратичної функції q(х) = ao + a1(x-x1) + a2(x-x1)(x-x2) співпадуть зі значенням F(х) в трьох вказаних точках. (див. Табл.1). Обчислення значень. Таблиця 1 W1 = W(x1) = q(x1) = ao ao = W1 W2 = W(x2) = q(x2) = W1 + a1(x2 - x1) a1 =(W2 - W1)/(x2 - x1) W3 =q(x3) = W1 + [(W2 - W1) (x3 - x1)]/ /(x2 - x1) + a2(x3 - x1) (x3 - 2) a2 = =0 = - 2.2.2. Метод Пауела. Якщо відомі значення функції f(х) в трьох різних точках  відповідно f, f, f, , то функція f(х) може бути апроксимована квадратичною функцією f(х)=Ax2+Bx+C, де: А, В і C визначаються з рівнянь A2+B+C=f A2+B+C=f A2+B+C=f Після перетворень цих рівнянь отримуємо A=fff B=fff C=fff де: . Зрозуміло, що (x) буде мати мінімум в точці х=-B/2A, якщо А>0. Отже можна апроксимувати точку мінімуму функції f(х) значенням Цей метод може безпосередньо застосовуватися до функцій однієї змінної. Він може бути дуже корисний для виконання лінійного пошуку. В цих процедурах потрібно знайти мінімум функції f(х) в точках прямої x0+D , де x0- задана точка, а D визначає заданий напрям. Значення функції f(x0+D) на цій прямій є значеннями функції однієї змінної :  = f(x0+D). Ідеї і результати, викладені вище, перетворюються у обчислювальні процедури, які описані далі. Передбачимо, що задані унімодальна функція однієї змінної f(х), початкова апроксимація місця знаходження мінімуму і довжина кроку D, є величиною того ж порядку, що і відстань від точки А до точки реального мінімуму х* (умова, яку не завжди просто задовольнити). Обчислювальна процедура має наступні кроки: Крок 1. x2 = x1 + D х. Крок 2. Обчислити F(x1) і F(x2). Крок 3. Якщо F(x1) > F(x2), то x3 = x1 + 2 D х. Якщо F(x1)< F(x2), то x3 = x1 - D х. F(x1) > F(x2), Крок 4. Обчислити F(x3) і знайти Fmin = min{ F(x1), F(x2), F(x3)}, Xmin = xi, відповідна Fmin. Крок 5. По x1, x2, x3 обчислити х*, використовуючи формулу для оцінки з допомогою квадратичної апроксимації. Крок 6. Перевірка закінчення. Якщо |Wmin - W(х*)| < W, то закінчити пошук. У іншому випадку перехід до кроку 7. Якщо |Xmin - х*| < х, то закінчити пошук. У іншому випадку перехід до кроку 7. Крок 7. Вибрати Xmin або х* і дві точки по обидві сторони від неї. Визначити в природному порядку нові значення x1, x2, x3 перейти до кроку 4. Даний метод часто називають методом Пауела. Відмітимо, що якщо величина D задана дуже малою, то  а також f, f, f будуть дуже близько один до одного і значення  може стати взагалі неточним. Щоб подолати цю трудність, для знаходження точки мінімума використовуватимемо іншу формулу: 2.3. Методи з використанням похідних Всі розглянуті в попередніх розділах методи пошуку базуються на припущеннях про унімодальність і в ряді випадків про безперервність цільової функції, яка досліджується. Доцільно передбачити, що якщо в доповнення до умови неперервності ввести вимогу диференційованості функції, то ефективність пошукових процедур можна істотно підвищити. Нагадаємо, що необхідне умова існування локального мінімуму функції в деякій точці z, згідно з яким перша похідна функції в точці має бути рівною нулю, т. е. f'(z}==df/dx|x=z=0. Якщо функція f(х) містить члени, які включають х в третій і більш високих степенях, то безпосереднє отримання аналітичного рішення рівняння f'(х)=0 може виявитися досить скрутним. У таких випадках використовуються наближені методи послідовного пошуку стаціонарної точки функції f. Передусім опишемо класичну пошукову схему, орієнтовану на знаходження кореня нелінійного рівняння. Ця схема була розроблена Ньютоном і пізніше уточнена Рафсоном. 2.3.1. Метод Ньютона-Рафсона. В рамках схеми Ньютона-Рафсона передбачається, що функція f двічі диференційована. Робота алгоритму починається в точці Xi, яка представляє початкове наближення (чи початкову оцінку) координати стаціонарної точки, або кореня рівняння f'(х)=0. Потім будується лінійна апроксимація функції f'(х) в точці Xi, і точка, в якій апроксимуюча лінійна функція рівна нулю, приймається як наступне наближення. Рис.1 Метод Ньютона-Рафсона ( збіжність) Якщо точка прийнята як поточне наближення до стаціонарної точки, то лінійна функція, апроксимуюча функцію f'(х) в точці , записується у вигляді . Прирівнявши праву частину рівняння до нуля, отримаємо наступне наближення: . Рис.1 ілюструє основні кроки реалізації методу Ньютона. На жаль, в залежності від вибору початкової точки і вигляду функції алгоритм може як збігатися до істинної стаціонарної точки, так і розбігтися, що відображено на рис. 2. Якщо початкова точка розташована правіше за х0, то ті xi, що отримуються внаслідок послідовних наближень точки віддаляються від стаціонарної точки z. Рис.2 Метод Ньютона-Рафсона (відсутність збіжності) 2.3.2. Приклад застосування методу Ньютона-Рафсона Розглянемо наступну задачу: мінімізувати Для того щоб визначити стаціонарну точку функції f(х), скористаємося методом Ньютона-Рафсона, поклавши : , . Ітерація 1. , , . Ітерація 2. , , , Ітерації продовжуються доти, поки не буде виконуватися нерівність , де зазделегідь встановлена величина допустимого відхилення. 3. КОНТРОЛЬНІ ЗАПИТАННЯ 4. ЛАБОРАТОРНЕ ЗАВДАННЯ 4.1. Набрати, скомпілювати та запустити програму задану викладачем . 4.2. Пояснити дії, які виконує програма. 4.3. Перевірити достовірність одержаного результату. 5. ЗМІСТ ЗВІТУ 5.1. Титульний лист. 5.2. Мета роботи, теоретичні відомості. 5.3. Лабораторне завдання. 5.4. Програма. 5.5. Висновок. 6. ЛІТЕРАТУРА Реклейтис Г., Рейвиндрон А., Рзгсдел К. Оптимизация в технике: В 2-х кн. Кн. 1. Пер. с англ. - М.: Мир, 1986. - 349 с. Реклейтис Г., Рейвиндрон А., Рзгсдел К. Оптимизация в технике: В 2-х кн. Кн.2. Пер. с англ. - М.: Мир, 1986. - 320 с. Шуп Т. Решение инженерных задач на ЭВМ. Практическое руководство. Пер. с англ. – М.: Мир, 1982. – 238 с. О. Коссак, О. Тумашова, О. Коссак. Методи наближених обчислень. Навчальний посібник. НУ «Львівська політехніка», 2003. - 168 с.

Методичні вказівки до лабораторної роботи Методи синтезу та оптимізації

horuktaras

17.07.2020 15:07-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись