Вершина
|
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))
начального симплекса
Отражение: вычислить
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(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.