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

1. Введение

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

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

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

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

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

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

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

Введение

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

Рассмотрим функцию двух переменных. Ее линии постоянного уровня 1 на рис. 1,

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

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

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

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

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

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

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

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

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

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

b 1 , то производится поиск по образцу.

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

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

P 1 =b 1 +2(b 2 -b 1) .

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

P i =b i +2(b i+1 -b i) .

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

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

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

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

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

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

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

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

при ограничениях x 1

x 2 x 1 +x 2 .

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

program HuDjMody;

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

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

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 of real;

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

procedure calculate;

z:=3*sqr(x)+(4*x*x)+(5*sqr(x));

if (x<0) or (x<0) or ((x+x)<4) then

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

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

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

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

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

for i:=1 to n do

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

for i:=1 to n do

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

for i:=1 to n do

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

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

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

if z

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

for i:=1 to n do

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

if j=n then goto 3;

3: if fi

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

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

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

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

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

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

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

4: for i:=1 to n do

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

for i:=1 to n do

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

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

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

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

if k<1e-08 then goto 7;

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

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

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

6: for i:=1 to n do

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

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

for i:=1 to n do

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

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

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

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

for i:=1 to n do

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

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

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

repeat until keypressed;

. Мы отслеживаем, где производится исследование – в базисной точке (В5 = 1, Р5 = 0) или в точке образца (В5 = 0, Р5 = 1). Как можно убедиться на практике, если не принимаются такие меры предосторожности даже программа с удовлетворительной логикой будет неработоспособна. Hooke - Jeeves ) так же, как и алгоритм Нелдера - Мида , служит для поиска безусловного локального экстремума функции и относится к прямым методам, то есть опирается непосредственно на значения функции. Алгоритм делится на две фазы: исследующий поиск и поиск по образцу (Pattern search).

На начальном этапе задаётся стартовая точка (обозначим её 1) и шаги h i по координатам. Затем замораживаем значения всех координат кроме 1-й, вычисляем значения функции в точках x 0 +h 0 и x 0 -h 0 (где x 0 - первая координата точки, а h 0 - соответственно значение шага по этой координате) и переходим в точку с наименьшим значением функции. В этой точке замораживаем значения всех координат кроме 2-й, вычисляем значения функции в точках x 1 +h 1 и x 1 -h 1 , переходим в точку с наименьшим значением функции и т. д. для всех координат. В случае, если для какой-нибудь координаты значение в исходной точке меньше, чем значения для обоих направлений шага, то шаг по этой координате уменьшается. Когда шаги по всем координатам h i станут меньше соответствующих значений e i , алгоритм завершается, и точка 1 признаётся точкой минимума.

Иллюстрация первого этапа для двух координат:

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

На этапе поиска по образцу откладывается точка 3 в направлении от 1 к 2 на том же расстоянии. Её координаты получаются по формуле x ¯ 3 = x ¯ 1 + λ (x ¯ 2 − x ¯ 1) {\displaystyle {\overline {x}}_{3}={\overline {x}}_{1}+\lambda ({\overline {x}}_{2}-{\overline {x}}_{1})} , где x i - точка с номером i, λ - параметр алгоритма, обычно выбирающийся равным 2. Затем в новой точке 3 проводится исследующий поиск, как на 1 фазе алгоритма, за исключением того, что шаг на этой фазе не уменьшается. Если на этой фазе в результате исследующего поиска удалось получить точку 4, отличную от точки 3, то точку 2 переобозначим на 1, а 4 на 2 и повторим поиск по образцу. В случае если не удаётся найти точку 4, отличную от точки 3, то точку 2 переобозначим на точку 1 и повторим 1-ю фазу алгоритма - исследующий поиск.

Иллюстрация второго этапа для двух координат:

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

Энциклопедичный YouTube

1 / 3
Просмотров:

Введение

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

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

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

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

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

Литература

Введение

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

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

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

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

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

P 1 =b 1 +2(b 2 -b 1) .

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

P i =b i +2(b i+1 -b i) .

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

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

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

минимизировать f

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

program HuDjMody;

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

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

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 of real;

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

procedure calculate;

z:=3*sqr(x)+(4*x*x)+(5*sqr(x));

if (x<0) or (x<0) or ((x+x)<4) then

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

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

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

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

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

for i:=1 to n do

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

for i:=1 to n do

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

for i:=1 to n do

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

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

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

if z

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

for i:=1 to n do

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

if j=n then goto 3;

3: if fi

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

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

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

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

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

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

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

4: for i:=1 to n do

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

for i:=1 to n do

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

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

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

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

if k<1e-08 then goto 7;

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

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

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

6: for i:=1 to n do

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

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

for i:=1 to n do

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

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

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

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

for i:=1 to n do

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

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

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

repeat until keypressed;

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

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

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

при ограничениях x 1 x 2 x 1 +x 2 .

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

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

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

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

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

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

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

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

Пробный шаг 108.000

Пробный шаг 71.000

Пробный шаг 44.000

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

Пробный шаг 48.000

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

Пробный шаг 44.000

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

Пробный шаг 44.000

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

Пробный шаг 44.000

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

Пробный шаг 44.000

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

Пробный шаг 44.000

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

Пробный шаг 44.000

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

Пробный шаг 44.000

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

Пробный шаг 44.000

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

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

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

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

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

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

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

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

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

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

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

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

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

Пробный шаг 324.000

Пробный шаг 253.000

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

Пробный шаг 124.000

Пробный шаг 81.000

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

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

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

Пробный шаг 60.000

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

Пробный шаг 60.000

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

Пробный шаг 60.000

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

Пробный шаг 60.000

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

Пробный шаг 60.000

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

Пробный шаг 60.000

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

Пробный шаг 60.000

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

Пробный шаг 60.000

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

Пробный шаг 60.000

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

Пробный шаг 60.000

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

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

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

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

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

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

Литература:

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

Введение

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

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

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

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

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

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

хук дживс функция минимизирование

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

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

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

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

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

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

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

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

P 1 =b 1 +2(b 2 -b 1).

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

P i =b i +2(b i+1 -b i).

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

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

Назначение сервиса . Онлайн-калькулятор предназначен для нахождения минимума функции методом Хука-Дживса (см. пример). Решение оформляется в формате Word .

Правила ввода функций :

Например, x 1 2 +x 1 x 2 , записываем как x1^2+x1*x2

Метод Хука-Дживса относятся к категории эвристических методов (методам прямого поиска). Методы прямого поиска используют не менее n независимых направлений, где n -размерность вектора.
Элементарным примером метода, реализующего процедуру рекурсивного перебора на множестве направлений поиска, является метод циклического изменения переменных - каждый раз меняется только одна переменная. Затем вдоль каждого из координатных направлений последовательно проводится поиск точки экстремума на основе методов одномерной минимизации. Однако, если линии уровня ЦФ имеют овражный характер, то процедура поиска становится неэффективной и даже может привести к отсутствию сходимости к точке локального extr , если изменение координатных направлений поиска осуществляется в циклическом порядке (показано Пауэллом).

Модифицированный метод Хука-Дживса позволяет существенно ускорить сходимость за счет того обстоятельства, что поиск периодически проводится в направлении d i =x i -x i -1 .
По существу процедура Хука–Дживса представляет собой комбинацию двух поисков:
а) исследующий поиск (для выявления характера локального поведения ЦФ и определения направления движения вдоль "оврагов") с циклическим изменением переменных;
б) ускоряющий поиск по образцу с использованием определенных эвристических правил.

Исследующий поиск. Выбирается некоторая исходная точка x 0 . Задается величина шага ∆ i , которая может быть различной для разных координатных направлений и изменяться в процессе поиска.
Если значение ЦФ в пробной точке меньше значения ЦФ в исходной точке, то шаг поиска успешный. В противном случае из исходной точки делается шаг в противоположном направлении. После перебора всех n координат исследующий поиск завершается. Полученная точка называется базовой.

Поиск по образцу. Осуществляется шаг из полученной базовой точки вдоль прямой, соединяющей эту точку с предыдущей базовой. Новая точка образца определяется по формуле:
x p k +1 =x k +(x k -x k -1).
Как только движение по образцу не приводит к уменьшению ЦФ, точка x p k +1 фиксируется в качестве временной базовой точки и вновь проводится исследующий поиск. Если в результате получается точка с меньшим значением ЦФ, чем в точке x k , то она рассматривается как новая базовая точка x k +1 . Но если исследующий поиск неудачен, то следует вернуться в точку x k и провести исследующий поиск с целью выявления нового направления минимизации. В конечном итоге возникает ситуация, когда такой поиск не приводит к успеху. В этом случае уменьшается шаг путем введения коэффициента α и возобновляется исследующий поиск.
Если исследуемая функция имеет овражный вид, то предпочтительнее использовать метод Хука-Дживса, а не метод Нелдера-Мида, так как в первом методе мы можем регулировать шаг в направлении убывания функции, в то время как во втором методе мы этого сделать не можем.

Схема алгоритма Хука–Дживса

Введем следующие обозначения: x k - текущая базовая точка; x k -1 - предыдущая базовая точка; x p k +1 - точка, построенная при движении по образцу; x k +1 - следующая (новая) базовая точка.
Критерий останова: |∆x|≤ε.
Шаг 1. Определить начальную точку x 0 ; приращения (шаги) ∆ i ; коэффициент уменьшения шага α>1; параметр окончания поиска ε<1.
Шаг 2. Провести исследующий поиск.
Шаг 3. Был ли исследующий поиск удачным (найдена ли точка с меньшим значением ЦФ)?
Да: переход на Шаг 5. Нет: продолжить, т.е. переход на Шаг 4.
Шаг 4. Проверка на окончание поиска. Выполняется ли неравенство |Δx| ≤ ε? Да: окончание поиска, т.е. текущая точка аппроксимирует точку экстремума x * .
Нет: уменьшить приращение ∆ i /α; i=1,2,..,n. Переход на Шаг2.
Шаг 5. Провести поиск по образцу: x p k +1 =x k +(x k -x k -1).
Шаг 6. Провести исследующий поиск, используя точку x p k +1 в качестве временной базовой точки. Пусть в результате получена точка x k +1 .
Шаг 7. Выполняется ли неравенство: f(x k +1) < f(x k)?
Да: положить x k -1 = x k ; x k = x k +1 . Переход на Шаг 5.
Нет: переход на Шаг 4.

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

Энциклопедичный YouTube

Введение

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

Схема алгоритма Хука–Дживса