Методы Хука-Дживса - (реферат)
Методы Хука-Дживса - (реферат)
Дата добавления: март 2006г.
Методы Хука-Дживса
Содержание:
Введение
Метод Хука-Дживса
Модифицированный метод Хука-Дживса
Блок-схема данного метода
Блок-схема единичного исследования
Текст программы
Распечатка результатов работы программы
Литература
Введение
На разработку методов прямого поиска для определения минимума функций и переменных было затрачено много усилий . Методы прямого поиска являются методами, в которых используются только значения функции. Мы рассмотрим подробно лишь один из них. Практика показала, что этот метод эффективен и применим для широкого числа приложений. Рассмотрим функцию двух переменных. Ее линии постоянного уровня1 на рис. 1,
x2
рис. 1
C D
A B
x1
а минимум лежит в точке (x1*, x2*). Простейшим методом поиска является метод покоординатного спуска. Из точки А мы производим поиск минимума вдоль направления оси и , таким образом, находим точку В, в которой касательная к линии постоянного уровня параллельна оси . Затем, производя поиск из точки В в направлении оси , получаем точку С, производя поиск параллельно оси , получаем точку 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-h1e1), и если ее значение уменьшилось, то b1 заменяем на b1-h1e1. Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка b1 остается неизменной и рассматриваются изменения в направлении оси х2, т. е. находится значение функции f (b1+h2e2) и т. д. Когда будут рассмотрены все n переменные, мы будем иметь новую базисную точку b2.
3. Если b2=b1, т. е. уменьшение функции не было достигнуто, то исследование повторяется вокруг той же базисной точки b1, но с уменьшенной длиной шага. На практике удовлетворительным является уменьшение шага (шагов) в десять раз от начальной длины.
4. Если b2b1, то производится поиск по образцу.
В. При поиске по образцу используется информация, полученная в процессе исследования, и минимизация функции завершается поиском в направлении, заданном образцом. Эта процедура производится следующим образом:
Разумно двигаться из базисной точки b2 в направлении b2-b1, поскольку поиск в этом направлении уже привел к уменьшению значения функции. Поэтому вычислим функцию в точке образца
P1=b1+2(b2-b1) .
В общем случае
Pi=bi+2(bi+1-bi) .
2. Затем исследование следует продолжать вокруг точки Р1 (Рi) .
3. Если наименьшее значение на шаге В, 2 меньше значения в базисной точке b2 (в общем случае bi+1), то получают новую базисную точку b3 (bi+2), после чего следует повторить шаг В, 1. В противном случае не производить поиск по образцу из точки b2 (bi+1), а продолжить исследования в точке b2 (bi+1). Г. Завершить этот процесс, когда длина шага (длины шагов) будет уменьшена до заданного малого значения.
Модифицированный метод Хука-Дживса
Этот метод нетрудно модифицировать и для учета ограничений . Было выдвинуто предложение , что для этого будет вполне достаточно при решении задачи минимизации присвоить целевой функции очень большое значение там, где ограничения нарушаются . К тому же такую идею просто реализовать с помощью програмирования .
Нужно проверить , каждая ли точка , полученная в процессе поиска , принадлежит области ограничений . Если каждая , то целевая функция вычисляется обычным путем . Если нет , то целевой функции присваивается очень большое значение . Таким образом , поиск будет осуществляться снова в допустимой области в направлении к минимальной точке внутри этой области.
В тексте прогаммы модифицированного метода прямого поиска Хука-Дживса сделана попытка реализовать такую процедуру. Рассматриваемая задача формулируется следующим образом :
минимизировать f (x1, x2) = 3x12+4x1x2+5x22 , при ограничениях x1 x2 x1+x2.
Текст программы
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] 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 x[j]: =y[j]-k;
calculate;
if z 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 (*** После оператора 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);
Страницы: 1, 2
