Впервые метод деформируемого многогранника был предложен Нелдером и Мидом. Они предложили метод поиска, оказавшийся весьма эффективным и легко осуществляемым на ЭВМ. Чтобы можно было оценить стратегию Нелдера и Мида, кратко опишем симплексный поиск Спендли, Хекста и Химсворта, разработанный в связи со статистическим планированием эксперимента. Вспомним, что регулярные многогранники в En
являются симплексами. Например, как видно из рисунка 1, для случая двух переменных регулярный симплекс представляет собой равносторонний треугольник (три точки); в случае трёх переменных регулярный симплекс представляет собой тетраэдр (четыре точки) и т.д.
Рисунок
1.
Регулярные симплексы для случая двух (а) и трёх (б) независимых переменных.
- обозначает наибольшее значение f(x). Стрелка указывает направление
наискорейшего улучшения.
При поиске минимума целевой функции f(x) пробные векторы x могут быть выбраны в точках En
, находящихся в вершинах симплекса, как было первоначально предложено Спендли, Хекстом и Химсвортом. Из аналитической геометрии известно, что координаты вершин регулярного симплекса определяются следующей матрицей D, в которой столбцы представляют собой вершины, пронумерованные от 1 до (n+1), а строчки – координаты, i принимает значения от 1 до n:
– матрица 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 приведены последовательные симплексы, построенные в двумерном пространстве с «хорошей» целевой функцией.
Рисунок
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
) ?
Растяжение: вычислить
xn+4
= xn+2
+ g(xn+3
- xn+2
)
Вычислить f(xn+4
)
Выполняется ли
неравенство
f(xn+4
) < f(xl
) ?
Заменить
xh
на xn+4
Выполняется ли неравенство f(xn+3
) < f(xi
)
для всех i ¹ h ?
Заменить
xh
на xn+3
Схема 1.
Информационная блок-схема поиска методом деформируемого многогранника.
|
Выполняется ли
неравенство
f(xn+3
) < f(xh
) ?
Заменить
xh
на xn+3
Сжатие: вычислить
xn+5
= xn+2
+ b(xh
- xn+2
)
Вычислить f(xn+5
)
Выполняется ли
неравенство
f(xn+5
) > f(xh
) ?
Заменить
xh
на xn+5
Редукция: заменить
все xi
на xl
+ 1
/2
(xi
- xl
)
Останов
Рисунок
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)
[по формуле (1)], который обозначим через 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 приведена траектория поиска на начальных этапах, а в таблице 2 приведены координаты вершин и значения f(x) для четырёх дополнительных этапов. На рисунке 5 изображена полная траектория поиска до его окончания. Для уменьшения f(x) до значения
потребовалось 32 этапа.
Рисунок
4.
Метод Нелдера и Мида при отсутствии ограничений.
Рисунок
5.
Траектория поиска с помощью алгоритма Нелдера и Мида.
Поиск по деформируемому многограннику_______________________
Пример____________________________________________________
Содержание_______________________________________________
Список рисунков____________________________________________
Список литературы________________________________________
Рисунок 1. Регулярные симплексы для случая двух (а) и трёх (б) независимых переменных._________________________________________________
Рисунок 2. Последовательность регулярных симплексов, полученных при минимизации f(x)._____________________________________________
Рисунок 3. Поиск минимума функции Розенброка методом деформируемого многогранника.______________________________________________
Рисунок 4. Метод Нелдера и Мида при отсутствии ограничений._____
Рисунок 5. Траектория поиска с помощью алгоритма Нелдера и Мида.
· Химмельблау Д. Прикладное нелинейное программирование. –М.,1975.