Методические указания к курсовой работе для студентов специальности «Управление и информатика в технических системах» (стр. 5 из 8)
На основе рассмотренных способов выбора случайных направлений построен ряд эффективных алгоритмов поиска.
3.9 Метод Нелдера – Мида
Метод Нелдера — Мида (называется также поиском по деформируемому многограннику) является развитием симплексного метода Спендли, Хекста и Химсворта. Эта конфигурация рассматривается в методе Спендли, Хекста и Химсворта. Идея метода состоит в сравнении значений функции в
вершинах симплекса и перемещении симплекса в направлении оптимальной точки с помощью итерационной процедуры. В симплексном методе, предложенном первоначально, регулярный симплекс использовался на каждом этапе. Нелдер и Мид предложили несколько модификаций этого метода, допускающих, чтобы симплексы были неправильными. В результате получился очень надежный метод прямого поиска, являющийся одним из самых эффективных, если 
.В методе Спендли, Хекста и Химсворта симплекс перемещается с помощью трех основных операций: отражения, растяжения и сжатия. Смысл этих операций станет понятным при рассмотрении шагов процедуры.
1. Найдем значения функции
, 
, ..., 
в вершинах симплекса.2. Найдем наибольшее значение функции
, следующее за наибольшим значением функции 
, наименьшее значение функции 
и соответствующие им точки 
, 
, 
.3. Найдем центр тяжести всех точек, за исключением точки
: 
.и вычислим
.4. Удобнее всего начать перемещение от точки
. Отразив точку 
относительно точки 
, получим точку 
и найдем 
. Если 
– коэффициент отражения, то положение точки 
определяется следующим образом: 
,т.е.
, 
.5. Сравним значения функций
и .Если
, то мы получили наименьшее значение функции. Направление из точки 
в точку 
наиболее удобно для перемещения. Таким образом, мы производим растяжение в этом направлении и находим точку 
и значение функции 
.Коэффициент растяжения
можно найти из следующих соотношений: 
,т.е.
, 
.6. Если
, то заменяем точку 
на точку и проверяем 
-ю точку симплекса на сходимость к минимуму (см. п. 2). Если сходимость достигнута, то процесс останавливается; в противном случае возвращаемся к п. 2.7. Если
, то отбрасываем точку . Очевидно, мы переместились слишком далеко от точки 
к точке 
. Поэтому следует заменить точку на точку , в которой было получено улучшение (шаг 5), проверить сходимость и, если она не достигнута, вернуться к п. 2.8. Если
, но 
, то является лучшей точкой по сравнению с другими двумя точками симплекса и мы заменяем точку на точку и, если сходимость не достигнута, возвращаемся к п. 2.9. Если
и 
, перейдем к п.10.10. Сравним значения функции
и 
.Если
, то переходим непосредственно к шагу сжатия в п. 11.Если
, то заменяем точку на точку и значение функции 
на значение функции 
. Запоминаем значение из п 8. Затем переходим к п. 11.11. В этом случае
, поэтому ясно, что мы переместились слишком далеко от точки 
к точке . Попытаемся исправить это, найдя точку 
(а затем 
) с помощью шага сжатия. Если 
, то сразу переходим к шагу сжатия и находим точку 
из соотношения: 
,где
– коэффициент сжатия.Тогда
.