Оптимизация прямого поиска для определения минимума функции n переменных методом Нелдера-Мида.

Федеральное агентство по образованию

Государственное образовательное учреждение высшего

профессионального образования

Самарский государственный технический университет

Факультет автоматики и информационных технологий

Кафедра информационно-измерительной техники

Расчетно-пояснительная записка

к курсовой работе Оптимизация прямого поиска для определения минимума функции 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.

Если >, то сразу переходим к шагу сжатия и находим точку из соотношения:

Если <, то сначала заменим точку на точку , а затем произведем сжатие. Тогда точку найдем из соотношения (см. рис.4):

Коэффициенты в вы

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать