Методы многомерной оптимизации: многомерная оптимизация методом Хука и Дживса

Сравнение методов многомерной оптимизации Хука-Дживса и Розенброка по числу вычислений и по числу вызова оптимизируемой функции в процессе оптимизации. Особенности применения алгоритмов ускоряющего шага, в которых используется поиск по направлению.

Рубрика Программирование, компьютеры и кибернетика
Вид лабораторная работа
Язык русский
Дата добавления 14.07.2012
Размер файла 2,8 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ

(НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ)

Отчет по лабораторной работе за курс:

«Теория оптимального планирования и управления»

кафедры 302

Тема

«Методы многомерной оптимизации: многомерная оптимизация методом Хука и Дживса»

Выполнила студентка

группы 03-323:

Ежова О.С.

Преподаватель:

Красовская М.А.

Москва

2012

Постановка задачи

Найти методом Хука и Дживса с непрерывным шагом:

MIN F1(x)= (Х1-4)4 +(X1-3 X2 )2,

с начальной точкой X0=(1;0)

Предусмотреть ввод точности .

Провести: многомерный оптимизация дживс розенброк

1. Нахождение экстремума функции F1(X) при различных значениях начальной точки;

2. Определение экстремума заданной функции при различных значениях точности (=0.01, =0.1, =0.001);

Алгоритм метода

Графики функции

Результаты работы программы

Начальная точка (1;0)

1) Начальная точка X0 = [1;0]

Точность е = 0.1

Опт. значение аргумента (3,8826;1,3109)

Опт. значение функции 0,00269660220874356

Кол-во итераций метода 3

2) Точность е = 0.01

Опт. значение аргумента (4,0037;1,3344)

Опт. значение функции 1,48019246160121E-7

Кол-во итераций метода 3

3) Точность е = 0.001

Опт. значение аргумента (3,9957;1,3321)

Опт. значение функции 6,03879971567203E-7

Кол-во итераций метода 3

Начальная точка (-2;2)

1) Точность е = 0.1

Опт. значение аргумента (3,7289;1,2470)

Опт. значение функции 0,00554697770081615

Кол-во итераций метода 5

2) Точность е = 0.01

Опт. значение аргумента (3,9867;1,3287)

Опт. значение функции 2,17609241998115E-7

Кол-во итераций метода 6

3) Точность е = 0.001

Опт. значение аргумента (3,9907;1,3305)

Опт. значение функции 5,73924492635677E-7

Кол-во итераций метода 7

Начальная точка (4;2)

1) Точность е = 0.1

Опт. значение аргумента (4,5855;1,5198)

Опт. значение функции 0,118199132492491

Кол-во итераций метода 2

2) Точность е = 0.01

Опт. значение аргумента (4,5914;1,5296)

Опт. значение функции 0,122304388908469

Кол-во итераций метода 2

3) Точность е = 0.001

Опт. значение аргумента (4,0108;1,3372)

Опт. значение функции 6,2375505275578E-7

Кол-во итераций метода 5

Листинг программы

unit Xuk;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Grids;

type

TForm1 = class(TForm)

Edit2: TEdit;

Edit4: TEdit;

Label1: TLabel;

Label2: TLabel;

Label4: TLabel;

ComboBox1: TComboBox;

Label7: TLabel;

Label8: TLabel;

Label9: TLabel;

StringGrid1: TStringGrid;

Edit1: TEdit;

Edit6: TEdit;

Edit7: TEdit;

Button1: TButton;

Edit3: TEdit;

Label3: TLabel;

Edit5: TEdit;

Edit8: TEdit;

procedure FormCreate(Sender: TObject);

procedure Button1Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

type Tper = class(TObject)

private

one:real;

two:real;

end;

procedure schityvanie;

function func (h:real):real;

procedure sechenie(var c:real);

var

Form1: TForm1;

alfa,t1,t2,x1,x2,e,F:real;

k,j,v,q:integer;

x,y,xp,d:Tper;

xstr,ystr,dstr:string;

implementation

{$R *.dfm}

procedure TForm1.FormCreate(Sender: TObject);

begin

ComboBox1.Items.Add('(x1-2)^4+(x1-2*x2)^2');

ComboBox1.Items.Add('4*x1+8*x2-2*x1^2-2*x2^2');

x:=Tper.Create;

xp:=Tper.Create;

y:=Tper.Create;

d:=Tper.Create;

end;

//считывание начальных значений

procedure schityvanie;

var

o,s,i,p:integer;

str,str1:string;

flaag:boolean;

begin

str1:='';

x.one:=0;

x.two:=0;

flaag:=true;

for o:=0 to 9 do

for s:=0 to Form1.StringGrid1.RowCount do

Form1.StringGrid1.Cells[o,s]:='';

o:=0;

Form1.StringGrid1.RowCount:=10;

s:=2;

x.one:=StrToFloat(Form1.Edit2.Text);

x.two:=StrToFloat(Form1.Edit3.Text);

e:=StrToFloat(Form1.Edit4.Text);

j:=1;

Form1.stringgrid1.Cells[0,0]:='K';

Form1.stringgrid1.Cells[1,0]:='Xk/F(Xk)';

Form1.stringgrid1.Cells[2,0]:='j';

Form1.stringgrid1.Cells[3,0]:='dj';

Form1.stringgrid1.Cells[4,0]:='yj';

Form1.stringgrid1.Cells[5,0]:='shag';

Form1.stringgrid1.Cells[6,0]:='yj+1';

Form1.stringgrid1.Cells[7,0]:='d';

Form1.stringgrid1.Cells[8,0]:='shag';

Form1.stringgrid1.Cells[9,0]:='y3+shag*d';

end;

//вычисление значения функции

function func(h:real):real;

begin

If Form1.ComboBox1.Text='(x1-2)^4+(x1-2*x2)^2' then

func:=((y.one+h*d.one)-2)*((y.one+h*d.one)-2)*((y.one+h*d.one)-2)*((y.one+h*d.one)-2)+

((y.one+h*d.one)-2*(y.two+h*d.two))*((y.one+h*d.one)-2*(y.two+h*d.two))

else func:=4*(y.one+h*d.one)+8*(y.two+h*d.two)-2*(y.one+h*d.one)*(y.one+h*d.one)-2*(y.two+h*d.two)*(y.two+h*d.two);

end;

//метод золотого сечения

procedure sechenie(var c:real);

var

a,b,Fn,Fm,m,n:real;

begin

Fn:=0;

Fm:=0;

a:=StrToFloat(Form1.Edit5.Text);

b:=StrToFloat(Form1.Edit8.Text);

alfa:=0.618;

n:=a+(1-alfa)*(b-a);

m:=a+alfa*(b-a);

Fn:=func(n);

Fm:=func(m);

While (b-a)>=e do

begin

If Fn > Fm then

begin

a:=n;

n:=m;

Fn:=Fm;

m:=a+alfa*(b-a);

Fm:=func(m);

end

else

begin

b:=m;

m:=n;

Fm:=Fn;

n:=a+(1-alfa)*(b-a);

Fn:=func(n);

end;

end;

c:=(a+b)/2;

end;

//метод Хука и Дживса

procedure TForm1.Button1Click(Sender: TObject);

var

j,w,num:integer;

Shag,Zfun,per:real;

flag:boolean;

arg:string;

begin

q:=0;

k:=0;

num:=2;

j:=0;

Shag:=0;

schityvanie;

xstr:='['+FloatToStrF(x.one,ffFixed,7,4)+';'

+ FloatToStrF(x.two,ffFixed,7,4)+']';

y.one:=x.one;

y.two:=x.two;

Zfun:=func(0);

Form1.stringgrid1.Cells[1,2]:=FloatToStr(Zfun);

ystr:='['+FloatToStrF(x.one,ffFixed,7,4)+';'

+ FloatToStrF(x.two,ffFixed,7,4)+']';

flag:=false;

while not flag do

begin

for j:= 1 to num do

begin

w:=j mod 2;

inc(q);

case j of

1:

begin

d.one:=1;

d.two:=0;

end;

2:

begin

d.one:=0;

d.two:=1;

end;

end;

dstr:='['+FloatToStrF(d.one,ffFixed,2,2)+';'

+ FloatToStrF(d.two,ffFixed,2,2)+']';

sechenie(Shag);

If w <> 0 then

begin

inc(k);

Form1.stringgrid1.Cells[0,q]:=IntToStr(k);

Form1.stringgrid1.Cells[1,q]:=xstr;

end;

Form1.stringgrid1.Cells[2,q]:=IntToStr(j);

Form1.stringgrid1.Cells[3,q]:=dstr;

Form1.stringgrid1.Cells[4,q]:=ystr;

Form1.stringgrid1.Cells[5,q]:=FloatToStr(Shag);

y.one:=y.one+shag*d.one;

y.two:=y.two+shag*d.two;

ystr:='['+FloatToStrF(y.one,ffFixed,7,4)+';'

+ FloatToStrF(y.two,ffFixed,7,4)+']';

Form1.stringgrid1.Cells[6,q]:=ystr;

If q>9 then Form1.StringGrid1.RowCount:=Form1.StringGrid1.RowCount+1;

end;

xp.one:=x.one;

xp.two:=x.two;

x.one:=y.one;

x.two:=y.two;

Per:=sqr((x.one-xp.one)*(x.one-xp.one)+(x.two-xp.two)*(x.two-xp.two));

If (per<e) then flag:=true

else

begin

d.one:=x.one-xp.one;

d.two:=x.two-xp.two;

dstr:='['+FloatToStrF(d.one,ffFixed,7,4)+';'

+ FloatToStrF(d.two,ffFixed,7,4)+']';

sechenie(Shag);

y.one:=x.one+shag*d.one;

y.two:=x.two+shag*d.two;

ystr:='['+FloatToStrF(y.one,ffFixed,7,4)+';'

+ FloatToStrF(y.two,ffFixed,7,4)+']';

xstr:=ystr;

If w = 0 then

begin

Form1.stringgrid1.Cells[7,q]:=dstr;

Form1.stringgrid1.Cells[8,q]:=FloatToStr(Shag);

Form1.stringgrid1.Cells[9,q]:=ystr;

end;

If q>100 then

begin

flag:=true;

ShowMessage (`функция не оптимизируется');

end;

end;

If q>2 then

begin

Zfun:=func(0);

Form1.stringgrid1.Cells[1,q]:=FloatToStr(Zfun);

end;

end;

Form1.Edit1.Text:=FloatToStr(k);

Form1.Edit6.Text:='['+FloatToStrF(x.one,ffFixed,7,4)+';'

+ FloatToStrF(x.two,ffFixed,7,4)+']';

Form1.Edit7.Text:=FloatToStr(Zfun);

end;

end.

Сводные таблицы

Хук и Дживс

Точность

Опт. значение аргумента

Опт. значение функции

Кол-во итераций

Начальная точка X0 = [1;0]

0.1

[3,8826;1,3109]

0,00269660220874356

3

0.01

[4,0037;1,3344]

1,48019246160121E-7

3

0.001

[3,9957;1,3321]

6,03879971567203E-8

3

Начальная точка X0 = [-2;2]

0.1

[3,7289;1,2470]

0,00554697770081615

5

0.01

[3,9867;1,3287]

2,17609241998115E-7

6

0.001

[3,9907;1,3305]

5,73924492635677E-7

7

Начальная точка X0 = [4;2]

0.1

[4,5855;1,5198]

0,118199132492491

2

0.01

[4,5914;1,5296]

0,122304388908469

2

0.001

[4,0108;1,3372]

6,2375505275578E-7

5

Розенброк

Точность

Опт. значение аргумента

Опт. значение функции

Кол-во итераций

Начальная точка X0 = [1;0]

0.1

[3,8825;1,3110]

0,00269660220874298

2

0.01

[4,0036;1,3345]

1,48019246160075E-7

3

0.001

[3,9956;1,3322]

6,03879971567171E-8

3

Начальная точка X0 = [-2;2]

0.1

[3,7288;1,2471]

0,00554697770081565

6

0.01

[3,9866;1,3288]

2,17609241998102E-7

6

0.001

[3,9906;1,3306]

5,73924492635629E-7

7

Начальная точка X0 = [4;2]

0.1

[4,5854;1,5199]

0,118199132492464

3

0.01

[4,5913;1,5297]

0,122304388908453

4

0.001

[4,0107;1,3373]

6,2375505275548E-7

5

Выводы

В ходе лабораторной работы был изучен метод многомерной оптимизации Хука и Дживса с непрерывным шагом.

Метод относится к категории методов,в которых используется поиск по направлению. Алгоритмы,в которых используется такой поиск, называют алгоритмами ускоряющего шага. Каждая итерация этих алгоритмов состоит из двух этапов: поиск вдоль координатных осей, или, исследующий поиск; поиск по образцу, или ускоряющий шаг.

Была написана программа и с помощью неё изучена функция

F(X) = (Х1-4)4 +(X1-3X2)2

Для наглядности результатов были проварьированы точность (основное значение критерия остановки) и начальная точка.

Были сделаны следующие выводы:

- количество итераций увеличивается с увеличением точности

- количество итераций увеличивается в зависимости от удаленности начальной точки от оптимального решения..

Экспериментальное сравнение алгоритмов Хука-Дживса и Розенброка по числу вычислений и по числу вызова оптимизируемой функции в процессе оптимизации показывает в пользу алгоритма Розенброка. Но в методе Розенброка вычислительные затраты идут на пересчет системы ортогональных направлений.

Размещено на Allbest.ru


Подобные документы

  • Теоретические основы метода оптимизации. Разработка компьютерной системы для решения задач многомерной безусловной оптимизации методом Хука-Дживса с минимизацией по направлению. Описание структуры программы и результаты ее отладки на контрольных примерах.

    курсовая работа [595,4 K], добавлен 13.01.2014

  • Задачи оптимизации в математике и информатике. Классификация методов оптимизации. Методы с переменной метрикой. Значение функции на заданном интервале. Локальный минимум функции. Методы минимизации функции. Классификация методов многомерной оптимизации.

    курсовая работа [1,5 M], добавлен 19.06.2012

  • Программирование численных методов одномерной оптимизации. Решение одномерных задач оптимизации методами последовательного поиска. Градиентные методы и их применение для оптимизации на ЭВМ математических моделей объектов. Методы нулевого порядка.

    контрольная работа [257,9 K], добавлен 15.01.2009

  • Программная реализация приложения для вычисления заданных функций. Процедура поиска минимума функции. Применение методов Хука-Дживса и градиентного спуска для решения задачи. Исследование функции в окрестности базисной точки, определение ее координат.

    контрольная работа [767,1 K], добавлен 02.02.2014

  • Задача оптимизации с точки зрения математики как задача нахождения экстремума вещественной функции в некоторой области. Классификация и типы методов оптимизации, условия их практического использования. Создание программы, ее листинг, описание алгоритмов.

    курсовая работа [181,7 K], добавлен 22.06.2012

  • Необходимые условия экстремума. Разработка машинного алгоритма и программы многомерной оптимизации для градиентного метода с использованием метода равномерного поиска. Проверка необходимых и достаточных условий экстремума для найденной точки минимума.

    курсовая работа [249,8 K], добавлен 25.09.2013

  • Нахождение стационарной точки. Расчет безусловного экстремума функции методами прямого поиска. Графическое пояснение метода равномерного симплекса. Метод поиска Хука-Дживса. Метод сопряженных направлений Пауэлла. Разработка программного модуля расчетов.

    курсовая работа [1,4 M], добавлен 16.09.2012

  • Математическое описание и аналитическое исследование методов оптимизации: Нелдера-Мида и градиентный с дроблением шага. Зависимость числа итераций от заданной точности. Решение задачи минимизации для каждого из методов и ее графическая интерпретация.

    курсовая работа [472,8 K], добавлен 22.11.2009

  • Решения алгебраических уравнений методом выделения корней. Аппроксимация функций методом наименьших квадратов; дихотомия, бисекция. Одномерная оптимизация многоэкстремальных функций; метод золотого сечения. Многомерная оптимизация градиентным методом.

    курсовая работа [956,7 K], добавлен 04.03.2013

  • Математические основы оптимизации. Постановка задачи оптимизации. Методы оптимизации. Решение задачи классическим симплекс методом. Графический метод. Решение задач с помощью Excel. Коэффициенты целевой функции. Линейное программирование, метод, задачи.

    реферат [157,5 K], добавлен 21.08.2008

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.