Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

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

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

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

А. Выбрать начальную базисную точку 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-h­1e1), и если ее значение уменьшилось, то b1 заменяем на b1-h1e1. Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка b­1 остается неизменной и рассматриваются изменения в направлении оси х2, т. е. находится значение функции f (b1+h2e2) и т. д. Когда будут рассмотрены все n переменные, мы будем иметь новую базисную точку b2.

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

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

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

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

P1=b1+2(b2-b1) .

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

Pi=bi+2(bi+1-bi) .

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

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

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

 

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

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

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

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

Найти минимум функции

а0=0

а1=1

а2=2
х1з=5

х2з=3,45

 

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

 

real function f(x1,x2)

real x1,x2,a0,a1,a2,x1k,x2k

a0=0

a1=0.256

a2=1

x1k=1.51

x2k=2.3

f=a0+a1**2*(x1-xk)**2+a2**2*(x2-x2k)**2

end

real x1,x2,a0,a1,a2,x1k,x2k

a0=0

a1=0.256

a2=1

x1k=1.51

x2k=2.3

del1=(-1)*(2*a1**2*(x1-1k))/sqrt((2*a1**2

*(x1-1k))**2+(2*a2**2*(x2-x2k))**2)

end

real function del2(x1,x2)

real x1,x2,a0,a1,a2,x1k,x2k

a0=0

a1=0.256

a2=1

x1k=1.51

x2k=2.3

del2=(-1)*(2*a2**2*(x2-x2k))/sqrt((2*a1**2

*(x1-x1k))**2+(2*a2**2*(x2-x2k))**2)

end

 

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). Как можно убедиться на практике, если не принимаются такие меры предосторожности даже программа с удовлетворительной логикой будет неработоспособна.

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

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

при ограничениях x1 2 x1+x2 .

 

 




Поиск по сайту:

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.