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

Критерий окончания поиска, использованный Нелдером и Мидом, состоял в проверке условия

(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 не должно быть много больше единицы, поскольку деформируемый многогранник легче адаптируется к топологии задачи при меньших значениях a, особенно когда необходимо изменять направление поиска, столкнувшись с изогнутой впадиной, и
в области локального минимума размеры многогранника должны уменьшаться и большое 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.
При 00,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

(8,9)=45,>
,
,
f(4,8)=8.
Поскольку f(4,8)=8

2
(0) на x
6
(0) и полагаем x
6
(0)=x
2
(1) на следующем этапе поиска.
(8,9)=45,>
Наконец, поскольку
,
начинаем этап поиска k=1. На рисунке 4 приведена траектория поиска на начальных этапах, а в таблице 2 приведены координаты вершин и значения f(x) для четырёх дополнительных этапов. На рисунке 5 изображена полная траектория поиска до его окончания. Для уменьшения f(x) до значения потребовалось 32 этапа.

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

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

Содержание

Поиск по деформируемому многограннику 3
Пример 10
Содержание 14
Список рисунков 14
Список литературы 14

Список рисунков

Рисунок 1.Регулярные симплексы для случая двух (а) и трёх (б) независимых переменных. 3
Рисунок 2.Последовательность регулярных симплексов, полученных при минимизации f(x).—— проекция 5
Рисунок 3.Поиск минимума функции Розенброка методом деформируемого многогранника, начиная с точки x(0)=[-1,2 1,0]T (числа указывают номер шага). 9
Рисунок 4.Метод Нелдера и Мида при отсутствии ограничений. 12
Рисунок 5.Траектория поиска с помощью алгоритма Нелдера и Мида. 13

Список литературы
Химмельблау Д. Прикладное нелинейное программирование. –М.,1975.

14

Рисунок 3.Информационная блок-схема поиска методом деформируемого многогранника.