Оптимизация прямого поиска для определения минимума функции n переменных методом Нелдера-Мида. (стр. 1 из 2)
Федеральное агентство по образованию
Государственное образовательное учреждение высшего
профессионального образования
Самарский государственный технический университет
Факультет автоматики и информационных технологий
Кафедра информационно-измерительной техники
Расчетно-пояснительная записка
к курсовой работе Оптимизация прямого поиска для определения минимума функции n переменных методом Нелдера-Мида.
по курсуСистемы автоматического проектирования
НормоконтрольПетрова Т. А.
Руководитель работы Хавлин О.В.
Студент Бромберг Е.Е.
Группа 5-АИТ-5
Срок выполнения ____________________________
Работа защищена с оценкой___________
г. Самара 2008
Реферат
Пояснительная записка содержит 16страниц, 5 рисунков и 2 источника.
ЭКСТРЕМУМ ФУНКЦИИ, БАЗИСНАЯ ТОЧКА, СИМПЛЕКС, ОТРАЖЕНИЕ, РАСТЯЖЕНИЕ, СЖАТИЕ, ДЛИНА ШАГА, МЕТОД НЕЛДЕРА-МИДА.
В пояснительной записке изложены основы прямого поиска для определения минимума функции n переменных. Выбран метод оптимизации поиска Нелдера-Мида. В расчетной части метод Нелдера-Мида реализован программно, в среде TurboPascal, представлены блок схема алгоритма оптимизации, листинг программы.
| СОДЕРЖАНИЕ | |
| Введение……………………………………………………... 1 Метод Нелдера-Мида…………………………………...2 Блок –схема алгоритма…………………………………..3 Листинг программы……………………………………...4 Список используемой литературы……………………… | 4 5 9 10 16 |
ВВЕДЕНИЕ
На разработку методов прямого поиска для определения минимума функции n переменных было затрачено много усилий. Методы прямого поиска являются методами, в которых используются только значения функции. Один из наиболее надежных метод Нелдера-Мида, являющийся одним из самых эффективных, если
Рассмотрим функцию двух переменных. Ее линии постоянного уровня представлены на рис. 1. Линией постоянного уровня называется кривая в двухмерном сечении пространственных параметров ( в данном случае – в плоскости
), значение функции на которой константа. Минимум функции лежит в точке 
, где 
-где ряд значений от 0,1 до 1 с шагом 0,1. 
1 МЕТОД НЕЛДЕРА-МИДА
Метод Нелдера-Мида является развитием симплексного метода Спендли, Хекста и Химсворта. Множество значений
й равноудаленной точки в n-мерном пространстве называется регулярным симплексом. Эта конфигурация рассматривается в методе Спендли, Хекста и Химсворта. Следовательно, в двумерном пространстве симплексом является равносторонний треугольник, а в трехмерном пространстве – правильный тетраэдр.Идея метода состоит в сравнении значений функции в
вершинах симплекса и перемещении симплекса в направлении оптимальной точки с помощью итерационной процедуры. В симплексном методе, предложенным первоначально, регулярный симплекс использовался на каждом этапе. Нелдер и Мид предложили несколько модификаций этого метода, допускающих, чтобы симплексы были неправильными. В результате получился очень надежный метод прямого поиска, являющийся одним из самый эффективных, если В данном методе симплекс перемещается с помощью трех основных операций: отражение, растяжение и сжатия. Рассмотрим основные шаги процедуры:
А. Найдем значения функции
в вершинах симплекса.
Б. Найдем наибольшее значение функции
, следующее за набольшим значением функции 
, наименьшее значение функции 
и соответствующие им точки 
.В. Найдем центр тяжести всех точек, за исключением точки
. Пусть центром тяжести будет 
И вычислим
.Г. Удобнее всего начать перемещение от точки
. Отразим точку относительно точки 
, получим точку 
и найдем 
.Операция отражения иллюстрируется рис. 1. Если
коэффициент отражения, то положение точки определяется следующим образом: 
Д. Сравним значения функции
и .1. Если
< , то мы получим наименьшее значение функции. Направление из точки в точку наиболее удобно для перемещения. Таким образом, мы производим растяжение в этом направлении и находим точку 
и значение 
. Рисунок 2 иллюстрирует операцию растяжения симплекса. Коэффициент растяжения 
можно найти из следующих соотношений: 
2. Если
> , но 
то является лучшей точкой по с сравнению с другими двумя точками симплекса и мы заменяем точку на точку и, если сходимость не достигнута, возвращаемся на шаг Б.3. Если
> и > , то перейдите на шаг Е.Е. Сравним значения функции
и 
.1. Если
> , то переходим непосредственно к шагу Е, 2.Если
< , то замещаем точку на точку и значение функции на значение . Запоминаем значение > из шага Д,2. приведенного выше. Затем переходим на шаг Е, 2.2. В этом случае
> , поэтому ясно, что мы переместились далеко от точки к точке . Попытаемся исправить это, найдя точку 
с помощью шага сжатия, показанного на рисунке 3.