Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Контакти
 


Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция






Модифікації процедури Хука-Дживса

Метод Хука-Дживса характеризується нескладною стратегією пошуку, відносною простотою обчислення і невисоким рівнем вимог до об'єму пам'яті, який виявляється нижчим, ніж при використанні методу пошуку за симплексом.

Завдяки цьому алгоритм Хука-Дживса знаходить широке застосування на практиці.

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

Відомий цілий ряд підходів до удосконалення методу Хука-Дживса. Відома модифікація процедури Хука-Дживса шляхом введення додаткових правил збільшення і зменшення приросту змінних, а також правило зменшення кроку за зразком, який застосовується в тих випадках, коли звичайний крок виявляється невдалим.

Експерименти дозволили допрацювати іншу фазу реалізації алгоритму, яку називають використанням зразка.

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

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

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

 

2.2.1 Написати програму, що реалiзує метод пошуку Хука-Дживса.

2.2.2 За допомогою розробленої програми знайти мiнiмум функцiї (табл. 1.1).

2.2.3 Навести приклади ситуацій, коли застосування методу Хука-Дживса є прийнятним та неприйнятним.

2.2.4 Порiвняти методи Нелдера-Мiда та Хука-Дживса за точнiстю знаходження оптимиму, кiлькiстю iтерацiй та часом роботи.

 

2.3 Зміст звіту

 

2.3.1 Сформульована мета роботи.

2.3.2 Алгоритм та програма, що реалізує метод Хука-Дживса.

2.3.3 Результати роботи програми.

2.3.4 Аналіз отриманих результатів і висновки.

 

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

 

 

2.4.1 Опишіть метод пошуку Хука-Дживса.

2.4.2 Яка мета дослідного пошуку в процедурі Хука-Дживса?

2.4.3 В чому полягає пошук за зразком в процедурі Хука-Дживса?

2.4.4 Які існують модифікації процедури Хука-Дживса?


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

Мета роботи - вивчити метод спряжених напрямків Пауелла.

 

 

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

Найбільш ефективним з алгоритмів прямого пошуку є метод, розроблений Пауеллом. При роботі цього алгоритму інформація, отримана на попередніх ітераціях, використовується для побудови векторів напряму пошуку, а також для усунення зациклення послідовності координатних пошуків.

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

Завдання з квадратичними цільовими функціями займають важливе місце в теорії оптимізації з двох причин:

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

2. В околі точки оптимуму будь-яку нелінійну функцію можна апроксимувати квадратичною функцією, оскільки лінійний член розкладання Тейлора звертається в нуль. Отже, робота алгоритму при вирішенні завдань з квадратичними функціями дозволяє отримати певні уявлення про збіжність алгоритму у разі, коли мінімізується функція загального вигляду.

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

Процедура перетворення квадратичної функції

 

q(х) = a+bTх+1/2хТCх (3.1)

 

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

 

Q(х) = хTCх (3.2)

 

шляхом перетворення

 

х = TZ (3.3)

 

приводиться до вигляду

 

Q(х)=ZTTTCTz=ZTDZ, (3.4)

 

де D — діагональна матриця, тобто елементи D відмінні від нуля тільки при i=j.

Нехай tj — j-й стовпець матриці Т. Тоді перетворення дозволяє записати кожен вектор х у вигляді лінійної комбінації стовпців tj:

 

х = TZ = t1z1 + t2z2 + ... + tNzN (3.5).

 

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

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

 

Проілюструємо вищевикладене прикладом.

Перетворення до вигляду суми квадрата.

 

Розглянемо функцію:

f(x)=4х12+3х22-4х1х21

і перетворення: х1=z1+0.5*z2 ; x2=z2

Перетворена квадратична функція набирає такого вигляду:

f(z)=4z12+2z22+z1+0.5z2

Це перетворення не є єдиним, зокрема перетворення

       
   


х= 1 0 z

2/3 1

 

також приводить матрицю квадратичної форми до діагонального вигляду.

Задаючи початкову точку х0=[0,0]т і два стовпці матриці перетворення t1=[1,0]Т, t2=[0.5,1]Т можна знайти точку оптимуму в результаті проведення двох послідовних пошуків в напрямах t1, t2. Пошук у напряму t1 по формулі:

х(1)=х(0)+λ*t1=[0,0]Т+ λ*[1,0]Т

дозволяє отримати λ=1/8 і точку х(1) =[-1/8, 0]Т.

Далі х(2) = х(1)+λ*t2= [-1/8, 0]Т+ λ*[0.5,1]Т=[-1/8, 0]Т-1/8*[0.5,1]Т=

=[-3/16, -1/8]Т.

 

З розглянутого прикладу виходить, що якщо система векторів tj, j=1,…,N або система зв'язаних напрямів побудована, то точку оптимуму квадратичної функції можна знайти в результаті реалізації N одновимірних пошуків, які проводяться уздовж кожного з N напрямів tj. Таким чином, невирішеними залишаються лише питання, пов'язані з побудовою системи векторів tj. Якщо матриця С відома, то матрицю перетворення Т можна знайти за допомогою методу Гауса-Жордана.

Метод Гауса-Жордана дозволяє представити матрицю С у вигляді перетворення

 

С=РТDР (3.6),

 

-1)ТС(Р-1)=D, Т=Р-1 (3.7).

 

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

Проте, в цьому випадку можна побудувати систему зв'язаних напрямів на основі властивості квадратичних функцій.

 




Переглядів: 543

<== попередня сторінка | наступна сторінка ==>
Алгоритм методу пошуку Хука-Дживса | Приклад мінімізації на основі властивості паралельного підпростору.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.007 сек.