Державний комітет Російської Федерації з вищої освіти

Новосибірський державний технічний університет

Кафедра АСУ

Реферат з дисципліни

ДОСЛІДЖЕННЯ ОПЕРАЦІЙна тему

МЕТОД деформується Многогранники

Студент Борзов Андрій Миколайович
Група АС-513
Викладач Ренін Сергій Васильович

Новосибірськ 1997

Пошук по деформується багатогранники

Вперше метод деформованого багатогранника був запропонований Нелдером і
МЗС. Вони запропонували метод пошуку, що виявився досить ефективним і легкоякі здійснюються на ЕОМ. Щоб можна було оцінити стратегію Нелдера і Міда,коротко опишемо симплексних пошук Спендлі, Хекста і Хімсворта, розробленийу зв'язку зі статистичними плануванням експерименту. Згадаймо, щорегулярні багатогранники в En є симплекс. Наприклад, як видно змалюнка 1, для випадку двох змінних регулярний симплекс представляєсобою рівносторонній трикутник (три крапки); у випадку трьох зміннихрегулярний симплекс являє собою тетраедр (чотири точки) і т.д.

Малюнок 1.

Регулярні симплекси для випадку двох (а) і трьох (б ) незалежних змінних.

(позначає найбільше значення f (x). Стрілка вказує напрямок

якнайшвидшого поліпшення.

При пошуку мінімуму цільової функції f (x) пробні вектори x можуть бутивибрані в точках En, що знаходяться у вершинах симплекс, як булоспочатку запропоновано Спендлі, Хекстом і Хімсвортом. З аналітичноїгеометрії відомо, що координати вершин регулярного симплексвизначаються наступною матрицею D, в якій стовпці представляють собоювершини, пронумеровані від 1 до (n +1), а рядки - координати, i приймаєзначення від 1 до n:

- матриця n X (n +1),

де

,

,

t - відстань між двома вершинами. Наприклад, для n = 2 і t = 1трикутник, наведений на малюнку 1, має наступні координати:

| Вершина | x1, i | x2, i |
| 1 | 0 | 0 |
| 2 | 0.965 | 0.259 |
| 3 | 0.259 | 0.965 |

Цільова функція може бути обчислена в кожній з вершин симплекс; звершини, де цільова функція максимальна (точка A на малюнку 1), проводитьсяпроектуються пряма через центр ваги симплекс. Потім точка Aвиключається і будується новий симплекс, званий відбитим, з рештиколишніх пікселів і однієї нової точки B, розташованої на проектує прямоїна належному відстані від центру тяжіння. Продовження цієї процедури,якій кожен раз викреслюється вершина, де цільова функція максимальна,а також використання правил зменшення розміру симплекс і запобіганняциклічного руху в околиці екстремуму дозволяють здійснити пошук,що не використовує похідні і в якому величина кроку на будь-якому етапі kфіксована, а напрямок пошуку можна змінювати. На малюнку 2 наведеніпослідовні симплекси, побудовані в двовимірному просторі з
«Доброю» цільовою функцією.

Малюнок 2.

Послідовність регулярних симплекс, отриманих при мінімізації f (x).

-- ---- проекція

Певні практичні труднощі, що зустрічаються при використаннірегулярних симплекс, а саме відсутність прискорення пошуку і труднощі припроведення пошуку на викривлених «ярах» і «хребтах», привели донеобхідності деяких поліпшень методів. Далі буде викладено метод
Нелдера і Міда, в якому симплекс може змінювати свою форму і такимчином вже не буде залишатися симплекс. Саме тому тутвикористано більше відповідна назва «деформується багатогранник».

У методі Нелдера і Міда мінімізується функція n незалежнихзмінних з використанням n +1 вершин деформується багатогранника в En.
Кожна вершина може бути ідентифікована вектором x. Вершина (точка) в
En, в якій значення f (x) максимально, проектується через центр ваги
(Центроїд) залишилися вершин. Поліпшені (більш низькі) значення цільовоїфункції знаходяться послідовною заміною точки з максимальним значеннямf (x) на більш «хороші точки», поки не буде знайдений мінімум f (x).

Більш докладно цей алгоритм може бути описаний таким чином.

Нехай, є i - й вершиною (точкою) в En на k-му етапі пошуку,k = 0, 1, ..., і нехай значення цільової функції у x (k) i одно f (x (k) i). Крімтого, відзначимо ті вектори x багатогранника, які дають максимальну імінімальне значення f (x).

Визначимо

 Оскільки багатогранник в En складається з (n +1) вершин x1, ..., xn +1, нехайxn 2 буде центром тяжіння всіх вершин, крім xh.

Тоді координати цього центру визначаються формулою

(1)де індекс j позначає координатне напрямок.

Початковий багатогранник зазвичай вибирається у вигляді регулярного симплекс
(але це не обов'язково) з точкою 1 як початку координат; можнапочаток координат помістити в центр ваги. Процедура відшукання вершини в
En, в якій f (x) має краще значення, складається з наступних операцій:

1. Відображення - проектування x (k) h через центр ваги у відповідності із співвідношенням

(2)

де (> 0 є коефіцієнтом відбиття; - центр ваги, що обчислює по формулі (1) ; - вершина, в якій функція f (x) приймає найбільше з n +1 значень на k-му етапі.

2. Розтягування. Ця операція полягає в наступному: якщо, то вектор
розтягується в Відповідно до співвідношенням

(3)

де (> 1 являє собою коефіцієнт розтягування. Якщо, то замінюється на і процедура триває знову з операції 1 при k = k +1. В іншому випадку замінюється на і також здійснюється перехід до операції 1 при k = k +1.

3. Стиснення. Якщо для всіх i (h, то вектор стискається у відповідності з формулою

( 4)

де 0