Новини освіти і науки:

G+

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

Модифікована система пошука по симплексу Нелдера – Міда

Хоча формула для визначення регулярного симплексу виявляється доволі зручною при побудові початкового зразка, проте вірних підстав для збереження властивостей регулярності симплексу в процесі пошуку немає. Отже, при віддзеркаленні симплексу існує можливість, як його розтягування, так і стискування. З цієї причини процедуру Нелдера- Міда інколи називають методом пошуку по деформованому багатограннику. При розрахунках по методу Нелдера- Міда використовуються вершини симплексу x₍_h₎, яким відповідає найбільше значення цільової функції f_(h), вершина x_(g), якій відповідає наступне по величині значення цільової функції f_(g) і x₍_l₎, якій відповідає найбільше значення цільової функції f_(е).

Віддзеркалення вершини симплексу здійснюється за прямою:

x=х_(h)+x*(x_С-x_(h)) (1.9)

x=x₍_h₎+(1+θ)*(x_С-x_(h)) (1.10)

При θ=1 має місце нормальне віддзеркалення симплексу, оскільки точка x_нове розташовується на відстані (x_С-x₍_h₎)) від точки x_с, при -1<=θ <=+1 спостерігається стисле віддзеркалення або стиск симплексу. Вибір θ =>1забеспечує розтягнуте віддзеркалення або розтягування симплексу.

Різні види відображення представлені на рис. 1.1

x_h

а)

x_h

б)

x_h

в)

x_h

д)

Рисунок 1.1 - Розтягування та зжимання симплексу:

а) нормальне відображення (θ=α=1), f₍_l₎<f₍_g_.);

б) розтягування (θ=α>1), f(x_нов)<f₍_l₎;

в) стиск (θ=β<0), f(x_нов)>f₍_g₎, f(x_нов)>f₍_h₎;

д) стиск (θ=β>0), f⁽^g⁾<f(x_нов)<f⁽^h⁾

Три значення параметру θ, що використовуються при нормальному віддзеркаленні, стиску та розтягуванні, позначаються (λ,β,γ).

Реалізація методу починається з побудови початкового симплексу і визначення точок x_(h), x_(g), x_(е), x_с, після нормального віддзеркалення здійснюється перевірка значень цільової функції за критерієм закінчення пошуку в точках відображеного симплексу, якщо пошук не закінчений за допомогою тестів, обирається одна з операцій: нормальне віддзеркалення, розтягування або стиск. Ітерації продовжуються, поки зміни значень цільової функції в вершинах симплексу не стануть незначними. Як задовільні значення параметрів (λ,β,γ) Нелдер і Мід рекомендують використовувати λ =1, β=0,5, γ =2.

Метод Нелдера-Міда володіє достатньою ефективністю і високою надійністю в умовах наявності випадкових збурень або помилок при визначенні значень цільової функції.

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

1.2.1 Написати програму, що реалiзує метод пошуку Нелдера-Мiда.

1.2.2 За допомогою розробленої програми знайти мiнiмум функцiї. Функції обирати згідно варіанту з табл. 1.1.

1.2.3 Навести приклади ситуацiй, коли застосування методу Нелдера-Мiда є прийнятним та неприйнятним.

Таблиця 1.1 – Варіанти досліджуваних функцій

№ вар.	Функція	Почат. точка
	y = (1 - x₁)²+ (2 - x₂)²	x⁽⁰⁾ = [0, 0]^T
	y = (5 - 2x₁)⁸+ (6 - 3x₂)⁴	x⁽⁰⁾ = [3, 2]^T
	y = (31 - 8x₁)⁶+ (2 - 3x₂)²	x⁽⁰⁾ = [1, -1]^T
	y = 9 - 2(5x₁+2x₂) +x₁²+x₂²	x⁽⁰⁾ = [0,2, 0,1]^T
	y = (1 - x₁)²+ (2 - x₂)² - 0,01x₁x₂	x⁽⁰⁾ = [-1, 0]^T
	y = (10 - 2x₁)²+ (12 - 5x₂)⁴	x⁽⁰⁾ = [0,3, 0,5]^T
	y = (8 - x₁)²- (7 - x₂)² + 3x₂⁴	x⁽⁰⁾ = [-3, 5]^T
	y = 19 - 15x₁- 8x₂ +3x₁²+x₂²	x⁽⁰⁾ = [0, 0]^T
	y = x₁⁶ - (1 - x₁)²+ (2 - x₂)²	x⁽⁰⁾ = [10, 20]^T
	y = 2x₁²+ 4x₁x₂³ - 10x₁x₂ + x₂³	x⁽⁰⁾ = [0, 0]^T
	y = 6x₁⁴+ 8x₁x₂⁶ - 13x₁x₂ + 4x₂³	x⁽⁰⁾ = [3, 7]^T
	y = 9 - 25x₁+ x₁²- 22x₂+x₂²	x⁽⁰⁾ = [0, 1]^T
	y = 22\|x₁\|⁷+ 24x₁³x₂⁶ - x₁x₂ + x₂³	x⁽⁰⁾ = [-12, 17]^T
	y = (1 - x₁)²+ (2 - x₂)² - 3x₁x₂	x⁽⁰⁾ = [-6, 7]^T
	y = x₁²- x₁³x₂² - 9x₁x₂ + x₂³	x⁽⁰⁾ = [20, -10]^T
	y = 18 - 20x₁- 8x₂ +2x₁²+2x₂²	x⁽⁰⁾ = [0, 0]^T
№ вар.	Функція	Почат. точка
	y = (1 - x₁)²+ (2 - x₂)² - x₁-x₂	x⁽⁰⁾ = [-1, 6]^T
	y = 3 - 3,3x₁- 1,1x₂ + 3x₁²+4x₂²	x⁽⁰⁾ = [0, 0]^T
	y = (1 - x₁)²+ (2 - x₂)² - x₁^-1x₂²	x⁽⁰⁾ = [-1, 0]^T
	y = 4x₁²+ 3x₂²- 4x₁x₂ +x₁	x⁽⁰⁾ = [5, 3]^T
	y = 2x₁²x₂²- 40x₁x₂ +x₁³	x⁽⁰⁾ = [8, -7]^T
	y = 5x₁³+ 8x₂⁶- 4x₁³x₂ +5x₂	x⁽⁰⁾ = [2, 17]^T
	y = 8x₁⁶+ 33x₂⁶- 24x₁³x₂³+x₁⁹	x⁽⁰⁾ = [3, -6]^T
	y = 6x₁^-2+ 2x₂⁸- 6x₁x₂ +8x₂⁴	x⁽⁰⁾ = [-1, 2]^T

1.3 Зміст звіту

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

1.3.2 Алгоритм та програма, що реалізує метод Нелдера-Мiда.

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

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

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

1.4.1 Наведіть класифікацію методів безумовної багатовимірної оптимізації.

1.4.2 Опишіть метод пошуку за симплексом.

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

1.4.4 Охарактеризуйте ситуацію циклічного руху під час симплексного пошуку.

1.4.5 Що є критерієм закінчення симплексного пошуку?

1.4.6 Як визначаються координати вершин початкового симплексу?

1.4.7 Як визначаються координати відображеної вершини симплексу?

1.4.8 Переваги та недолiки методу пошуку за симплексом.

1.4.9 Коли треба використовувати симплексний метод?

1.4.10 Опишіть модифіковану процедуру пошуку за симплексом Нелдера-Міда.

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

Мета роботи - вивчити метод безумовної багатовимiрної оптимiзацiї Хука-Дживса.

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

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

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

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

Х^(к) – поточна базова точка;

Х^(к-1) – попередня базова точка;

Х_р^(к+1) – точка побудови в наближенні до зразка;

Х^(к+1) – наступна нова базова точка.

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

<== попередня сторінка	\|	наступна сторінка ==>
МЕТОДИЧНІ ВКАЗІВКИ	\|	Алгоритм методу пошуку Хука-Дживса

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

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