Поиск по сайту:



Проверить аттестат

Мы принимаем Яндекс.Деньги

Смотри также:

Принятие управленческих решений - Курсовая работа.

Соборное Уложение 1649 года - Курсовая работа.

Управление валютными рисками банка - Курсовая работа.

Анализ интеллекта и творческих способностей у переученных и непереученных левшей - Курсовая работа.

Все новинки...

Курсовая работа «Метод Нелдера-Мида»

Листов18
Когда сдавалась работа2010
ОценкаОтлично
Имя автораМаксим
Файл: 64.24 КБ
Поделиться:
СОДЕРЖАНИЕ
Введение
Оснавная часть
1 Постановка математической задачи
2 Рассматриваемая задача
3 Изложение метода
4 Анализ метода
5 Числовой эксперимент
Заключение
Список использованных источников
Прилодение А
 

ВВЕДЕНИЕ

В технике, экономике, естественных науках часто возникают задачи оптимизации сложной совокупности оборудования, операций, ценней или процессов. Требуется минимизировать или максимизировать некоторую функцию, называемую целевой, которая характеризует цену, вес, общую эффективность или нечто подобное при определенных ограничениях. Подобные задачи оптимизации, сформулированные математически, относятся к задачам нелинейного программирования.
Формула нелинейного программирования может быть сформулирована следующим образом: минимизировать f(x), x , при m линейных или нелинейных ограничения в виде равенств h¬j(x) = 0, j = 1, … , m , и p – m линейных или нелинейных ограничениях в виде неравенств gj(x) ? 0, j = m+1, …, p. Существуют задачи нелинейного программирования без ограничений.
Одним из методов оптимизации, не использующим производные целевой функции, является метод поиска. В проекте требуется решить задачу поиска минимума функции многих переменных с учетом без учета ограничений посредством реализации метода Нелдера-Мида.
Метод Нелдера-Мида является развитием симплексного метода Спендли, Хекста и Химсворта. Выпуклая оболочка множества (n+1)-й равноудаленной точки в n-мерном пространстве называется регулярным симплексом. Эта конфигурация рассматривается в методе Спендли, Хекста и Химсворта. В двухмерном пространстве регулярным симплексом является правильный треугольник, а в трехмерном - правильный тетраэдр. Идея метода состоит в сравнении значений функции в вершинах симплекса и перемещении симплекса в направлении оптимальной точки с помощью итерационной процедуры. В симплексном методе, предложенном первоначально, регулярный симплекс использовался на каждом этапе. Нелдер и Мид предложили несколько модификаций этого метода, допускающих, чтобы симплексы были неправильными. В результате получился очень надежный метод прямого поиска, являющийся одним из самых эффективных при n?6.
Главными особенностями алгоритма можно назвать следующие:
- метод Нелдера-Мида не накладывает ограничений на гладкость функции;
- данный метод является эффективным при низкой скорости вычисления минимизируемой функции. Как правило, на каждой итерации происходит вычисление значения функции не более чем в 3 точках;
- отсутствие теории сходимости. Алгоритм может расходиться даже на гладких функциях.

ОСНОВНАЯ ЧАСТЬ

1 Постановка математической задачи
Задачей оптимизации называется задача поиска экстремума функции, заданной на некотором множестве.
Как правило, под задачей оптимизации также подразумевается поиск элемента x, при котором целевая функция f(x) достигает экстремума.
Для того, чтобы корректно поставить задачу оптимизации необходимо задать:
- Допустимое множество
- Целевую функцию
- Критерий поиска (max или min)
Тогда решить задачу означает одно из:
- Показать что
- Показать, что целевая функция f(x) не ограничена.
- Найти
- Если не существует , то найти
Если допустимое множество , то такая задача называется задачей безусловной оптимизации, в противном случае — задачей условной оптимизации.

2 Рассматриваемая задача

Метод Нелдера-Мида, также известный как метод поиска по деформируемому многограннику, — метод безусловной оптимизации вещественной функции от нескольких переменных. Иными словами на допустимое множество накладываются следующие ограничения: .
Кроме того, одним из главных преимуществ данного метода является то, что в нем не используется градиента целевой функции, что позволяет применять его к негладким функциям. Метод Нелдера-Мида использует понятие симплекса n-мерного пространства.
Множество называется выпуклым, если .
Выпуклой оболочкой множества X называется наименьшее выпуклое множество C такое, что
Симплексом или n-симплексом называется выпуклая оболочка множества (n+1) точек.
Например:
1-симплексом является отрезок
2-симплексом является треугольник
3-симплексом является тетраэдр.

3 Изложение метода

Параметрами метода являются:
- коэффициент отражения ?>0, обычно выбирается равным 1.
- коэффициент сжатия ?>0, обычно выбирается равным 0.5.
- коэффициент растяжения ?>0 обычно выбирается равным 2.
3.1 Инициализация
Произвольным образом выбирается n+1 точка xi=( , ,…, ) , образующие симплекс n-мерного пространства. В этих точках вычисляются значения функции: f1=f( ), f2= f( ), … , fn+1= f( ).
1. Сортировка. Из вершин симплекса выбираем три точки: xh с наибольшим (из выбранных) значением функции fh, xg со следующим по величине значением fg и xl с наименьшим значением функции fl. Целью дальнейших манипуляций будет уменьшение по крайней мере fh.
2. Найдём центр тяжести всех точек, за исключением xh:xc= i. Вычислять fc=f(xc) не обязательно.
3. Отражение. Отразим точку xh относительно xc с коэффициентом ? (при ?=1 это будет центральная симметрия, в общем случае — гомотетия), получим точку xr и вычислим в ней функцию: fr=f(xr). Координаты новой точки вычисляются по формуле xr=(1+ ? )xc- ? xh.
4. Далее сравниваем значение fr со значениями fh,fg,fl:
4а). Если fr
Если fe
Если fe>fl , то заменяем точку xh на xr и заканчиваем итерацию (на шаг 8).
4b). Если fl
4с). Если fh>fr>fg , то меняем обозначения xr,xh (и соответствующие значения функции) местами и переходим на шаг 5.
4d). Если fr>fh, то переходим на шаг 5.
5. Сжатие. Строим точку xs=?xh+(1-?)xc и вычисляем в ней значение fs.
6. Если fs
7. Если fs>fh, то производим сжатие симплекса — гомотетию к точке с наименьшим значением x0: xi x0+(xi-x0)/2 для всех требуемых точек xi.
8. Последний шаг — проверка сходимости. Может выполняться по-разному, например, оценкой дисперсии набора точек. Суть проверки заключается в том, чтобы проверить взаимную близость полученных вершин симплекса, что предполагает и близость их к искомому минимуму. Если требуемая точность ещё не достигнута, можно продолжить итерации с шага 1.

4 Анализ метода

Изучение сходимости алгоритма Нелдера-Мида является трудной математической задачей. Известные результаты о сходимости симплекс-методов основаны на следующих предположениях:
- Симплекс не должен вырождаться при итерациях алгоритма
- На гладкость функции накладываются некоторые условия
В общем случае для метода Нелдера-Мида не выполняются сразу оба эти предположения, а следовательно, об условиях сходимости известно весьма мало. МакКиннон в 1998 году описал семейство строго выпуклых функций и класс начальных симплексов в двухмерном пространстве, для которых все вершины рабочего симплекса сходятся не к оптимальной точке. В 1998 году Лагариас опубликовал статью, в которой он исследовал сходимость метода в одно- и двухмерном пространствах для некоторых строго выпуклых функций с ограниченными поверхностями уровня.
Алгоритм Нелдера-Мида дает сильное уменьшение значение функции уже при первых нескольких итерациях и быстро достигает необходимой точности. Как правило, алгоритм производит одно или два вычисления функции на каждой итерации, если не учитывать сжатие, которое редко используется на практике. Это крайне важно в тех ситуациях, когда вычисление значений функции очень дорого или же требует много времени. Для подобных задач алгоритм Нелдера-Мида гораздо эффективнее многих других методов, требующих вычисления не менее значений функции на каждой итерации.
Главными преимуществами алгоритма являются его простота и эффективность.
С другой стороны, в силу отсутствия теории сходимости, на практике метод может приводить к неверному ответу даже для гладких функций. Также возможна ситуация, когда рабочий симплекс находится далеко от оптимальной точки, а алгоритм производит большое число итерации, при этом мало изменяя значения функции. Эвристический метод решения этой проблемы заключается в запуске алгоритма несколько раз и ограничении числа итераций.

5 Числовой эксперимент

В качестве числового эксперимента метод Нелдера-Мида был применен для вычисления минимума функции Розенброка:
для которой и . В качестве начального приближения был взят симплекс .
Ниже приведена таблица промежуточных результатов после каждых 10 итераций алгоритма.
Таблица 1 – Промежуточные результаты
Число итераций Координаты первой точки симплекса Координаты второй точки симплекса Координаты третьей точки симплекса fl fh
10 x=2.78; y=7.55; x=2.39; y=6.39; x=1.73; y=6.87; 6.725 1479.400
20 x=2.63; y=6.96; x=2.70; y=7.29; x=2.64; y=6.88; 2.769 3.225
30 x=2.24; y=4.94; x=2.35; y=5.50; x=2.42; y=5.86; 1.823 2.017
40 x=1.90; y=3.58; x=1.83; y=3.38; x=1.97; y=3.89; 0.821 0.996
50 x=1.51; y=2.28; x=1.53; y=2.36; x=1.57; y=2.47; 0.273 0.327
60 x=1.20; y=1.42; x=1.23; y=1.51; x=1.27; y=1.61; 0.050 0.079
70 x=0.99; y=0.97; x=1.01; y=1.02; x=0.96; y=0.93; 0.000 0.003
Итоговое количество итераций 79. Вычисленный минимум функционала равен .
Метод Нелдера-Мида прост в реализации, в качестве параметров алгоритма как правило используются следующие:
В качестве начального, как правило, используется произвольный симплекс. Также возможно многократное вычисление минимума при различных случайных начальных симплексах.

ЗАКЛЮЧЕНИЕ

Была осуществлена реализация метода поиска по деформируемому многограннику для функции Розенброка с визуализацией траектории метода.
Симплекс-метод Нелдера-Мида является очень эффективным алгоритмом поиска экстремума функции многих переменных, не накладывающим ограничений на гладкость функции. На каждой итерации алгоритма производится как правило одно-два вычисления значений функции, что чрезвычайно эффективно если эти вычисления очень медленны. Кроме того, алгоритма очень прост в реализации. Главным же его недостатком является отсутствие теории сходимости и наличие примеров, когда метод расходится даже на гладких функциях.

СПИСОК ИСПОЛЗОВАННЫХ ИСТОЧНИКОВ

1. Банди Б. Методы Оптимизации. Вводный курс. М.: Радио и связь, 1988.
2. http://www.scholarpedia.org/article/Nelder-Mead_algorithm

Приложение А

import java.awt.*;
import java.util.*;
import java.awt.event.*;
public class Dot
{
public double x1,x2;
public Dot(){x1=0;x2=0;}
public Dot(double X1,double X2){x1=X1;x2=X2;}
public Dot(Dot D){x1=D.x1; x2=D.x2;}
public Dot (Dot d1,Dot d0){x1 = 2*d1.x1-d0.x1; x2 = 2*d1.x2-d0.x2;}
public void setDot(Dot D){x1=D.x1; x2=D.x2;}
public void setDot(Dot d1,Dot d0){x1 = 2*d1.x1-d0.x1; x2 = 2*d1.x2-d0.x2;}
public void setDot(double x1,double x2){this.x1=x1;this.x2=x2;}
public boolean equalTo(Dot D){ if ((x1==D.x1)&&(x2==D.x2)) return true; return false; }
}
public class Triangle
{
public Dot xl,xg,xh;
public int[] masx = new int[3];
public int[] masy = new int[3];
public Triangle(){ xl = new Dot(); xg = new Dot(); xh = new Dot(); }
public Triangle(Dot xl,Dot xg,Dot xh){ this.xl = new Dot(xl); this.xg = new Dot(xg); this.xh = new Dot(xh); }
public Triangle(Triangle T){ xl = new Dot(T.xl); xg = new Dot(T.xg); xh = new Dot(T.xh); }
public void setTriangle(Triangle T){ xl.setDot(T.xl); xg.setDot(T.xg); xh.setDot(T.xh); }
public void setTriangle(Dot xl,Dot xg,Dot xh){ this.xl.setDot(xl); this.xg.setDot(xg); this.xh.setDot(xh); }
public void cutInHalf() { xg.setDot((xg.x1+xl.x1)/2, (xg.x2+xl.x2)/2); xh.setDot((xh.x1+xl.x1)/2, (xh.x2+xl.x2)/2);}}
public class Method extends Frame
{
double scl = 630;
double indent = 30;
double topY = 23;
int mesure = 13;
double step = mesure/5;
int precision = -8;
double alfa = 1;
double beta = 0.5;
double gama = 2;
double masX1[]=new double [(int)(2*scl)+2];
double masX2[]=new double [(int)scl*2+2];
int masx1[] = new int [(int)scl*2+2];
int masx2[] = new int [(int)scl*2+2];
Triangle T[] = new Triangle[(int)(10*scl)];
int t = 0;
String message = "";
String message2 = "";