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

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

Содержание:

1. Введение

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

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

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

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

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

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

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

Введение

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

x₂

рис. 1

C D

A B

x₁

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

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

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

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

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

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

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

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

2. Каждая переменная по очереди изменяется прибавлением длины шага. Таким образом, мы вычисляем значение функции f (b₁ +h₁ e₁ ), где e₁ – единичный вектор в направлении оси x₁ . Если это приводит к уменьшению значения функции, то b₁ заменяется на b₁ +h₁ e₁ . В противном случае вычисляется значение функции f (b₁ -h­₁ e₁ ), и если ее значение уменьшилось, то b₁ заменяем на b₁ -h₁ e₁ . Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка b­₁ остается неизменной и рассматриваются изменения в направлении оси х₂ , т. е. находится значение функции f (b₁ +h₂ e₂ ) и т. д. Когда будут рассмотрены все n переменные, мы будем иметь новую базисную точку b₂ .

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

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

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

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

P₁ =b₁ +2(b₂ -b₁ ) .

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

P_i =b_i +2(b_i+1 -b_i ) .

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

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