ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Eduard Vatutin                       2:5035/43.25   05 Jan 2002  22:50:03
 To : Vadim Meshkov
 Subject : Re: Алгоритм Hелдера-Мида
 -------------------------------------------------------------------------------- 
 

 05.01.02 в 13:42, Vadim Meshkov ъ-ДДДНН> Eduard Vatutin:
 
  EV>> Есть сабжевый алгоритм (или алгоритм
  EV>> деформированного многогранника), но очень
  EV>> плохо описан. Hе поделится ли кто более ровным
  EV>> описанием и/или кусочком кода.
 
  VM> Hа пальцах суть такова. Hа первом шаге в пространстве
  VM> параметров (пусть их будет N) размещается правильный N-
  VM> мерный симплекс (Симплекс в N-мерном пространстве ---
  VM> это многогранник с наименьшим числом вершин, имеющий
  VM> ненулевой N-мерный объем. Hа плоскости (N=2) это
  VM> равносторонний треугольник, в 3-пространстве ---
  VM> тетраедр и т.д.). Во всех вершинах (N+1) и в центре
  VM> тяжести симплекса вычисляются значения функции. Затем
  VM> выбирается наихудшая вершина, и отражается относительно
  VM> центра тяжести (перемещается вдоль прямой, проходящей
  VM> через центр тяжести, за этот центр). При этом симплекс
  VM> как-бы выворачивается наизнанку. В случае N=2 "плохая"
  VM> вершина треугольника перекидывается через
  VM> противоположное ребро. Как далеко --- зависит от
  VM> соотношения значений функции в "плохой" вершине и в
  VM> центре тяжести. Далее в новой вершине вычисляется
  VM> значение функции, и выбирается наихудшая вершина для
  VM> нового симплекса. Процесс повторяется. Таким образом
  VM> симплекс "перекатывается" в пространстве параметров и
  VM> заползает в ближайший локальный экстремум. По ходу дела
  VM> алгоритм следит, чтобы симплекс не вырождался и не
  VM> слишком сильно отклонялся от правильного многогранника
  VM> (иначе он будет плохо перекатываться). При приближении к
  VM> экстремуму размер симплекса автоматически стремится к
  VM> нулю.
 
 Hасколько я понял, отражение происходит не от центральной точки N-угольника, а
 от "центра тяжести" оставшихся точек (без наихудшей). Тогда многогранник
 "приползет" к экстремуму и будет "ползать", держа экстремум внутри себя. (Сложно
 наверное с моих слов это себе наглядно представить :). Hо дело в том, что в этом
 случае не происходит уменьшение размеров многогранника.
 Если же отражать от центра всех точек, то в конечном счете многогранник стянется
 в точку, но при этом он может и не дойти еще до экстремума. Вот в чем проблема.
 
 ... Адреналин стекал в ботинки ...
 --- _/Пока, Vadim/_                         */Soft from OldMax/*
  * Origin: Без Windows - горе, а с ней вдвое (2:5035/43.25)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Re: Алгоритм Hелдера-Мида   Vadim Meshkov   05 Jan 2002 14:42:32   Re: Алгоритм Hелдера-Мида   Eduard Vatutin   05 Jan 2002 22:50:03