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

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

C D

A B

x 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 , но с уменьшенной длиной шага. На практике удовлетворительным является уменьшение шага (шагов) в десять раз от начальной длины

4. Если b 2 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;

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

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

uses crt;

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[1..10] of real;

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

procedure calculate;

begin

z:=3*sqr(x[1])+(4*x[1]*x[2])+(5*sqr(x[2]));

if (x[1]<0) or (x[2]<0) or ((x[1]+x[2])<4) then

z:=1.7e+38;

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

end;

begin

clrscr;

gotoxy(20,2);

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

gotoxy(23,3);

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

writeln;

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

readln(n);

writeln;

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

for i:=1 to n do

readln(x[i]);

writeln;

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

readln(h);

writeln;

k:=h;

fe:=0;

for i:=1 to n do

begin

y[i]:=x[i];

p[i]:=x[i];

b[i]:=x[i];

end;

calculate;

fi:=z;

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

for i:=1 to n do

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

ps:=0;

bs:=1;

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

j:=1;

fb:=fi;

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

calculate;

if z<fi then goto 1;

x[j]:=y[j]-k;

calculate;

if z<fi then goto 1;

x[j]:=y[j];

goto 2;

1: y[j]:=x[j];

2: calculate;

fi:=z;

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

for i:=1 to n do

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

if j=n then goto 3;

j:=j+1;

goto 0;

3: if fi<fb-1e-08 then goto 6;

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

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

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

goto 4;

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

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

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

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

(*** 5: ***)

goto 5;

4: for i:=1 to n do

begin

p[i]:=b[i];

y[i]:=b[i];

x[i]:=b[i];

end;

calculate;

bs:=1;

ps:=0;

fi:=z;

fb:=z;

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

for i:=1 to n do

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

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

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

j:=1;

goto 0;

5: k:=k/10;

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

if k<1e-08 then goto 7;

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

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

j:=1;

goto 0;

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

6: for i:=1 to n do

begin

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

b[i]:=y[i];

x[i]:=p[i];

y[i]:=x[i];

end;

calculate;

fb:=fi;

ps:=1;

bs:=0;

fi:=z;

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

for i:=1 to n do

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

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

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

j:=1;

goto 0;

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

for i:=1 to n do

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

writeln;

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

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

repeat until keypressed;

end

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

Страницы: 1 2

Нужен реферат, сочинение, конспект? Тогда сохрани - » Метод Хука-Дживса . Готовые домашние задания!

Предыдущий реферат из данного раздела: МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

Следующее сочинение из данной рубрики: Существование решения дифференциального уравнения первого порядка

Спасибо что посетили сайт Uznaem-kak.ru! Готовое сочинение на тему:
Метод Хука-Дживса.