|
|
Целевая функция может быть вычислена в каждой из вершин симплекса; из вершины, где целевая функция максимальна (точка 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)
где 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<b<1 представляет собой коэффициент сжатия. Затем заменяем на и возвращаемся к операции
1 для продолжения поиска на (k+1)-м шаге.
4.
Редукция. Если , все векторы уменьшаются в 2 раза с отсчётом от в соответствии с формулой
(5)
Затем возвращаемся к операции 1 для продолжения поиска на (k+1)-м
шаге.
Критерий окончания поиска, использованный Нелдером и Мидом, состоял в проверке условия
(6)
где e – произвольное малое число, а – значение целевой функции в центре тяжести .
На схеме 1 приведена блок-схема поиска методом деформируемого многогранника, а на рисунке 3 показана последовательность поиска для функции Розенброка, начиная их x(0)=[-1,2 1,0]T. Деформируемый многогранник в противоположность жёсткому симплексу адаптируется к топографии целевой функции, вытягиваясь вдоль длинных наклонных плоскостей, изменяя направление в изогнутых впадинах и сжимаясь в окрестности минимума.
Пуск
Вычислить начальные значения
xi(0), i = 1, 2, …, n+1, и f(x(0))
начального симплекса
Вычислить xh и xl и c
Отражение: вычислить
xn+3 = xn+2 + a(xn+2 - xn)
Вычислить
f(xn+3)
|
неравенство
f(xn+3) < f(xh) ?
Страницы: 1, 2 |
|
При использовании материалов активная ссылка на источник обязательна.