.

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

Язык: русский
Формат: реферат
Тип документа: Word Doc
0 928
Скачать документ

Содержание:

1. Введение ………………………………………………… с. 2

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

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

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

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

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

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

Литература ………………………………………………. с. 18

Введение

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

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

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

Разумно двигаться из базисной точки 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) = 3×12+4x1x2+5×22 ,

.

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

Нет

Да

Да Нет

Да

Нет

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

Да

Нет

Нет Да

Да

Нет

Нет

Да

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

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) thenz:=1.7e+38;fe:=fe+1; (*** Счетчик ***)end;beginclrscr;gotoxy(20,2);writeln('Модифицированный метод Хука-Дживса');gotoxy(23,3);writeln('( при наличии ограничений )');writeln;writeln('Введите число переменных:');readln(n);writeln;writeln('Введите начальную точку x1,x2,…,xN');for i:=1 to n doreadln(x[i]);writeln;writeln('Введите длину шага');readln(h);writeln;k:=h;fe:=0;for i:=1 to n dobeginy[i]:=x[i];p[i]:=x[i];b[i]:=x[i];end;calculate;fi:=z;writeln('Начальное значение функции', z:2:3);for i:=1 to n dowriteln(x[i]:2:3);ps:=0;bs:=1;(*** Исследование вокруг базисной точки ***)j:=1;fb:=fi;0: x[j]:=y[j]+k;calculate;if z

Похожие документы
Обсуждение
    Заказать реферат
    UkrReferat.com. Всі права захищені. 2000-2019