Разработаны эффективные, высоко робастные методы и алгоритмы оптимизации, на основе которых создан комплекс программ, позволяющий решать практические задачи оптимизации
Search This Blog
Monday, November 4, 2013
Метод деформируемого многогранника
Алгоритм
Пусть требуется найти безусловный минимум функции n
переменных .
Предполагается, что серьёзных ограничений на область определения функции нет,
то есть функция определена во всех встречающихся точках.
Параметрами метода являются:
коэффициент отражения α > 0, обычно выбирается равным 1.
коэффициент сжатия β > 0, обычно выбирается равным 0,5.
коэффициент растяжения γ > 0, обычно выбирается равным 2.
Подготовка. Вначале выбирается n + 1 точка , образующие симплекс n-мерного
пространства. В этих точках вычисляются значения функции: .
Дальнейший план действий:
1. Сортировка. Из вершин симплекса
выбираем три точки: xh с наибольшим (из
выбранных) значением функции fh, xg со следующим по величине
значением fg и xl с наименьшим значением
функции fl. Целью дальнейших
манипуляций будет уменьшение по крайней мере fh.
2. Найдём центр
тяжести всех
точек, за исключением xh: .
Вычислять fc = f(xc) не обязательно.
3. Отражение. Отразим точку xh относительно xc с коэффициентом α (при α = 1 это
будет центральная
симметрия, в общем случае — гомотетия),
получим точку xr и вычислим в ней функцию: fr = f(xr). Координаты новой точки вычисляются по формуле:
xr = (1 +
α)xc − αxh
4. Далее смотрим, насколько нам удалось уменьшить
функцию, ищем место fr в ряду fh,fg,fl:
4а Если fr < fl, то направление
выбрано удачное и можно попробовать увеличить шаг — производим растяжение.
Новая точка xe = (1 −
γ)xc + γxr и значение функции fe = f(xe).
Если fe < fl, то можно
расширить симплекс до этой точки: заменяем точку xh на xe и заканчиваем итерацию (на
шаг 8).
Если fe > fl, то переместились
слишком далеко: в набор берём xr (опять вместо xh) и заканчиваем
итерацию (на шаг 8).
4b Если fl < fr < fg, то выбор точки
уже неплохой (новая лучше двух прежних). Заменяем точку xh на xr и переходим на шаг 8.
4с Если fh > fr > fg, то меняем
обозначения xr,xh (и соответствующие
значения функции) местами и идём на шаг 5.
4d Если fr > fh, то просто идём
на следующий шаг 5.
В результате (возможно, после переобозначения) fr > fh > fg > fl.
5. Сжатие. Строим точку xs = βxh + (1 −
β)xc и вычисляем в ней
значение fs.
6 Если fs < fh, то заменяем
точку xh на xs и идём на шаг 8.
7 Если fs > fh, то
первоначальные точки оказались самыми маленькими. Делаем глобальное
сжатие симплекса — гомотетию к
точке с наименьшим значением x0:
для всех требуемых точек xi.
8 Последний шаг — проверка сходимости. Может
выполняться по-разному, например, оценкой дисперсии набора
точек. Суть проверки заключается в том, чтобы проверить взаимную близость
полученных вершин симплекса, что предполагает и близость их к искомому
минимуму. Если требуемая точность ещё не достигнута, можно продолжить итерации
с шага 1.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment