Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Реферат: Методы Хука-Дживса

Название: Методы Хука-Дживса
Раздел: Рефераты по математике
Тип: реферат Добавлен 03:53:10 24 марта 2008 Похожие работы
Просмотров: 739 Комментариев: 3 Оценило: 1 человек Средний балл: 2 Оценка: неизвестно     Скачать

Методы Хука-Дживса

Содержание:

1. Введение

2. Метод Хука-Дживса

3. Модифицированный метод Хука-Дживса

4. Блок-схема данного метода

5. Блок-схема единичного исследования

6. Текст программы

7. Распечатка результатов работы программы

8. Литература

Введение

На разработку методов прямого поиска для определения минимума функций и переменных было затрачено много усилий . Методы прямого поиска являются методами, в которых используются только значения функции. Мы рассмотрим подробно лишь один из них. Практика показала, что этот метод эффективен и применим для широкого числа приложений.
Рассмотрим функцию двух переменных. Ее линии постоянного уровня1 на рис. 1,

x2

рис. 1

C D

A B

x1

а минимум лежит в точке (x1 * ,x2 * ). Простейшим методом поиска является метод покоординатного спуска. Из точки А мы производим поиск минимума вдоль направления оси и , таким образом, находим точку В, в которой касательная к линии постоянного уровня параллельна оси . Затем, производя поиск из точки В в направлении оси , получаем точку С, производя поиск параллельно оси , получаем точку D, и т. д. Таким образом, мы приходим к оптимальной точке. Очевидным образом эту идую можно применить для функций n-переменных.

Теоретически данный метод эффективен в случае единственного минимума функции. Но на практике он оказывается слишком медленным. Поэтому были разработаны более сложные методы, использующие больше информации на основании уже полученных значений функции.

Метод Хука-Дживса

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

Описание этой процедуры представлено ниже:

А. Выбрать начальную базисную точку b1 и шаг длиной h1 для каждой переменной xj , j = 1, 2,…, n. В приведенной ниже программе для каждой переменной используется шаг h , однако указанная выше модификация тоже может оказаться полезной.

Б. Вычислить f (х) в базисной точке b1 с целью получения сведений о локальном поведении функции f (x). Эти сведения будут использоваться для нахождения подходящего направления поиска по образцу, с помощью которого можно надеяться достичь большего убывания значения функции. Функция f (x) в базисной точке b1 , находится следующим образом:

1. Вычисляется значение функции f (b1 ) в базисной точке b1 .

2. Каждая переменная по очереди изменяется прибавлением длины шага. Таким образом, мы вычисляем значение функции f (b1 +h1 e1 ), где e1 – единичный вектор в направлении оси x1 . Если это приводит к уменьшению значения функции, то b1 заменяется на b1 +h1 e1 . В противном случае вычисляется значение функции f (b1 -h­1 e1 ), и если ее значение уменьшилось, то b1 заменяем на b1 -h1 e1 . Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка b­1 остается неизменной и рассматриваются изменения в направлении оси х2 , т. е. находится значение функции f (b1 +h2 e2 ) и т. д. Когда будут рассмотрены все n переменные, мы будем иметь новую базисную точку b2 .

3. Если b2 =b1 , т. е. уменьшение функции не было достигнуто, то исследование повторяется вокруг той же базисной точки b1 , но с уменьшенной длиной шага. На практике удовлетворительным является уменьшение шага (шагов) в десять раз от начальной длины.

4. Если b2 b1 , то производится поиск по образцу.

В. При поиске по образцу используется информация, полученная в процессе исследования, и минимизация функции завершается поиском в направлении, заданном образцом. Эта процедура производится следующим образом:

3. Разумно двигаться из базисной точки b2 в направлении b2 -b­1 , поскольку поиск в этом направлении уже привел к уменьшению значения функции. Поэтому вычислим функцию в точке образца

P1 =b1 +2(b2 -b1 ) .

В общем случае

Pi =bi +2(bi+1 -bi ) .

2. Затем исследование следует продолжать вокруг точки Р1i ) .

3. Если наименьшее значение на шаге В, 2 меньше значения в базисной точке b2 (в общем случае bi+1 ), то получают новую базисную точку b3 (bi+2 ), после чего следует повторить шаг В, 1. В противном случае не производить поиск по образцу из точки b2 (bi+1 ), а продолжить исследования в точке b2 (bi+1 ).

Г. Завершить этот процесс, когда длина шага (длины шагов) будет уменьшена до заданного малого значения.

Модифицированный метод Хука-Дживса

Этот метод нетрудно модифицировать и для учета ограничений .Было выдвинуто предложение , что для этого будет вполне достаточно при решении задачи минимизации присвоить целевой функции очень большое значение там,где ограничения нарушаются .К тому же такую идею просто реализовать с помощью програмирования .

Нужно проверить ,каждая ли точка ,полученная в процессе поиска , принадлежит области ограничений .Если каждая , то целевая функция вычисляется обычным путем . Если нет , то целевой функции присваивается очень большое значение . Таким образом , поиск будет осуществляться снова в допустимой области в направлении к минимальной точке внутри этой области.

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

минимизировать f (x1 ,x2 ) = 3x1 2 +4x­1 x2 +5x2 2 ,

при ограничениях x12 x1 +x2 .



Текст программы

program HuDjMody;

(*** Модифицированный метод Хука-Дживса ***)

(*** (при наличии ограничений) ***)

uses crt;

label 0,1,2,3,4,5,6,7;

var k,h,z,ps,bs,fb,fi :real;

i,j,n,fe :integer;

x,y,b,p :array[1..10] of real;

(*** Процедура,вычисляющая функцию ***)

procedure calculate;

begin

z:=3*sqr(x[1])+(4*x[1]*x[2])+(5*sqr(x[2]));

if (x[1]<0) or (x[2]<0) or ((x[1]+x[2])<4) then

z:=1.7e+38;

fe:=fe+1; (*** Счетчик ***)

end;

begin

clrscr;

gotoxy(20,2);

writeln('Модифицированный метод Хука-Дживса');

gotoxy(23,3);

writeln('( при наличии ограничений )');

writeln;

writeln('Введите число переменных:');

readln(n);

writeln;

writeln('Введите начальную точку x1,x2,…,xN');

for i:=1 to n do

readln(x[i]);

writeln;

writeln('Введите длину шага');

readln(h);

writeln;

k:=h;

fe:=0;

for i:=1 to n do

begin

y[i]:=x[i];

p[i]:=x[i];

b[i]:=x[i];

end;

calculate;

fi:=z;

writeln('Начальное значение функции', z:2:3);

for i:=1 to n do

writeln(x[i]:2:3);

ps:=0;

bs:=1;

(*** Исследование вокруг базисной точки ***)

j:=1;

fb:=fi;

0: x[j]:=y[j]+k;

calculate;

if z<fi then goto 1;

x[j]:=y[j]-k;

calculate;

if z<fi then goto 1;

x[j]:=y[j];

goto 2;

1: y[j]:=x[j];

2: calculate;

fi:=z;

writeln('Пробный шаг',' ', z:2:3);

for i:=1 to n do

writeln(x[i]:2:3);

if j=n then goto 3;

j:=j+1;

goto 0;

3: if fi<fb-1e-08 then goto 6;

(*** После оператора 3,если функция не уменьшилась, ***)

(*** произвести поиск по образцу ***)

if (ps=1) and (bs=0) then

goto 4;

(*** Но если исследование производилось вокруг точки ***)

(*** шаблона PT,и уменьшение функции не было достигнуто,***)

(*** то изменить базисную точку в операторе 4: ***)

(*** в противном случае уменьшить длину шага в операторе***)

(*** 5: ***)

goto 5;

4: for i:=1 to n do

begin

p[i]:=b[i];

y[i]:=b[i];

x[i]:=b[i];

end;

calculate;

bs:=1;

ps:=0;

fi:=z;

fb:=z;

writeln('Замена базисной точки',' ',z:2:3);

for i:=1 to n do

writeln(x[i]:1:3);

(*** (следует за последним комментарием) ***)

(*** и провести исследование вокруг новой базисной точки ***)

j:=1;

goto 0;

5: k:=k/10;

writeln('Уменьшить длину шага');

if k<1e-08 then goto 7;

(*** Если поиск незакончен,то произвести новое ***)

(*** исследование вокруг новой базисной точки ***)

j:=1;

goto 0;

(*** Поиск по образцу ***)

6: for i:=1 to n do

begin

p[i]:=2*y[i]-b[i];

b[i]:=y[i];

x[i]:=p[i];

y[i]:=x[i];

end;

calculate;

fb:=fi;

ps:=1;

bs:=0;

fi:=z;

writeln('Поиск по образцу',' ',z:2:3);

for i:=1 to n do

writeln(x[i]:2:3);

(*** После этого произвести исследование вокруг ***)

(*** последней точки образца ***)

j:=1;

goto 0;

7: writeln('Минимум найден');

for i:=1 to n do

writeln('x(',i,')=',p[i]:2:3);

writeln;

writeln('Минимум функции равен',' ',fb:2:3);

writeln('Количество вычислений функции равно',' ',fe);

repeat until keypressed;

end.

Приведенная выше программа реализует описанную процедуру. Одной или двух точек бывает недостаточно для определения начальной точки. Первая точка всегда должна выбираться осмотрительно. ЭВМ работает только с ограниченной точностью, и ошибки могут накапливаться в процессе сложных вычислений, особенно если шаг имеет “неудобную” длину. (Обычно мы будем избегать “неудобной” длины, но программа должна быть работоспособна и в таких ситуациях.) Поэтому в строке , где выясняется вопрос об изменении базисной точки, мы избегаем уменьшения длины шага из-за накапливания ошибки введением длины шага, равной . Мы отслеживаем, где производится исследование – в базисной точке (В5 = 1, Р5 = 0) или в точке образца (В5 = 0, Р5 = 1). Как можно убедиться на практике, если не принимаются такие меры предосторожности даже программа с удовлетворительной логикой будет неработоспособна.

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

Процедура calculate вычисляет значение минимизируемой функции ,в нашем случае : f (x1 ,x2 ) = 3x1 2 +4x­1 x2 +5x2 2 ,

при ограничениях x12 x1 +x2 .

Минимум, равный 44, достигается в точке (3;1) при ограничении x1 +x2 =4.

Для начальной точки (4;3) и при длине шага , равной единице , программой успешно решена задача минимизации .

Ниже приведена распечатка результата работы программы :

Модифицированный метод Хука-Дживса

(при наличииограничений)

Введите число переменных

2

Введите начальную точку х1,х2,…,хN

4

3

Введите длину шага

1

Начальное значение функции 141.000

4.000

3.000

Пробный шаг 108.000

3.000

3.000

Пробный шаг 71.000

3.000

2.000

Поиск по образцу 1.70000000000001566Е+0038

2.000

1.000

Пробный шаг 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

Поиск по образцу 1.70000000000001566Е+0038

3.000

0.000

Пробный шаг 48.000

4.000

0.000

Пробный шаг 48.000

4.000

0.000

Замена базисной точки 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

Уменьшить длину шага

Пробный шаг 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

Уменьшить длину шага

Пробный шаг 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

Уменьшить длину шага

Пробный шаг 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

Уменьшить длину шага

Пробный шаг 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

Уменьшить длину шага

Пробный шаг 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

Уменьшить длину шага

Пробный шаг 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

Уменьшить длину шага

Пробный шаг 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

Уменьшить длину шага

Минимум найден

х(1) = 3.000

х(2) = 1.000

Минимум функции равен 44.000

Количество вычислений равно 74

Для начальной точки (3;4) и длины шага , равной единице , программой также успешно решена задача минимизации .

Для начальной точки (5;6) и длины шага , равной единице , задача не решена , т.к. программа остановилась в точке (1;3) , т.е. на активном ограничении , и выдала неверный результат .

Распечатка результата работы программы приведена ниже :

Модифицированный метод Хука-Дживса

(при наличииограничений)

Введите число переменных

2

Введите начальную точку х1,х2,…,хN

5

6

Введите длину шага

1

Начальное значение функции 375.000

5.000

6.000

Пробный шаг 324.000

4.000

6.000

Пробный шаг 253.000

4.000

5.000

Поиск по образцу 155.000

3.000

4.000

Пробный шаг 124.000

2.000

4.000

Пробный шаг 81.000

2.000

3.000

Поиск по образцу 1.70000000000001566Е+0038

0.000

1.000

Пробный шаг 1.70000000000001566Е+0038

0.000

1.000

Пробный шаг 1.70000000000001566Е+0038

0.000

1.000

Замена базисной точки 81.000

2.000

3.000

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

Поиск по образцу 1.70000000000001566Е+0038

0.000

3.000

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

Замена базисной точки 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

Уменьшить длину шага

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

Уменьшить длину шага

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

Уменьшить длину шага

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

Уменьшить длину шага

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

Уменьшить длину шага

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

Уменьшить длину шага

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

Уменьшить длину шага

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

Уменьшить длину шага

Минимум найден

х(1) = 1.000

х(2) = 3.000

Минимум функции равен 60.000

Количество вычислений равно 89

Аналогичные неутешительные результаты были получены для начальной точки (5;6) и длины шага , равной 0.5 .Неверное решение было найдено в точке (1.5;2.5) . Для начальной точки (4;3) и длины шага , равной 0.5 ,программа работала нормально , но было получено неверное решение в точке (2.5;1.5) .

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

Литература:

1. Б.Банди “Методы оптимизации”

2. Р.Хук , Т.А.Дживс “ Прямой поиск решения для числовых и статических проблем ”, 212-219 с., 1961 .

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений06:45:13 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
16:08:49 24 ноября 2015
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
11:53:47 24 ноября 2015

Работы, похожие на Реферат: Методы Хука-Дживса

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(149958)
Комментарии (1829)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru