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

Тип работы:
Лабораторная работа
Предмет:
Программирование


Узнать стоимость

Детальная информация о работе

Выдержка из работы

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

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

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

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

кафедры 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,269 660 220 874 356

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

2) Точность е = 0. 01

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

Опт. значение функции 1,4 801 924 616 0121E-7

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

3) Точность е = 0. 001

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

Опт. значение функции 6,387 997 156 7203E-7

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

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

1) Точность е = 0. 1

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

Опт. значение функции 0,554 697 770 081 615

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

2) Точность е = 0. 01

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

Опт. значение функции 2,1 760 924 199 8115E-7

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

3) Точность е = 0. 001

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

Опт. значение функции 5,7 392 449 263 5677E-7

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

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

1) Точность е = 0. 1

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

Опт. значение функции 0,118 199 132 492 491

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

2) Точность е = 0. 01

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

Опт. значение функции 0,122 304 388 908 469

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

3) Точность е = 0. 001

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

Опт. значение функции 6,237 550 527 5578E-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*x12−2*x22');

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,269 660 220 874 356

3

0. 01

[4,0037; 1,3344]

1,4 801 924 616 0121E-7

3

0. 001

[3,9957; 1,3321]

6,387 997 156 7203E-8

3

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

0. 1

[3,7289; 1,2470]

0,554 697 770 081 615

5

0. 01

[3,9867; 1,3287]

2,1 760 924 199 8115E-7

6

0. 001

[3,9907; 1,3305]

5,7 392 449 263 5677E-7

7

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

0. 1

[4,5855; 1,5198]

0,118 199 132 492 491

2

0. 01

[4,5914; 1,5296]

0,122 304 388 908 469

2

0. 001

[4,0108; 1,3372]

6,237 550 527 5578E-7

5

Розенброк

Точность

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

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

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

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

0. 1

[3,8825; 1,3110]

0,269 660 220 874 298

2

0. 01

[4,0036; 1,3345]

1,4 801 924 616 0075E-7

3

0. 001

[3,9956; 1,3322]

6,387 997 156 7171E-8

3

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

0. 1

[3,7288; 1,2471]

0,554 697 770 081 565

6

0. 01

[3,9866; 1,3288]

2,1 760 924 199 8102E-7

6

0. 001

[3,9906; 1,3306]

5,7 392 449 263 5629E-7

7

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

0. 1

[4,5854; 1,5199]

0,118 199 132 492 464

3

0. 01

[4,5913; 1,5297]

0,122 304 388 908 453

4

0. 001

[4,0107; 1,3373]

6,237 550 527 5548E-7

5

Выводы

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

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

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

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

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

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

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

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

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

ПоказатьСвернуть
Заполнить форму текущей работой