Метод деформируемого многогранника - OXFORDST.RU

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

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

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

Метод Нелдера — Мида, также известный как метод деформируемого многогранника и симплекс-метод, — метод безусловной оптимизации функции от нескольких переменных, не использующий производной (точнее — градиентов) функции, а поэтому легко применим к негладким функциям.

Суть метода заключается в последовательном перемещении и деформировании симплекса вокруг точки экстремума.

Метод находит локальный экстремум и может «застрять» в одном из них. Если всё же требуется найти глобальный экстремум, можно пробовать выбирать другой начальный симплекс. Более развитый подход к исключению локальных экстремумов предлагается в генетическом методе отжига.

Алгоритм

Пусть требуется найти безусловный минимум функции n переменных . Предполагается, что серьёзных ограничений на область определения функции нет, то есть функция определена во всех встречающихся точках.

Параметрами метода являются:

  • коэффициент отражения α > 0 , обычно выбирается равным 1 .
  • коэффициент сжатия β > 0 , обычно выбирается равным 0,5 .
  • коэффициент растяжения γ > 0 , обычно выбирается равным 2 .

Подготовка. Вначале выбирается n + 1 точка , образующие симплекс n-мерного пространства. В этих точках вычисляются значения функции: .

Дальнейший план действий:

1. Сортировка. Из вершин симплекса выбираем три точки: xh с наибольшим (из выбранных) значением функции fh , xg со следующим по величине значением fg и xl с наименьшим значением функции fl . Целью дальнейших манипуляций будет уменьшение по крайней мере fh . 2. Найдём центр тяжести всех точек, за исключением xh : . Вычислять fc = f(xc) не обязательно. 3. Отражение. Отразим точку xh относительно xc с коэффициентом α (при α = 1 это будет центральная симметрия, в общем случае — гомотетия), получим точку xr и вычислим в ней функцию: fr = f(xr) . Координаты новой точки вычисляются по формуле: xr = (1 + α)xc − αxh 4. Далее смотрим, насколько нам удалось уменьшить функцию, ищем место fr в ряду fh,fg,fl : 4а Если fr , то направление выбрано удачное и можно попробовать увеличить шаг — производим растяжение. Новая точка xe = (1 − γ)xc + γxr и значение функции fe = f(xe) .

  • Если fe , то можно расширить симплекс до этой точки: заменяем точку xh на xe и заканчиваем итерацию (на шаг 8). Если fe >fl , то переместились слишком далеко: в набор берём xr (опять вместо xh ) и заканчиваем итерацию (на шаг 8).

4b Если fl , то выбор точки уже неплохой (новая лучше двух прежних). Заменяем точку xh на xr и переходим на шаг 8. 4с Если fh >fr >fg , то меняем обозначения xr,xh (и соответствующие значения функции) местами и идём на шаг 5. 4d Если fr >fh , то просто идём на следующий шаг 5.

В результате (возможно, после переобозначения) fr > fh > fg > fl .

5. Сжатие. Строим точку xs = βxh + (1 − β)xc и вычисляем в ней значение fs . 6 Если fs , то заменяем точку xh на xs и идём на шаг 8. 7 Если fs > fh , то первоначальные точки оказались самыми маленькими. Делаем глобальное сжатие симплекса — гомотетию к точке с наименьшим значением x : для всех требуемых точек xi . 8 Последний шаг — проверка сходимости. Может выполняться по-разному, например, оценкой дисперсии набора точек. Суть проверки заключается в том, чтобы проверить взаимную близость полученных вершин симплекса, что предполагает и близость их к искомому минимуму. Если требуемая точность ещё не достигнута, можно продолжить итерации с шага 1.

См. также

Прямые методы:
(требуют только значения функции в точках приближений)
Метод Гаусса • Метод деформируемого многогранника (метод Нелдера — Мида, симплексный метод) • Метод конфигураций • Метод Розенброка • Метод сопряжённых направлений • Метод Хука — Дживса

Методы второго порядка:
(требуют значения первой и второй частных производных):
Метод Ньютона • Метод Ньютона-Рафсона

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

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

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

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

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

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

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

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

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

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

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

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

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

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

,

,

t – расстояние между двумя вершинами. Например, для n=2 и t=1 треугольник, приведённый на рисунке 1, имеет следующие координаты:

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

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

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

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

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

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

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

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

(1)

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

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

1. Отражение – проектирование x (k) h через центр тяжести в соответствии с соотношением
(2)
где a>0 является коэффициентом отражения; – центр тяжести, вычисляемый по формуле (1); – вершина, в которой функция f(x) принимает наибольшее из n+1 значений на k-м этапе.

2. Растяжение . Эта операция заключается в следующем: если , то вектор растягивается в соответствии с соотношением
(3)
где g>1 представляет собой коэффициент растяжения. Если , то заменяется на и процедура продолжается снова с операции 1 при k=k+1. В противном случае заменяется на и также осуществляется переход к операции 1 при k=k+1.

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

Пуск

Вычислить начальные значения

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

Вычислить xh и xl и c

неравенство

Метод Нелдера-Мида (метод деформируемого многогранника)

Чтобы можно было оценить метод Нелдера -Мида, кратко рассмотрим поиск по регулярному многограннику, предложенный Спендли, Хекстом и Химсвортом.

Регулярным многогранником (симплексом) в n-мерном пространстве называется множество из (n+1)-ой равноудалённой точки. На плоскости симплексом является равносторонний треугольник, в пространстве — правильный тетраэдр.

Из аналитической геометрии известно, что координаты вершин регулярного симплекса определяются следующей матрицей D размерности :

где t — расстояние между двумя вершинами. Столбцы этой матрицы являются координатами вершин симплекса.

При оптимизации этим методом целевая функция вычисляется в каждой вершине регулярного симплекса. Из вершины, где целевая функция максимальна, проводится проектирующая прямая через центр тяжести симплекса, затем вершина с максимальным значением функции отбрасывается и строится новый (отражённый) симплекс из оставшихся прежних точек и одной новой точки, расположенной на проектирующей прямой на надлежащем расстоянии от центра тяжести. Продолжение этой процедуры, в которой каждый раз отбрасывается точка с максимальным значением целевой функции, а также использование правил уменьшения размера симплекса и предотвращения циклического движения в окрестности экстремума позволяют осуществить поиск, в котором величина шага на любом этапе фиксирована, а направление поиска можно менять (производные не используются).

Последовательные симплексы, построенные в двумерном пространстве для минимизации «хорошей» целевой функцией, приведены на рис. 8.

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

Нелдер и Мид (1964) предложили модификацию, в которой симплекс может изменять свою форму. Так как в этом случае симплекс уже не будет регулярным, метод назвали поиском по деформируемому многограннику.

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

Пусть являются i-ой вершиной на некотором k-ом этапе поиска. Пусть также

,

т.е. в точке функция принимает наибольшее значение, а в точке— наименьшее значение среди точек многогранника.

Так как многогранник состоит из точек, то центр тяжести всех вершин, кроме, обозначим через. Координатыопределяются по формуле

.

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

Алгоритм деформируемого многогранника состоит из операций отражения, растяжения, сжатия и редукции.

Отражение. Вершина проектируется через центр тяжести оставшихся вершин в соответ­ствии с соотношением

,

где α > 0 является коэффициен­том отражения (рис.9). Первой всегда выполняется операция отражения.

Растяжение. Если , то векторрастягивается в соответствии с соотношением

,

где γ>1 — коэффициент растяжения (рис 10).

Если , тозаменяется наи процедура продолжается снова с операции отражения.

В противном случае заменяется наи также осуществляется переход к операции отражения.

Сжатие. Если для всех, то векторсжимается в соответствии с формулой

,

где 0 >1, то это затрудняет адаптацию многогранника при изменениях направления поиска и замедляет сходимость в окрестности минимума. Таким образом, α =1 выбирается как компромисс. Чтобы выяснить, какое влияние на поиск имеет выбор β и γ, были проведены решения тестовых задач. Оказалось, что влияние β на эффективность поиска, более заметно, чем влияние γ.

Для практических нужд Нелдером и Мидом были рекомендованы следующие значения коэффициентов: α = 1, β = 0,5, γ = 2.

Программирование и комп-ры : Метод деформируемого многогранника

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

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

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

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

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

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

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

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

Впервые метод деформируемого многогранника был предложен Нелдером и

Мидом. Они предложили метод поиска, оказавшийся весьма эффективным и легко

осуществляемым на ЭВМ. Чтобы можно было оценить стратегию Нелдера и Мида,

кратко опишем симплексный поиск Спендли, Хекста и Химсворта, разработанный

в связи со статистическим планированием эксперимента. Вспомним, что

регулярные многогранники в En являются симплексами. Например, как видно из

рисунка 1, для случая двух переменных регулярный симплекс представляет

собой равносторонний треугольник (три точки); в случае трёх переменных

регулярный симплекс представляет собой тетраэдр (четыре точки) и т.д.

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

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

При поиске минимума целевой функции f(x) пробные векторы x могут быть

выбраны в точках En, находящихся в вершинах симплекса, как было

первоначально предложено Спендли, Хекстом и Химсвортом. Из аналитической

геометрии известно, что координаты вершин регулярного симплекса

определяются следующей матрицей D, в которой столбцы представляют собой

вершины, пронумерованные от 1 до (n+1), а строчки – координаты, i принимает

значения от 1 до n:

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

t – расстояние между двумя вершинами. Например, для n=2 и t=1

треугольник, приведённый на рисунке 1, имеет следующие координаты:

|Вершина |x1,i | x2,i |

Целевая функция может быть вычислена в каждой из вершин симплекса; из

вершины, где целевая функция максимальна (точка A на рисунке 1), проводится

проектирующая прямая через центр тяжести симплекса. Затем точка A

исключается и строится новый симплекс, называемый отражённым, из оставшихся

прежних точек и одной новой точки B, расположенной на проектирующей прямой

на надлежащем расстоянии от центра тяжести. Продолжение этой процедуры, в

которой каждый раз вычёркивается вершина, где целевая функция максимальна,

а также использование правил уменьшения размера симплекса и предотвращения

циклического движения в окрестности экстремума позволяют осуществить поиск,

не использующий производные и в котором величина шага на любом этапе k

фиксирована, а направление поиска можно изменять. На рисунке 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] Поскольку многогранник в En состоит из (n+1) вершин x1, …,xn+1, пусть

xn+2 будет центром тяжести всех вершин, исключая xh.

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

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

Начальный многогранник обычно выбирается в виде регулярного симплекса

(но это не обязательно) с точкой 1 в качестве начала координат; можно

начало координат поместить в центр тяжести. Процедура отыскания вершины в

En, в которой f(x) имеет лучшее значение, состоит из следующих операций:

1. Отражение – проектирование x(k)h через центр тяжести в соответствии с

где (>0 является коэффициентом отражения; [pic] – центр тяжести,

вычисляемый по формуле (1); [pic] – вершина, в которой функция f(x)

принимает наибольшее из n+1 значений на k-м этапе.

2. Растяжение. Эта операция заключается в следующем: если [pic], то вектор

[pic] растягивается в соответствии с соотношением

где (>1 представляет собой коэффициент растяжения. Если [pic], то [pic]

заменяется на [pic] и процедура продолжается снова с операции 1 при

k=k+1. В противном случае [pic] заменяется на [pic] и также

осуществляется переход к операции 1 при k=k+1.

3. Сжатие. Если [pic] для всех i(h, то вектор [pic] сжимается в

соответствии с формулой

все xi на xl + 1/2(xi — xl)

Поиск минимума функции Розенброка методом деформируемого многогранника,

начиная с точки x(0)=[-1,2 1,0]T (числа указывают номер шага).

Коэффициент отражения ( используется для проектирования вершины с

наибольшим значением f(x) через центр тяжести деформируемого многогранника.

Коэффициент ( вводится для растяжения вектора поиска в случае, если

отражение даёт вершину со значением f(x), меньшим, чем наименьшее значение

f(x), полученное до отражения. Коэффициент сжатия ( используется для

уменьшения вектора поиска, если операция отражения не привела к вершине со

значением f(x), меньшим, чем второе по величине (после наибольшего)

значение f(x), полученное до отражения. Таким образом, с помощью операций

растяжений или сжатия размеры и форма деформируемого многогранника

масштабируются так, чтобы они удовлетворяли топологии решаемой задачи.

Естественно возникает вопрос, какие значения параметров (, ( и (

должны быть выбраны. После того как деформируемый многогранник подходящим

образом промасштабирован, его размеры должны поддерживаться неизменными,

пока изменения в топологии задачи не потребуют применения многогранника

другой формы. Это возможно реализовать только при (=1. Кроме того, Нелдер и

Мид показали, что при решении задачи с (=1 требуется меньшее количество

вычислений функции, чем при (0,6 может

потребоваться избыточное число шагов и больше машинного времени для

достижения окончательного решения.

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

Для иллюстрации метода Нелдера и Мида рассмотрим задачу минимизации

функции f(x)=4(x1–5)2+(x2–6)2, имеющей минимум в точке x*=[5 6]T. Поскольку

f(x) зависит от двух переменных, в начале поиска используется многоугольник

с тремя вершинами. В этом примере в качестве начального многогранника взят

треугольник с вершинами x1(0)=[8 9]T, x2(0)=[10 11]T и x3(0)=[8 11]T, хотя

можно было бы использовать любую другую конфигурацию из трёх точек.

На нулевом этапе поиска, k=0, вычисляя значения функции, получаем

f(8,9)=45, f(10,11)=125 и f(8,11)=65. Затем отражаем x2(0)=[10 11]T через

центр тяжести точек x1(0) и x3(0) [по формуле (1)], который обозначим через

Метод деформируемого многогранника (метод Нелдера-Мида)

Метод Нелдера-Мида, также известный как метод деформируемого многогранника и симплекс-метод, – метод безусловной оптимизации функции от нескольких переменных, не использующий производной функции, поэтому легко применим к негладким и зашумлённым функциям.

Суть метода заключается в последовательном перемещении и деформировании симплекса вокруг точки экстремума.

Метод находит локальный экстремум и может «застрять» в одном из них. Если всё же требуется найти глобальный экстремум, можно пробовать выбирать другой начальный симплекс. Более развитый подход к исключению локальных экстремумов предлагается в алгоритмах, основанных на методе Монте-Карло, а также в эволюционных алгоритмах.

Пусть требуется найти безусловный минимум функции n переменных . Предполагается, что серьёзных ограничений на область определения функции нет, то есть функция определена во всех встречающихся точках.

Параметрами метода являются:

1) коэффициент отражения α > 0, обычно выбирается равным 1.

2) коэффициент сжатия β > 0, обычно выбирается равным 0,5.

3) коэффициент растяжения γ > 0, обычно выбирается равным 2.

Алгоритм данного метода такой:

1. «Подготовка». Вначале выбирается n + 1 точка , образующие симплекс n-мерного пространства. В этих точках вычисляются значения функции: .

2. «Сортировка». Из вершин симплекса выбираем три точки: xh с наибольшим (из выбранных) значением функции fh, xg со следующим по величине значением fg и xl с наименьшим значением функции fl. Целью дальнейших манипуляций будет уменьшение по крайней мере fh.

3. Найдём центр тяжести всех точек, за исключением xh: . Вычислять fc = f(xc) не обязательно.

4. «Отражение». Отразим точку xh относительно xc с коэффициентом α (при α = 1 это будет центральная симметрия, в общем случае — гомотетия), получим точку xr и вычислим в ней функцию: fr = f(xr). Координаты новой точки вычисляются по формуле:

5. Далее смотрим, насколько нам удалось уменьшить функцию, ищем место fr в ряду fh,fg,fl.

Если fr fl, то переместились слишком далеко: присваиваем точке xh значение xr и заканчиваем итерацию (на шаг 9).

Если fl fr > fg, то меняем местами значения xr и xh. Также нужно поменять местами значения fr и fh. После этого идём на шаг 6.

Если fr > fh, то просто идём на следующий шаг 6.

В результате (возможно, после переобозначения) fr > fh > fg > fl.

6. «Сжатие». Строим точку xs = βxh + (1 − β)xc и вычисляем в ней значение fs = f(xs).

7. Если fs fh, то первоначальные точки оказались самыми удачными. Делаем «глобальное сжатие» симплекса — гомотетию к точке с наименьшим значением xl:

(3)

9. Последний шаг — проверка сходимости. Может выполняться по-разному, например, оценкой дисперсии набора точек. Суть проверки заключается в том, чтобы проверить взаимную близость полученных вершин симплекса, что предполагает и близость их к искомому минимуму. Если требуемая точность ещё не достигнута, можно продолжить итерации с шага 2.

Понравилась статья? Поделиться с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: