Курсовая работа: Исследование методов оптимизации

.

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

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

.

Если a=1 , то получим зеркальное отражение. В одномерном случае процедура отражения, обеспечивающая получение точки , симметричной точке относительно иллюстрируется рис. 2.2

Рисунок 2.2 - Построение точки

Сравним теперь между собой значения

Возможны следующие варианты

а). В этом случае выполняется растяжение симплекса и отыскивается точка

Параметр обычно принимается равным 1,5.

Полученная точка заменяет , если . В противном случае для замены используется точка .

б) . При этом реализуется отражение. Точка заменяет .

в) . В этом случае осуществляется сжатие и отыскивается точка

Параметр обычно принимается равным 0,5. Точка заменяет .

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

Критерий останова вычислительной процедуры имеет вид :

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

Модификация метода

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

.

Найдем теперь координаты точки такой, что центр тяжести симплекса с длиной ребра, равной t , использующего вершину в качестве начальной, совпадал бы с . Матрица координат указанного симплекса имеет вид

(2.1)

Координаты центра тяжести этого симплекса образуют вектор