Основы теории оптимизации (стр. 31 )

Cхемa 1. Блок-схема поиска методом деформируемого многогранника

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

Коэффициент отражения a используется для проектирования вершины с наибольшим значением f(x) через центр тяжести деформируемого многогранника. Коэффициент g вводится для растяжения вектора поиска в случае, если отражение даёт вершину со значением f(x), меньшим, чем наименьшее значение f(x), полученное до отражения. Коэффициент сжатия b используется для уменьшения вектора поиска, если операция отражения не привела к вершине со значением f(x), меньшим, чем второе по величине (после наибольшего) значение f(x), полученное до отражения. Таким образом, с помощью операций растяжений или сжатия размеры и форма деформируемого многогранника масштабируются так, чтобы они удовлетворяли топологии решаемой задачи.

Естественно возникает вопрос, какие значения параметров a, b и g должны быть выбраны. После того как деформируемый многогранник подходящим образом промасштабирован, его размеры должны поддерживаться неизменными, пока изменения в топологии задачи не потребуют применения многогранника другой формы. Это возможно реализовать только при a=1. Кроме того, Нелдер и Мид показали, что при решении задачи с a=1 требуется меньшее количество вычислений функции, чем при a<1. С другой стороны, a не должно быть много больше единицы, поскольку

1)  деформируемый многогранник легче адаптируется к топологии задачи при меньших значениях a, особенно когда необходимо изменять направление поиска, столкнувшись с изогнутой впадиной, и

2)  в области локального минимума размеры многогранника должны уменьшаться и большое a в этих условиях замедлит сходимость.

Таким образом, значение a=1 выбирается как компромисс.

Чтобы выяснить, какое влияние на процедуру поиска имеет выбор b и g, Нелдер и Мид (а также Павиани) провели решение нескольких тестовых задач, используя большое число различных комбинаций значений b и g. В качестве удовлетворительных значений этих параметров при оптимизации без ограничений Нелдер и Мид рекомендовали a=1, b=0,5 и g=2. Размеры и ориентация исходного многогранника в некоторой степени влияли на время решения, а значения a, b и g оказывали значительно большее влияние. Павиани отмечает, что нельзя чётко решить вопрос относительно выбора b и g и что влияние выбора b на эффективность поиска несколько более заметно, чем влияние g. Павиани рекомендует следующие диапазоны значений для этих параметров:

0,4 £ b £ 0,6,

2,8 £ g £ 3,0.

При 0<b<0,4 существует вероятность того, что из-за уплощения многогранника будет иметь место преждевременное окончание процесса. При b>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) [по формуле (64)], который обозначим через x4(0):

,

с тем, чтобы получить x5(0).

,

,

f(6,9)=13.

Поскольку f(6,9)=13<f(8,9)=45, переходим к операции растяжения:

,

,

f(4,8)=8.

Поскольку f(4,8)=8<f(8,9)=45, заменяем x2(0) на x6(0) и полагаем x6(0)=x2(1) на следующем этапе поиска.

Наконец, поскольку

,

начинаем этап поиска k=1. На рисунке 4 приведена траектория поиска на начальных этапах. На рисунке 5 изображена полная траектория поиска до его окончания. Для уменьшения f(x) до значения потребовалось 32 этапа.

Рис.4. Метод Нелдера и Мида при отсутствии ограничений.

Рис. 5.
Траектория поиска с помощью алгоритма Нелдера и Мида.

С помощью операции растяжения и сжатия размеры и форма деформируемого многогранника адаптируются к топографии целевой функции. В результате многогранник вытягивается вдоль длинных наклонных поверхностей, изменяет направление в изогнутых впадинах, сжимается в окрестности минимума, что определяет эффективность рассмотренного метода.

Алгоритм метода симплекса

Напомним, что под симплексом понимается n-мерный выпуклый многогранник n-мерного пространства, имеющий n+1 вершину. Для n=2 это треугольник, а при n=3 это тетраэдр.

  Идея метода состоит в сравнении значений функции в n+1 вершинах симплекса и перемещении симплекса в направлении лучшей точки. В рассматриваемом методе симплекс перемещается с помощью операций отражения. Далее принято следующее: х0(k), х1(k), … , хn(k) – вершины симплекса, где k - номер итерации.

Алгоритм

Шаг 1. Построение начального симплекса. Задаются начальная точка х0(0) и длина ребра симплекса l. Формируются остальные вершины симплекса:

xi(0) = x0(0) + l*ei (i=1,2,…,n), где ei – единичные векторы.

Шаг 2. Определение направления улучшения решения. Для этого на k-й итерации вычисляются значения целевой функции в каждой точке симплекса. Пусть для всех i:

f(xmin(k))£f(xi(k))£f(xmax(k)),

где min, max, i – номера соответствующих вершин симплекса. Определим центр тяжести всех точек, исключая точку xmax(k),

Ck=(Sxi(k))/n .

Тогда направление улучшения решения определяется вектором Ck-xmax(k).

Шаг 3. Построение отраженной точки. Замена вершины xmax(k) с максимальным значением целевой функции на новую точку с помощью операции отражения, результатом которой является новая точка:

uk=ck+(ck-xmax(k))=2ck-xmax(k)

Шаг 4. Построение нового симплекса. Вычисляем f(uk). При этом возможен один из двух случаев:

а) f(uk)<f(xmax(k);

б) f(uk)³f(xmax(k).

а) Вершина xmax заменяется на uk, чем определяется набор вершин k+1-й итерации и k-я итерация заканчивается.

б) В результате отражения получается новая точка uk, значение функции в которой еще хуже, чем в точке xmax, то есть отражать симплекс некуда. Поэтому в этом случае производится пропорциональное уменьшение симплекса (например, в 2 раза) в сторону вершины xmin(k):

xi(k+1)=xi=(xi(k)+xmin(k))/2, где i=0,1,…,n.

На этом k-я итерация заканчивается.

Шаг 5. Проверка сходимости. Если

то поиск минимума заканчивается и полагается

В противном случае k=k+1 и происходит переход к шагу 2.

Алгоритм методa деформируемого симплекса

(метод Нелдера – Мида)

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

В рассматриваемом методе симплекс перемещается с помощью трех основных операций над симплексом: отражение, растяжение и сжатие.

Алгоритм

Шаг 1. Построение начального симплекса. Задаются начальная точка х0(0) и длина ребра l. Формируются остальные вершины симплекса:  xi(0)=x0(0)+lei (i=1,2,…,n), где ei – единичные векторы.

Шаг 2. Определение направления улучшения решения. Для этого на каждой итерации вычисляются значения целевой функции в каждой вершине симплекса. Пусть для всех i