Метод деформованого багатогранника

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

НОВОСИБІРСЬКИЙ ДЕРЖАВНИЙ ТЕХНІЧНИЙ УНИВЕРСИТЕТ.

[pic].

Кафедра АСУ Реферат по дисциплине.

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

МЕТОД ДЕФОРМИРУЕМОГО МНОГОГРАННИКА Студент Борзов Андрію Миколайовичу Група АС-513 Викладач Ренин Сергій Васильевич.

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

Пошук по деформируемому многограннику.

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

[pic].

Малюнок 1.

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

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

якнайшвидшого улучшения.

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

[pic] - матриця n X (n+1),.

где.

[pic],.

[pic],.

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 наведено послідовні симплексы, зведені у двовимірному просторі з «хорошою» цільової функцией.

[pic].

Малюнок 2.

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

——- проекция.

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

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

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

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

Определим.

[pic] [pic].

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

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

[pic] (1) де індекс j позначає координатне направление.

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

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

[pic] (2).

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

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

[pic] (3).

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

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

[pic] (4).

де 0.