Вход

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

Реферат по информатике и информационным технологиям
Дата добавления: 13 февраля 2010
Язык реферата: Русский
Word, rtf, 229 кб
Реферат можно скачать бесплатно
Скачать
Данная работа не подходит - план Б:
Создаете заказ
Выбираете исполнителя
Готовый результат
Исполнители предлагают свои условия
Автор работает
Заказать
Не подходит данная работа?
Вы можете заказать написание любой учебной работы на любую тему.
Заказать новую работу

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 г.




© Рефератбанк, 2002 - 2018