Реферат: Метод Хука-Дживса - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

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

Банк рефератов / Информатика, информационные технологии

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Microsoft Word, 229 kb, скачать бесплатно
Обойти Антиплагиат
Повысьте уникальность файла до 80-100% здесь.
Промокод referatbank - cкидка 20%!

Узнайте стоимость написания уникальной работы

11



Введение

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

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

Целю данной работы, является освещения концепций метода Хука-Дживса.

Основными задачами, подлежащими рассмотрению в связи с поставленной целью являются:

  • объяснить в чем состоит суть метода Хука-Дживса;

  • показать его отличие от других методов данного типа;

  • рассмотреть алгоритм работы метода;

  • пояснить этапы выполнения метода;

  • уточнить в чем состоит модификация данного метода;

  • наглядно продемонстрировать работу метода с помощью блок-схем.

Актуальность данной работы заключается в конкретизации и резюмированию знаний об этом методе.


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

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



x2


C D


A B

x1


рис. 1


а минимум лежит в точке (x1*,x2*)1. Простейшим методом поиска является метод покоординатного спуска. Из точки А мы производим поиск минимума вдоль направления оси и, таким образом, находим точку В, в которой касательная к линии постоянного уровня параллельна оси. Затем, производя поиск из точки В направлении оси, получаем точку С, производя поиск параллельно оси, получаем точку 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+h1e1), где e1 – единичный вектор в направлении оси x1. Если это приводит к уменьшению значения функции, то b1 заменяется на b1+h1e1. В противном случае вычисляется значение функции f (b1-h­1e1), и если ее значение уменьшилось, то b1 заменяем на b1-h1e1. Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка b­1 остается неизменной и рассматриваются изменения в направлении оси х2, т. е. находится значение функции f (b1+h2e2) и т. д. Когда будут рассмотрены все n переменные, мы будем иметь новую базисную точку b2.

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

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

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

1. Разумно двигаться из базисной точки 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).

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


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


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

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

Далее представлены две блок-схемы метода Хука-Дживса.

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

В блок-схеме №2 приведен алгоритм единичного исследования, результатом которого пользуются в блок-схеме №1. Производится пошаговое уточнение значения функции с контролем попадания этого значения в область определения функции.

Блок-схемы представлены ниже.



Блок-схема №1 - Метод Хука-Дживса













Нет





Да



Да Нет














Да


Нет



Блок-схема №2 - Единичное исследование











Да



Нет



Нет Да

Да

Нет








Нет



Да










Заключение


В данной работы были освещены концепции метода Хука-Дживса.

Конкретно, было выполнено следующее:

- объяснено в чем состоит суть метода Хука-Дживса;

- показано его отличие от других методов данного типа;

- рассмотрен алгоритм работы метода;

- были пояснены этапы его выполнения;

- уточнено в чем состоит модификация данного метода;

- наглядно продемонстрирована работа метода с помощью блок-схем.

Основываясь на данной работе и на материалах использованных для ее написания, можно сделать следующие выводы:

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

- метод Хука-Дживса использует информацию на основании уже полученных значений функции, это экономит время работы;

- метод Хука-Дживса нетрудно модифицировать для учета ограничений;

- метод Хука-Дживса прост в реализации с помощью программирования.


Список литературы


  1. Б.Банди. Методы оптимизации. - М., 1998 г.

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




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

1 Б.Банди Методы оптимизации. - М., 1998 г.




1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Женщины не любят логику, потому что с ней труднее объяснить мужу необходимость десятой пары туфель.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по информатике и информационным технологиям "Метод Хука-Дживса", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

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


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2017
Рейтинг@Mail.ru