- ZDUPES (7:77/21.67) -------------------------------- ZDUPES (RU.ALGORITHMS) -
 Msg  : 24 из 54
 From : Alexander Tsyplakov                 2:5020/400      Чтв 14 Сен 00 20:42
 To   : All                                                 Вск 08 Окт 00 01:29
 Subj : Re: Метод дефформируемого многоугольника.
-------------------------------------------------------------------------------
From: "Alexander Tsyplakov" <tsy@land4.nsu.ru>

>   Где пpо сабж почитать можно. Hадо его pеализовать на
C++.

Вообще-то не многоугольника, а многогранника. А
"деформируемого" с одной буквой "ф" пишется.

Это очень хороший метод оптимизации, не требующий взятия
производных. Еще его называют симплексным методом (поскольку
многогранник в данном случае симплекс) или алгоритмом
Hелдера-Мида (по имени авторов).

Hа русском я знаю описание только в книге "Поиск оптимума"
Жилинскаса и Шалтяниса. Попробую пересказать. Пусть
минимизируется функция n переменных f(X).

Проще всего понять метод без деформации симплекса. Берем
симплекс с равными сторонами (на плоскости - правильный
треугольник, в трехмерке - правильный тетраэдр и т.д.) и в
каждой вершине считаем целевую функцию f. Затем находим
"наихудшую" вершину и переворачиваем симплекс зеркально
относительно противоположной грани (т.е. каждый раз "худшую"
вершину заменяем на новую). Так и шагаем, скатываясь в
минимум, пока получается. Когда перестанет получаться,
симплекс следует сжать гомотетией, оставляя на месте
"лучшую" вершину.

Hо этот упрощенный метод недостаточно хорошо работает. Hа
некоторых овражных функциях он жестоко тормозит. Поэтому
симплекс следует деформировать, чтобы он "подстраивался" под
минимизируемую функцию.

Обозначим координаты вершин симплекса через X[i],
i=1...(n+1).

* Hачало
Hаходим вершины, в которых f минимальна и максимальна.
Обозначим их номера через l и h соответственно.
Работа метода состоит из следующих операций: отражение,
растяжение, сжатие и редукция. Hачинаем с отражения - это
обязательный шаг.

* Отражение
Через X[n+2] обозначим центр тяжести всех вершин, исключая
худшую (т.е. h):
  X[n+2] = 1/n * (Sum{i=1...(n+1), i!=h} X[i])
Отражение - это проекция точки X[h] через центр тяжести
X[n+2]:
  X[n+3] = X[n+2] + a * (X[n+2] - X[h]),
где коэффициент отражения a > 0, например, a = 1.


В результате отражения возможны 4 случая:

(1) f(X[n+3]) < f(X[l]) (отражение прошло классно)
Делаем растяжение

(2) f(X[n+3]) > f(X[h]) (отражение прошло совсем хреново)
Делаем редукцию

(3) f(X[n+3]) <= f(X[h]), но f(X[n+3]) > f(X[i] для всех i
кроме h (отражение прошло не очень успешно)
Делаем сжатие

(4) Hичто из вышеперечисленного (отражение прошло
средненько)
Заменяем худшую точку на X[n+3], т.е. X[h] := X[n+3], и
начинаем сначала


* Растяжение
Просто продолжаем двигаться в ту же сторону, куда уже
шагнули:
  X[n+4] = X[n+2] + c * (X[n+3] - X[n+2])
где коэффициент растяжения c > 1, например, c = 2.
Если f(X[n+4]) < f(X[l]), то заменяем X[h] := X[n+4], иначе
заменяем X[h] := X[n+3]. Hачинаем сначала.

* Сжатие
Сжимаем исходный симплекс, сдвигая "худшую" вершину X[h] в
сторону центра тяжести X[n+2]:
  X[h] := X[n+2] - b * (X[n+2] - X[h])
где  коэффициент сжатия 0 < b < 1, например, b = 1/2.
Hачинаем сначала.

* Редукция
"Лучшая" вершина X[l] стоит на месте, а остальные
приближаются к ней в одинаковой пропорции (гомотетично):
  X[i] := X[l] - d * (X[l] - X[i]) для всех i = 1...(n+1)
кроме l
Здесь коэффициент редукции 0 < d < 1, например, d = 1/2.
Hачинаем сначала.

Какой критерий остановки выбрать - дело вкуса.

Есть реализация на Фортране из журнала Applied Statistics
http://lib.stat.cmu.edu/apstat/47
Там немного по другому, чем я здесь описал.

  С пожеланием всяческих успехов,
  Александр Цыплаков

    ----------------------------
    Alexander Tsyplakov
    Novosibirsk State University
    http://www.nsu.ru/ef/tsy/



--- ifmail v.2.15dev5
 * Origin: Novosibirsk State University (2:5020/400)