ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Vadim Meshkov                        2:5020/400     05 Jan 2002  14:42:32
 To : Eduard Vatutin
 Subject : Re: Алгоритм Hелдера-Мида
 -------------------------------------------------------------------------------- 
 

 Eduard Vatutin 
 <Eduard.Vatutin@p25.f43.n5035.z2.fidonet.org> пишет:
 
 EV> Есть сабжевый алгоритм (или алгоритм
 EV> деформированного многогранника), но очень
 EV> плохо описан. Hе поделится ли кто более ровным
 EV> описанием и/или кусочком кода.
 
 Алгоритм имеет много модификаций. Хорошее описание и код 
 на FORTRANе (что вряд-ли будет полезно) можно найти в 
 книге Д.Химмельблау "Прикладное нелинейное 
 программирование", М.: Мир, 1975.
 
 Hа пальцах суть такова. Hа первом шаге в пространстве 
 параметров (пусть их будет N) размещается правильный N-
 мерный симплекс (Симплекс в N-мерном пространстве --- 
 это многогранник с наименьшим числом вершин, имеющий 
 ненулевой N-мерный объем. Hа плоскости (N=2) это 
 равносторонний треугольник, в 3-пространстве --- 
 тетраедр и т.д.). Во всех вершинах (N+1) и в центре 
 тяжести симплекса вычисляются значения функции. Затем 
 выбирается наихудшая вершина, и отражается относительно 
 центра тяжести (перемещается вдоль прямой, проходящей
 через центр тяжести, за этот центр). При этом симплекс 
 как-бы выворачивается наизнанку. В случае N=2 "плохая" 
 вершина треугольника перекидывается через 
 противоположное ребро. Как далеко --- зависит от 
 соотношения значений функции в "плохой" вершине и в 
 центре тяжести. Далее в новой вершине вычисляется
 значение функции, и выбирается наихудшая вершина для 
 нового симплекса. Процесс повторяется. Таким образом 
 симплекс "перекатывается" в пространстве параметров и 
 заползает в ближайший локальный экстремум. По ходу дела 
 алгоритм следит, чтобы симплекс не вырождался и не 
 слишком сильно отклонялся от правильного многогранника 
 (иначе он будет плохо перекатываться). При приближении к 
 экстремуму размер симплекса автоматически стремится к 
 нулю.
 
 Все это, конечно, любопытно, но полагаю, что заниматься 
 самодеятельностью здесь ни к чему: в сети можно отыскать 
 массу реализаций subj, написанных на чем угодно.
 
 С уважением к собравшимся, В.М.
 -- 
 Отправлено через сервер Talk.Ru - http://www.talk.ru
 --- ifmail v.2.15dev5
  * Origin: Talk.ru (2:5020/400)
 
 

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

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