ОПТИМИЗАЦИЯ ДЕФОРМИРУЕМЫХ СИСТЕМ : Метод деформируемого многогранника

Monday, November 4, 2013

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

Алгоритм

Пусть требуется найти безусловный минимум функции n переменных . Предполагается, что серьёзных ограничений на область определения функции нет, то есть функция определена во всех встречающихся точках.

Параметрами метода являются:

коэффициент отражения $α > 0$ , обычно выбирается равным $1$ .

коэффициент сжатия $β > 0$ , обычно выбирается равным $0,5$ .

коэффициент растяжения $γ > 0$ , обычно выбирается равным $2$ .

Подготовка. Вначале выбирается $n$ $+ 1$ точка , образующие симплекс n-мерного пространства. В этих точках вычисляются значения функции: .

Дальнейший план действий:

1. Сортировка. Из вершин симплекса выбираем три точки: $x h$ с наибольшим (из выбранных) значением функции $f h$ , $x g$ со следующим по величине значением $f g$ и $x l$ с наименьшим значением функции $f l$ . Целью дальнейших манипуляций будет уменьшение по крайней мере $f h$ .

2. Найдём центр тяжести всех точек, за исключением $x h$ : . Вычислять $f c$ $=$ $f$ $($ $x c$ $)$ не обязательно.

3. Отражение. Отразим точку $x h$ относительно $x c$ с коэффициентом $α$ (при $α = 1$ это будет центральная симметрия, в общем случае — гомотетия), получим точку $x r$ и вычислим в ней функцию: $f r$ $=$ $f$ $($ $x r$ $)$ . Координаты новой точки вычисляются по формуле:

x_r $= (1 + α)$ $x c$ $- α$ $x h$

4. Далее смотрим, насколько нам удалось уменьшить функцию, ищем место $f r$ в ряду $f h$ $,$ $f g$ $,$ $f l$ :

4а Если $f r$ $<$ $f l$ , то направление выбрано удачное и можно попробовать увеличить шаг — производим растяжение. Новая точка $x e$ $= (1 - γ)$ $x c$ $+ γ$ $x r$ и значение функции $f e$ $=$ $f$ $($ $x e$ $)$ .

Если $f e$ $<$ $f l$ , то можно расширить симплекс до этой точки: заменяем точку $x h$ на $x e$ и заканчиваем итерацию (на шаг 8).

Если $f e$ $>$ $f l$ , то переместились слишком далеко: в набор берём $x r$ (опять вместо $x h$ ) и заканчиваем итерацию (на шаг 8).

4b Если $f l$ $<$ $f r$ $<$ $f g$ , то выбор точки уже неплохой (новая лучше двух прежних). Заменяем точку $x h$ на $x r$ и переходим на шаг 8.

4с Если $f h$ $>$ $f r$ $>$ $f g$ , то меняем обозначения $x r$ $,$ $x h$ (и соответствующие значения функции) местами и идём на шаг 5.

4d Если $f r$ $>$ $f h$ , то просто идём на следующий шаг 5.

В результате (возможно, после переобозначения) $f r$ $>$ $f h$ $>$ $f g$ $>$ $f l$ .

5. Сжатие. Строим точку $x s$ $= β$ $x h$ $+ (1 - β)$ $x c$ и вычисляем в ней значение $f s$ .

6 Если $f s$ $<$ $f h$ , то заменяем точку $x h$ на $x s$ и идём на шаг 8.

7 Если $f s$ $>$ $f h$ , то первоначальные точки оказались самыми маленькими. Делаем глобальное сжатие симплекса — гомотетию к точке с наименьшим значением $x$ $0$ :

для всех требуемых точек $x i$ .

8 Последний шаг — проверка сходимости. Может выполняться по-разному, например, оценкой дисперсии набора точек. Суть проверки заключается в том, чтобы проверить взаимную близость полученных вершин симплекса, что предполагает и близость их к искомому минимуму. Если требуемая точность ещё не достигнута, можно продолжить итерации с шага 1.

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)