Реферат: Метод деформируемого многогранника

Государственный комитет РоссийскойФедерации

по высшему образованию

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра АСУ

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

ИССЛЕДОВАНИЕ ОПЕРАЦИЙ

на тему

МЕТОД ДЕФОРМИРУЕМОГО МНОГОГРАННИКА

Студент БорзовАндрей Николаевич

Группа АС–513

Преподаватель Ренин Сергей Васильевич

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

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

Впервыеметод деформируемого многогранника был предложен Нелдером и Мидом. Онипредложили метод поиска, оказавшийся весьма эффективным и легко осуществляемымна ЭВМ. Чтобы можно было оценить стратегию Нелдера и Мида, кратко опишемсимплексный поиск Спендли, Хекста и Химсворта, разработанный в связи состатистическим планированием эксперимента. Вспомним, что регулярныемногогранники в

Enявляются симплексами. Например, как видно из рисунка 1, для случая двухпеременных регулярный симплекс представляет собой равносторонний треугольник(три точки); в случае трёх переменных регулярный симплекс представляет собойтетраэдр (четыре точки) и т.д.

A

B

B

Рисунок SEQ Рисунок * ARABIC 1.
Регулярные симплексы для случая двух (а) и трёх (б) независимых переменных.

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

Припоиске минимума целевой функции

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

<img src="/cache/referats/1184/image005.gif" v:shapes="_x0000_i1027"> – матрица

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

Рисунок SEQ Рисунок * ARABIC 2.
Последовательность регулярных симплексов, полученных при минимизации f(x).
— проекция

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

Вметоде Нелдера и Мида минимизируется функция

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

Болееподробно этот алгоритм может быть описан следующим образом.

Пусть<img src="/cache/referats/1184/image012.gif" v:shapes="_x0000_i1031">

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

Определим

<img src="/cache/referats/1184/image020.gif" v:shapes="_x0000_i1035"> Поскольку многогранникв

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

Тогдакоординаты этого центра определяются формулой

<img src="/cache/referats/1184/image022.gif" v:shapes="_x0000_i1036"> (1)

где индекс

j обозначает координатное направление.

Начальныймногогранник обычно выбирается в виде регулярного симплекса (но это не обязательно)с точкой 1 в качестве начала координат; можно начало координат поместить вцентр тяжести. Процедура отыскания вершины в

1.

Отражение – проектирование x(k)h черезцентр тяжести в соответствии с соотношением
<img src="/cache/referats/1184/image024.gif" v:shapes="_x0000_i1037"> (2)
гдеa>0 является коэффициентом отражения; <img src="/cache/referats/1184/image026.gif" v:shapes="_x0000_i1038"> – центр тяжести, вычисляемыйпо формуле (1); <img src="/cache/referats/1184/image028.gif" v:shapes="_x0000_i1039"> – вершина, в которойфункция f(x)принимает наибольшее из n+1значений на k-мэтапе.

2.

Растяжение.Эта операция заключается в следующем: если <img src="/cache/referats/1184/image030.gif" v:shapes="_x0000_i1040"><img src="/cache/referats/1184/image032.gif" v:shapes="_x0000_i1041"> растягивается всоответствии с соотношением
<img src="/cache/referats/1184/image034.gif" v:shapes="_x0000_i1042"> (3)
где g>1 представляет собой коэффициентрастяжения. Если <img src="/cache/referats/1184/image036.gif" v:shapes="_x0000_i1043"><img src="/cache/referats/1184/image028.gif" v:shapes="_x0000_i1044"> заменяется на <img src="/cache/referats/1184/image039.gif" v:shapes="_x0000_i1045"> и процедурапродолжается снова с операции 1 при k=k+1. В противном случае <img src="/cache/referats/1184/image028.gif" v:shapes="_x0000_i1046"> заменяется на <img src="/cache/referats/1184/image041.gif" v:shapes="_x0000_i1047"> и также осуществляетсяпереход к операции 1 при k=k+1.

3.

Сжатие. Если <img src="/cache/referats/1184/image043.gif" v:shapes="_x0000_i1048"> для всех i¹h, то вектор <img src="/cache/referats/1184/image045.gif" v:shapes="_x0000_i1049"> сжимается всоответствии с формулой
<img src="/cache/referats/1184/image047.gif" v:shapes="_x0000_i1050"> (4)
где 0<b<1 представляет собой коэффициент сжатия.Затем <img src="/cache/referats/1184/image028.gif" v:shapes="_x0000_i1051"> заменяем на <img src="/cache/referats/1184/image050.gif" v:shapes="_x0000_i1052"> и возвращаемся коперации 1 для продолжения поиска на (k+1)-м шаге.

4.

Редукция.Если <img src="/cache/referats/1184/image052.gif" v:shapes="_x0000_i1053"><img src="/cache/referats/1184/image054.gif" v:shapes="_x0000_i1054"> уменьшаются в 2 раза сотсчётом от <img src="/cache/referats/1184/image056.gif" v:shapes="_x0000_i1055"> в соответствии сформулой
<img src="/cache/referats/1184/image058.gif" v:shapes="_x0000_i1056"> (5)

Затем возвращаемся к операции 1 для продолжения поиска на (k+1)-м шаге.

Критерийокончания поиска, использованный Нелдером и Мидом, состоял в проверке условия

<img src="/cache/referats/1184/image060.gif" v:shapes="_x0000_i1057"> (6)

где

e – произвольное малое число, а <img src="/cache/referats/1184/image062.gif" v:shapes="_x0000_i1058"> – значение целевойфункции в центре тяжести <img src="/cache/referats/1184/image026.gif" v:shapes="_x0000_i1059">

Насхеме 1 приведена блок-схема поиска методом деформируемого многогранника, а нарисунке 3 показана последовательность поиска для функции Розенброка, начиная их

x(0)=[-1,2 1,0]T.Деформируемый многогранник в противоположность жёсткому симплексу адаптируетсяк топографии целевой функции, вытягиваясь вдоль длинных наклонных плоскостей,изменяя направление в изогнутых впадинах и сжимаясь в окрестности минимума.

<img src="/cache/referats/1184/image064.gif" v:shapes="_x0000_s2050">Пуск

<img src="/cache/referats/1184/image066.gif" v:shapes="_x0000_s2051">Вычислить начальные значения

xi(0), i = 1, 2, …,n+1, и f(x(0))

начального симплекса

<img src="/cache/referats/1184/image068.gif" v:shapes="_x0000_s2107"><img src="/cache/referats/1184/image069.gif" v:shapes="_x0000_s2108">Вычислить xh и xlи c

Отражение: вычислить

xn+3 = xn+2 +

a(xn+2 — xn)

Вычислить

f(xn+3)

Нет

Выполняется ли

<img src="/cache/referats/1184/image074.gif" v:shapes="_x0000_s2085">неравенство

f(xn+3)

< f(xh) ?

Да

<img src="/cache/referats/1184/image076.gif" v:shapes="_x0000_s2073">Растяжение: вычислить

xn+4 = xn+2 +

g(xn+3 — xn+2)

Вычислить

f(xn+4)

<img src="/cache/referats/1184/image079.gif" v:shapes="_x0000_s2088"><img src="/cache/referats/1184/image080.gif" v:shapes="_x0000_s2075">Выполняется ли

неравенство

f(xn+4) < f(xl) ?

<img src="/cache/referats/1184/image082.gif" v:shapes="_x0000_s2090">Заменить

xh на xn+4

Нет

Выполняется ли

неравенство f(xn+3)< f(xi)

для всех

i ¹ h ?

Нет

Нет

Да