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

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

Например, как видно из рисунка 1, для случая двух переменных регулярный симплекс представляет собой равносторонний треугольник (три точки); в случае трёх переменных регулярный симплекс представляет собой тетраэдр (четыре точки) и т.д.

A
A
B
а
б
B
Рисунок SEQ Рисунок * ARABIC 1 . Регулярные симплексы для случая двух (а) и трёх (б) независимых переменных. обозначает наибольшее значение f(x) . Стрелка указывает направление наискорейшего улучшения. При поиске минимума целевой функции f(x) пробные векторы x могут быть выбраны в точках E n , находящихся в вершинах симплекса, как было первоначально предложено Спендли, Хекстом и Химсвортом. Из аналитической геометрии известно, что координаты вершин регулярного симплекса определяются следующей матрицей D , в которой столбцы представляют собой вершины, пронумерованные от 1 до ( n+1 ), а строчки – координаты, i принимает значения от 1 до n : – матрица n X (n+1) , где t – расстояние между двумя вершинами.

Например, для n=2 и t=1 треугольник, приведённый на рисунке 1, имеет следующие координаты:

Вершина x 1,i x 2,i
1 0 0
2 0.965 0.259
3 0.259 0.965
Целевая функция может быть вычислена в каждой из вершин симплекса; из вершины, где целевая функция максимальна (точка A на рисунке 1), проводится проектирующая прямая через центр тяжести симплекса. Затем точка A исключается и строится новый симплекс, называемый отражённым, из оставшихся прежних точек и одной новой точки B, расположенной на проектирующей прямой на надлежащем расстоянии от центра тяжести.

Продолжение этой процедуры, в которой каждый раз вычёркивается вершина, где целевая функция максимальна, а также использование правил уменьшения размера симплекса и предотвращения циклического движения в окрестности экстремума позволяют осуществить поиск, не использующий производные и в котором величина шага на любом этапе k фиксирована, а направление поиска можно изменять. На рисунке 2 приведены последовательные симплексы, построенные в двумерном пространстве с «хорошей» целевой функцией. Рисунок SEQ Рисунок * ARABIC 2 . Последовательность регулярных симплексов, полученных при минимизации f(x). ----- проекция Определённые практические трудности, встречающиеся при использовании регулярных симплексов, а именно отсутствие ускорения поиска и трудности при проведении поиска на искривлённых «оврагах» и «хребтах», привели к необходимости некоторых улучшений методов. Далее будет изложен метод Нелдера и Мида, в котором симплекс может изменять свою форму и таким образом уже не будет оставаться симплексом.

Именно поэтому здесь использовано более подходящее название «деформируемый многогранник». В методе Нелдера и Мида минимизируется функция n независимых переменных с использованием n+1 вершин деформируемого многогранника в E n . Каждая вершина может быть идентифицирована вектором x . Вершина (точка) в E n , в которой значение f(x) максимально, проектируется через центр тяжести (центроид) оставшихся вершин.

Улучшенные (более низкие) значения целевой функции находятся последовательной заменой точки с максимальным значением f(x) на более «хорошие точки», пока не будет найден минимум f(x) . Более подробно этот алгоритм может быть описан следующим образом. Пусть iй вершиной (точкой) в E n на k -м этапе поиска, k=0, 1, …, и пусть значение целевой функции в x (k) i равно f(x (k) i ) . Кроме того, отметим те векторы x многогранника, которые дают максимальное и минимальное значения f(x) . Определим Поскольку многогранник в E n состоит из (n+1) вершин x 1 , …,x n+1 , пусть x n+2 будет центром тяжести всех вершин, исключая x h . Тогда координаты этого центра определяются формулой (1) где индекс j обозначает координатное направление.

Начальный многогранник обычно выбирается в виде регулярного симплекса (но это не обязательно) с точкой 1 в качестве начала координат; можно начало координат поместить в центр тяжести.

Процедура отыскания вершины в E n , в которой 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 для продолжения поиска на (k+1)- м шаге. 4. Редукция . Если уменьшаются в 2 раза с отсчётом от в соответствии с формулой (5) Затем возвращаемся к операции 1 для продолжения поиска на (k+1)- м шаге.

Критерий окончания поиска, использованный Нелдером и Мидом, состоял в проверке условия (6) где e – произвольное малое число, а – значение целевой функции в центре тяжести На схеме 1 приведена блок-схема поиска методом деформируемого многогранника, а на рисунке 3 показана последовательность поиска для функции Розенброка, начиная их x (0) =[-1,2 1,0] T . Деформируемый многогранник в противоположность жёсткому симплексу адаптируется к топографии целевой функции, вытягиваясь вдоль длинных наклонных плоскостей, изменяя направление в изогнутых впадинах и сжимаясь в окрестности минимума. Пуск

Вычислить начальные значения x i (0) , i = 1, 2, …, n+1, и f(x (0) ) начального симплекса
Вычислить x h и x l и c
Отражение: вычислить x n+3 = x n+2 + a (x n+2 - x n )
Вычислить f(x n+3 )
Нет
Выполняется ли неравенство f(x n+3 ) f(x h ) ?
Да
Растяжение: вычислить x n+4 = x n+2 + g (x n+3 - x n+2 )
Вычислить f(x n+4 )
Выполняется ли неравенство f(x n+4 ) l ) ?
Заменить x h на x n+4
Нет
Выполняется ли неравенство f(x n+3 ) i ) для всех i ¹ h ?
Нет
Нет
Да
Нет
Заменить x h на x n+3
Нет
Схема 1. Информационная блок-схема поиска методом деформируемого многогранника.
Выполняется ли неравенство f(x n+3 ) h ) ?
Да
Да
Заменить x h на x n+3 Сжатие: вычислить x n+5 = x n+2 + b (x h - x n+2 )
Вычислить f(x n+5 )
Выполняется ли неравенство f(x n+5 ) > f(x h ) ?
Заменить
Да
x h на x n+5
Редукция: заменить все x i на x l + 1 / 2 (x i - x l )
Да
Останов Рисунок SEQ Рисунок * ARABIC 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 . С другой стороны, 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 существует вероятность того, что из-за уплощения многогранника будет иметь место преждевременное окончание процесса. При b > 0,6 может потребоваться избыточное число шагов и больше машинного времени для достижения окончательного решения.

Пример Поиск методом деформируемого многогранника. Для иллюстрации метода Нелдера и Мида рассмотрим задачу минимизации функции f(x)=4(x 1 –5) 2 +(x 2 –6) 2 , имеющей минимум в точке x * =[5 6] T . Поскольку f(x) зависит от двух переменных, в начале поиска используется многоугольник с тремя вершинами. В этом примере в качестве начального многогранника взят треугольник с вершинами x 1 (0) =[8 9] T , x 2 (0) =[10 11] T и x 3 (0) =[8 11] T , хотя можно было бы использовать любую другую конфигурацию из трёх точек. На нулевом этапе поиска, k=0 , вычисляя значения функции, получаем f(8,9)=45, f(10,11)=125 и f(8,11)=65. Затем отражаем x 2 (0) =[10 11] T через центр тяжести точек x 1 (0) и x 3 (0) [ по формуле (1) ] , который обозначим через x 4 (0) : с тем, чтобы получить x 5 (0) . , , f(6,9)=13. Поскольку f(6,9)=13 , переходим к операции растяжения: f(4,8)=8. Поскольку f(4,8)=8 заменяем x 2 (0) на x 6 (0) и полагаем x 6 (0) =x 2 (1) на следующем этапе поиска.