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

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

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

1.4.1.1 Исследующий поиск

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

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

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

Xp(k+1)=X(k)+(X(k)-X(k-1)). (1.9)

Как только движение по образцу не приводит к уменьшению целевой функции, точка Xp(k+1)фиксируется в качестве временной базовой точки и вновь проводится исследующий поиск. Если в результате получается точка с меньшим значением целевой функции, чем в точке X(k), то она рассматривается как новая базовая точка X(k+1). С другой стороны, если исследующий поиск неудачен, необходимо вернуться в точку X(k) и провести исследующий поиск с целью выявления нового направления минимизации. В конечном счете возникает ситуация, когда такой поиск не приводит к успеху. В этом случае требуется уменьшить величину шага путем введения некоторого множителя и возобновить исследующий поиск. Поиск завершается, когда величина шага становится достаточно малой. Последовательность точек, получаемую в процессе реализации метода, можно записать в следующем виде:

X(k) - текущая базовая точка,

X(k-1)- предыдущая базовая точка,

Xp(k+1)- точка, построенная при движении по образцу,

X(k+1)- следующая (новая) базовая точка.

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

1.4.1.3Описание алгоритма метода

Шаг 1. Выбрать начальную базисную точку b1 и шаг длиной hj для каждой переменной xj, j=1,2,...,n.

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

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

Каждая переменная по очереди изменяется прибавлением длины шага. Таким образом, мы вычисляем значение функции f(b1+h1*e1), где e1-единичный вектор в направлении оси х1.

Если это приводит к уменьшению значения функции, то d1 заменяется на b1+h1*e1. В противном случае вычисляется значение функции f(b1-h1*e1), и если ее значение уменьшилось, то b1 заменяем на b1-h1*e1.

Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка b1 остается неизменной и рассматриваются изменения в направлении оси х2, т.е. находится значение функции f(b1+ h2*e2) и т.д. Когда будут рассмотрены все n-переменныx, мы будем иметь новую базисную точку b2.

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

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

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

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

P1=b1+2*(b2-b1). (1.10)

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

Pi=bi+2*(b(i+1)-bi). (1.11)

Затем исследование следует продолжать вокруг точки P1(Pi).

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

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