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

Метод Хука-Дживса был разработан в 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 , то производится поиск по образцу

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

Разумно двигаться из базисной точки 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 ,

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

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

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

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: ***)
(*** в противном случае уменьшить длину шага в операторе***)
(*** 5: ***)

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

4.000
3.000

Пробный шаг 108.000

3.000
3.000

Пробный шаг 71.000

3.000
2.000

2.000
1.000

Пробный шаг 44.000

3.000
1.000

Пробный шаг 44.000

3.000
1.000

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

3.000
0.000

Пробный шаг 48.000

4.000
0.000

Пробный шаг 48.000

4.000
0.000

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

3.000
1.000

Пробный шаг 44.000

3.000
1.000

Пробный шаг 44.000

3.000
1.000

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

Пробный шаг 44.000

3.000
1.000

Пробный шаг 44.000

3.000
1.000

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

Пробный шаг 44.000

3.000
1.000

Пробный шаг 44.000

3.000
1.000

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

Пробный шаг 44.000

3.000
1.000

Пробный шаг 44.000

3.000
1.000

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

Пробный шаг 44.000

3.000
1.000

Пробный шаг 44.000

3.000
1.000

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

Пробный шаг 44.000

3.000
1.000

Пробный шаг 44.000

3.000
1.000

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

Пробный шаг 44.000

3.000
1.000

Пробный шаг 44.000

3.000
1.000

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

Пробный шаг 44.000

3.000
1.000

Пробный шаг 44.000

3.000
1.000

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

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

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

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

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

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

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

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

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

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

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

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

5.000
6.000

Пробный шаг 324.000

4.000
6.000

Пробный шаг 253.000

4.000
5.000

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

3.000
4.000

Пробный шаг 124.000

2.000
4.000

Пробный шаг 81.000

2.000
3.000

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

0.000
1.000

0.000
1.000

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

0.000
1.000

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

2.000
3.000

Пробный шаг 60.000

1.000
3.000

Пробный шаг 60.000

1.000
3.000

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

0.000
3.000

Пробный шаг 60.000

1.000
3.000

Пробный шаг 60.000

1.000
3.000

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

1.000
3.000

Пробный шаг 60.000

1.000
3.000

Пробный шаг 60.000

1.000
3.000

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

Пробный шаг 60.000

1.000
3.000

Пробный шаг 60.000

1.000
3.000

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

Пробный шаг 60.000

1.000
3.000

Пробный шаг 60.000

1.000
3.000

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

Пробный шаг 60.000

1.000
3.000

Пробный шаг 60.000

1.000
3.000

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

Пробный шаг 60.000

1.000
3.000

Пробный шаг 60.000

1.000
3.000

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

Пробный шаг 60.000

1.000
3.000

Пробный шаг 60.000

1.000
3.000

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

Пробный шаг 60.000

1.000
3.000

Пробный шаг 60.000

1.000
3.000

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

Пробный шаг 60.000

1.000
3.000

Пробный шаг 60.000

1.000
3.000

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

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

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

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

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

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

Введение

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

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

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

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

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

Литература

Введение

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

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

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

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

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

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 , то производится поиск по образцу.

Разумно двигаться из базисной точки 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

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

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 .

Министерство образования и науки РФ Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования "Сибирский государственный индустриальный университет"

Кафедра информационных технологий в металлургии.

Курсовая работа

по дисциплине: «Оптимизация в технике и технологиях»

Многомерная оптимизация методом Хука-Дживса

Выполнил:

ст. гр. ИС-10

Хлыстов Д.С.

Проверил:

к.т.н., доцент

Рыбенко И.А.

Новокузнецк2013

1.Теор е тические основ ы метода оптимизации

1.1. Постановка задачи
1.2 Математические основы метода

1.2.1 Метод Хука--Дживса
1.2.2 Метод квадратичной аппроксимации

1.3 Разработка алгоритма численной реализации

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

1.4 Составление и реализация контрольных примеров средствами Excel

2. Программная реализация системы на ЭВМ средствами Delphi

2.1 Описание структуры программы и ее компонентов
2.2 Результаты отладки программы на контрольных примерах
2.3 Составление инструкции по использованию программы

3.2 Исследование влияния параметров задачи (начальное приближение, точность, параметры алгоритма) на количество
расчетов целевой функции
3.3 Исследование работоспособности метода путем решения задач различной размерности и сложности

Заключение
Список литературы
Приложение 1

1.Теоритические основ метода оптимизации.

1.1 Постановка задачи

Многомерная оптимизация заключается в нахождении для функции n действительных переменных

f (x 1 , x 2 , x 3 , …, x n ) = f (X ), x E n

компонентов вектора X * , которые дают условие

f (X *) = min(max)f (X ).

Рассматривая локальный X 0 и глобальный X * экстремумы функции можно отметить их особенности. Функция f (X ) имеет локальный минимум в точке X 0 , если существует окрестность, такая, что f (X ) больше f (X 0) во всех точках этой окрестности. В случае глобального минимума в точке X * для всех X справедливо неравенство

f (X ) f (X *).

Для решения поставленной задачи я использовал алгоритмы безусловной оптимизации методами:

Для многомерной Хука--Дживса.

Для одномерной квадратичной аппроксимации.

1.2 Математические основы метода

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

Метод включает два этапа: “исследующий поиск” вокруг базисной точки и “поиск по образцу” в направлении, выбранном для минимизации. В исследующем поиске задается начальное приближение X (1) и приращения по координатам X . Рассчитывается значение f (X (1)) в базисной точке. Затем в циклическом порядке совершаются пробные шаги. Если приращение улучшает целевую функцию, то шаг считается “удачным”. По этой переменной значение изменяется на величину шага и дается приращение по другой переменной Иначе - “неудачным” и делается шаг в противоположном направлении. И если он тоже оказался “неудачным”, то значение этой переменной оставляют без изменения, и дается приращение по другой переменой и т.д. пока не будут изменены все независимые переменные. На этом завершается первый исследующий поиск, найдена точка X (2) . Поиск по образцу осуществляется вдоль направления, соединяющего X (2) иX (1) . Совершается один или несколько шагов до тех пор, пока шаги являются “удачными”.

Применяют две модификации метода прямого поиска:

в исследующем поиске используется одномерная минимизация вдоль координатных направлений;

исследующий поиск осуществляется на основе дискретных шагов по направлениям.

1.2.2 Метод квадратичной аппроксимации.

Метод основан на предположении о том, что в ограниченном интервале можно аппроксимировать функцию квадратичным полиномом, который используется для оценивания координаты оптимума. Оценка оптимального значения рассчитывается по формуле:

= (x 2 + x 1)/2 - (a 1 /2a 2).

Предполагается, что заданы x 1 , x 2 , x 3 , и известны значения функции в этих точках f 1 , f 2 , f 3 , а аппроксимирующая функция

g (x ) = a 0 + a 1 (x - x 1) + a 2 (x - x 1)(x - x 2)

совпадает с f (x ) в трех указанных точках.

Коэффициенты полинома определяются уравнениями

a 0 = f 1 ; a 1 = (f 2 - f 1)/(x 2 - x 1); a 2 = 1/(x 3 - x 2)[(f 3 - f 1)/(x 3 - x 1) - (f 2 - f 1)(x 2 - x 1)].

Для унимодальных функций оказывается приемлемой для оценки оптимума x * .

1.3 Разработка алгоритма численной реализации

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

Начальный этап . Выбрать начальную точку X (1) , и 0 - скаляр, используемый в критерии остановки. Пусть единичные координатные направления, б - коэффициент сжатия шага. Положить Y (1) = X (1) , k = j = 1 и перейти к основному этапу.

Основной этап.Шаг 1 . Любым методом одномерной оптимизации найти j * - оптимальное решение задачи минимизации функции f (Y (j ) + j ) при условии и положить Y (j+1 ) = Y (j ) + j * . Если j n , то заменить j на j + 1 и вернуться к шагу 1. Если j=n , то перейти к шагу 2.

Шаг 2 . Положить X (k+ 1) = Y (n ) . Если ||X (k+ 1) - X (k ) || , то остановиться; в противном случае вычислить шаг а=||X (k+ 1) - X (k ) || ?б, Y (1) = X (k ) , заменить k на k + 1, положить j = 1 и перейти к шагу 3.

Шаг 3. Вычислить Y (j+1) = Y (j ) +a и f(Y (j) ) , f(Y (j+1) ) . Если f(Y (j+1) ) <f(Y (j) ) , то j=j +1 и вернуться к шагу 3. Иначе положить X (k ) =Y (j ) ,j= 1, Y (1) = X (k) , и вернуться к шагу 1.

1.3.2 Метод квадратичной аппроксимации

Шаг 1 . Задать x 1 , x 2 , x 3 , и вычислить значения функции в этих точках f(х 1), f(х 2), f(х 3).

Шаг 2 . Рассчитать a 0 = f(х 1); a 1 = (f(х 2) - f(х 1))/(x 2 - x 1); a 2 = 1/(x 3 - x 2)[(f(х 3) - f(х 1))/(x 3 - x 1) - (f(х 2) - f(х 1))(x 2 - x 1)].

Шаг 2 . Вычислить оптимальное решение: = (x 2 + x 1)/2 - (a 1 /2a 2).

1 .4 Составление и реализация контрольных примеров средствами Excel

Рассмотрим функцию f(x)=(х1+х2)^2+(х2-1)^2 с точностью e=0,01 и начальными значениями х1=5 , х2=6 . Результаты расчетов приведены в таблице 1.

Таблица 1 -- Расчет экстремума функции f(x)=(х1+х2)^2+(х2-1)^2 методом Хука--Дживса.




По образцу
							Критерий
							Не достигнут













По образцу
							Критерий
							Не достигнут






















По образцу
							Критерий
							Не достигнут















По образцу
							Критерий
							Не достигнут














По образцу
							Критерий
							Не достигнут
























По образцу
							Критерий
							Достигнут

Таким образом экстремум в точке [-1;1] найден за шесть итерации с точностью e =0,01 .

1.5 Анализ результатов расчета

При подсчете функции f(x)=(х1+х2)^2+(х2-1)^2 с точностью e =0,01 , был найден экстремум в точке [-1;1]за 6 итераций.

Достоинства метода:

Простая стратегия поиска, вычисление только значений функции, небольшой объём требуемой памяти.

Недостатки:

Алгоритм основан на циклическом движении по координатам. Это может привести к вырождению алгоритма в бесконечную последовательность исследующих поисков без поиска по образцу.

2. Программная реализация системы на ЭВМ средствами Delphi

2.1 Описание структуры программы и ее компонентов

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

Поле для ввода начальных координат

Поле для ввода точности поиска

Выбор функции.

Поле для вывода всех шагов и итераций.

Поля для вывода экстремума в точках.

Вывод конечного числа итераций.

Программа реализованная в среде Delphiи имеет следующий вид (рис.1).

Рисунок 1 -- интерфейс программы Хука--Дживса

Ознакомится с листингом программы на примере одной функции можно в приложении 1.

2.2 Результаты отладки программы на контрольных примерах

В программной реализации использовались функции различной сложности:

f(x) = (x 1 +x 2 ) 2 +(x 2 -1) 2

f(x)= (x 1 +x 2 ) 2 +(x 2 +4) 2

f(x)= (x 1 -3x 2 ) 2 +(x 2 +1) 2

f(x)= (x 1 -6x 2 ) 2 +(x 2 +1) 2

f(x)= (x 1 -2x 2 ) 2 +(x 2 -3) 2

f(x)= (x 1 +2x 2 ) 2 +(x 2 -4) 2

Мною была выбрана функция для отладки программы f(x) = (x 1 +x 2 ) 2 +(x 2 -1) 2 , с начальным интервалом и точность поиска равную e=0,01 .

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

2.3 Составление инструкции по использованию программы

1) Запустить программу - после открытия программы перед вами появится окно интерфейса программы (Рис.2).

Рисунок 2-- Интерфейс программы.

2) Вводим точность и начальныезначения интервала (Рис.3)

Рисунок 3--Поля для ввода точности и начального значения интервала.

оптимизация программа хук дживс

3) Выбираем функцию и нажимаем кнопку «Рассчитать» (Рис.4).

Рисунок 4-- Окно для выбора функций.

Рисунок 5--Поля вывода.

Рисунок 6 -- Подробные расчеты выбранной функции.

3. Исследование эффективности работы метода оптимизации на тестовых задачах

3.1 Выбор и описание тестовых задач

Для тестов выбралфункцию f(x)= (x 1 -6x 2 ) 2 +(x 2 +1) 2 с начальными координатами[-5; -3] и точность e=0,015

Сначала делаем исследующий поиск с помощью квадратичной аппроксимации f(x)= (x 1 -6x 2 ) 2 +(x 2 +1) 2 при х1=-5,х2=-3 и получаем х`1=-18. После для х1=-18 и х2=-3 и получаем х`2=-2,945. Вычисляем S1=-13и S2=0,054,а также h1=-1,2 и h2=0,0054.

Далее переходим к поиску по образцу. Первое действие подставляем в функцию f(x)= (x 1 -6x 2 ) 2 +(x 2 +1) 2 наши значения х1=-5,х2=-3 получая f(x)=173. Второе действие меняем х1=х1+h1 а х2=x2+h2 и снова считаем значение функции получая f(x)=140,11. Повторяем второе действие пока функция убывает, как только она начинает возрастать прекращаем поиск по образцу. Мне потребовалось 12 итераций на 11 итерации значения былих1=-18, х2=-2,94595,f(x)=3,891891892 на 12 итерации стали такими былих1=-19,3, х2=-2,94054,f(x)=6,510540541.

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

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

3.2 Исследование влияния параметров задачи (начальное приближение, точность, параметры алгоритма) на количество расчетов целевой функции

Проведя исследования заданных мной функций выяснилось:

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

2. Для некоторых функций точность влияет на количество итераций.

3.3 Исследование работоспособности метода путем решения задач различной размерности и сложности.

Алгоритм Хука--Дживса показал себя как быстро работающий. Если e=<0,9 то количество итерация не возрастает, но если точность будет больше e>0,9 то количество итераций уменьшится.

При исследовании сложных функций было выявленочто не у всех функций можно найти точный экстремум.

3.4 Обработка результатов исследований визуальными и формальными средствами Excel

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

Рассмотрим первую функциюf(x)= (x 1 -6x 2 ) 2 +(x 2 +1) 2 при х1=-5,х2=-3 получаем таблицу 2, а также график 1.

Таблица 2--зависимость итераций от точности и начального приближения

		точность	итерации

График 1--зависимость итераций и начального приближения

Поменяем начальное приближение,но точность оставим прежней e=0.015, так как при изменении точности количество итераций в данной функции не меняется, и тогда получим таблицу 3 и график 2.

Таблица 2 -- зависимость итерации от начального приближения

		итерации

График 2 -- зависимость итерации от начального приближения

Заключение

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

Список литературы.

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

2. Алгоритмы и примеры решения задач одномерной оптимизации: Метод.указ./ Сост.: С.П Мочалов, И.А. Рыбенко.: СибГИУ.- Новокузнецк, 2004.- 18с., ил.

3. Мочалов С.П. Методы оптимизации металлургических процессов: Учебное пособие / КузПИ. -Кемерово, 1989.- 81с.

Приложение 1

Var //описание глобальных переменных

iteration:integer;

functionRB1ExplSearch(x1,x2:double;check:integer):Double; //Функция для расчета метода квадратичной аппроксимации она же исследующий поиск

f1,f2,f3:double;

a0,a1,a2:double;

tx1,tx2,tx3:double;

ifcheck=1 then //для расчета первого х

f1:=sqr(tx1+x2)+sqr(x2-1);

f2:=sqr(tx2+x2)+sqr(x2-1);

f3:=sqr(tx3+x2)+sqr(x2-1);

a1:=(f2-f1)/(tx2-tx1);

xopt:=(tx2+tx1)/2-a1/2/a2;

ifcheck=2 then //для расчета второго х

f1:=sqr(tx1+x1)+sqr(tx1-1);

f2:=sqr(tx2+x1)+sqr(tx2-1);

f3:=sqr(tx3+x1)+sqr(tx3-1);

a1:=(f2-f1)/(tx2-tx1);

a2:=1/(tx3-tx2)*((f3-f1)/(tx3-tx1)-(f2-f1)/(tx2-tx1));

xopt:=(tx2+tx1)/2-a1/2/a2;

procedure TForm1.RezClick(Sender: TObject); //основная процедура

x1opt,x2opt:double;

error:single; //погрешность

ListBox1.Items.Clear;

EXopt1.Text:="";

EXopt2.Text:="";

EIteration.Text:="";

x1:=StrToFloat(Ex1.text);

x2:=StrToFloat(Ex2.text);

error:=strtofloat(Eerror.Text);

ifRB1.Checkedthen //проверка на выбор функции и запуск метода Хука--Дживса

x1opt:=RB1ExplSearch(x1,x2,1); //Передача значений в функцию квадратичной аппроксимации для первого х

x2opt:=RB1ExplSearch(x1opt,x2,2); // Передача значений в функцию квадратичной аппроксимации для второго х

ListBox1.Items.Add("Исследующий поиск");

ListBox1.Items.Add("x1 = "+FloatToStr(x1opt)+" x2 = "+FloatToStr(x2opt));

h1:=(x1opt-x1)*0.1;

h2:=(x2opt-x2)*0.1;

F:=sqr(x1+x2)+sqr(x2-1);

whiledF

F:=sqr(x1+x2)+sqr(x2-1);

ListBox1.Items.Add("Поискпообразцу");

ListBox1.Items.Add("x1 = "+FloatToStr(x1)+" x2 = "+FloatToStr(x2));

dF:=sqr(x1+x2)+sqr(x2-1);

test:=sqrt(sqr(x1-sx1)+sqr(x2-sx2)); // расчет критерий для окончание поиска

iteration:=iteration+1; //подсчет количества итераций

untiltest<=error //проверка критерий с заданной точность

raiseException.Create("Выбиритефункцию");

ListBox1.Items.Add("");

ListBox1.Items.Add("Количество итераций "+inttostr(iteration));

EIteration.Text:=IntToStr(iteration); //вывод результатов итерации

EXopt1.Text:=FloatToStr(x1); //вывод результатов для х первого

EXopt2.Text:=FloatToStr(x2); //вывод результатов для ч второго

EFunc.Text:=FloatToStr(F); //вывод результатов для функции в точках х1 х2

Except //блок обработки ошибок

onEConvertError do

ShowMessage("х1 должен быть числом или вместо точки должна быть запятая");

ShowMessage("х2 должен быть числом или вместо точки должна быть запятая");

Eerror.SetFocus;

ShowMessage("Точность должна быть числом или вместо точки должна быть запятая");

Подобные документы

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

лабораторная работа , добавлен 14.07.2012

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

курсовая работа , добавлен 20.05.2012

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

контрольная работа , добавлен 02.02.2014

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

курсовая работа , добавлен 04.03.2013

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

курсовая работа , добавлен 16.09.2012

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

курсовая работа , добавлен 25.04.2015

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

лабораторная работа , добавлен 16.12.2014

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

курсовая работа , добавлен 14.07.2012

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

курсовая работа , добавлен 25.09.2013

Описание и функциональное назначение программы по оптимизации функции, ее логическая структура и используемые технические средства. Практическое применение программы, вызов и загрузка, входные и выходные данные, выполнение контрольного примера и листинг.

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

Содержание:

Введение

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

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

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

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

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

Литература

Введение

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

(x 1 * ,x 2 * )

x 2

Рис. 1

C D

A B

x 1

а минимум лежит в точке (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 .

4. Если 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 of real;

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

procedure calculate;

begin

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

if (x<0) or (x<0) or ((x+x)<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

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);

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

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

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 (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

4.000

3.000

Пробный шаг 108.000

3.000

Пробный шаг 71.000

3.000

2.000

1.000

Пробный шаг 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

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

3.000

0.000

Пробный шаг 48.000

4.000

0.000

Пробный шаг 48.000

4.000

0.000

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

3.000

1.000

Пробный шаг 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

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

Пробный шаг 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

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

Пробный шаг 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

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

Пробный шаг 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

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

Пробный шаг 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

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

Пробный шаг 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

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

Пробный шаг 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

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

Пробный шаг 44.000

3.000

1.000

Пробный шаг 44.000

3.000

1.000

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

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

х(1) = 3.000

х(2) = 1.000

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

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

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

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

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

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

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

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

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

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

5.000

6.000

Пробный шаг 324.000

4.000

6.000

Пробный шаг 253.000

4.000

5.000

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

3.000

4.000

Пробный шаг 124.000

2.000

4.000

Пробный шаг 81.000

2.000

3.000

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

0.000

1.000

0.000

1.000

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

0.000

1.000

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

2.000

3.000

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

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

0.000

3.000

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

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

1.000

3.000

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

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

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

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

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

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

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

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

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

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

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

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

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

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

Пробный шаг 60.000

1.000

3.000

Пробный шаг 60.000

1.000

3.000

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

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

х(1) = 1.000

х(2) = 3.000

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

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

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

Литература:

Б.Банди “Методы оптимизации”

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

1) Методы Розенброка и Дэвиса, Свенна, Кемпи более подробно изложены в книге Химмельблау , переведенной на русский язык,- Прим. Перев

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

3.2.3. Метод сопряженных направлений Пауэлла

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

Задачи с квадратичными целевыми функциями занимают важное место в теории оптимизации по двум причинам.

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

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

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

Процедура преобразования квадратичной функции

q (x ) = a + bx + ½ xC x (3.25)

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

Q (x ) = xC x (3.26)

путем преобразования

x = T z (3.27)

приводится к виду

Q (x ) = zTC T z = zD z (3.28)

где D - диагональная матрица, т. е. элементы D отличны от нуля только при i = j

f(x) = 4x+ 3x- 4xx+ x

Рис. 3.8. Линии уровня квадратичной функции с перекрёстными членами.

Пусть t - j -й столбец матрицы Т . Тогда преобразование (3.27) позволяет записать каждый вектор х в виде линейной комбинации вектор-столбцов t.

x = T z = t z + tz+…+ tz . (3.29)

Другими словами, вместо координат вектора х в стандартной координатной системе, определяемой множеством векторов e ( i ) , используются координаты вектора в новой координатной системе, заданной векторами t. Кроме того, система векторов t соответствует главным осям рассматриваемой квадратичной формы, поскольку матрица квадратичной формы приводится к диагональному виду. Такая ситуация возникает, если квадратичную функцию с перекрестными членами, линии уровня которой изображены на рис. 3.8, записать в новой координатной системе, оси которой совпадают с большой и малой осями квадратичной функции (см. рис. 3.9).

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

f(x) = 4x+ 2x+ x+x

Рис. 3.9. Линии уровня квадратичной функции без перекрёстных членов

Пример 3.4. Преобразование к виду суммы квадратов

Рассмотрим функцию

f (x ) = 4 x+ 3x– 4xx+ x

и преобразование

x = z + ½ z, x= z,

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

f (z )= 4 z+ 2 z+ z + ½ z.

Заметим, что это преобразование не является единственным, поскольку система векторов t не удовлетворяет условию ортонормированности. В частности, нетрудно проверить, что преобразование

также приводит матрицу квадратичной формы к диагональному, виду. Задавая начальную точку x = и два столбца матрицы преобразования

t = , t = [½, 1],

можно найти точку оптимума [– ,– ] T в результате проведения двух последовательных поисков в направлениях t и t Поиск в направлении t по формуле

x= x+ λt

позволяет получить значение λ = – и точку х (1) = [– , 0]. Далее из точки х (1) проводится поиск в направлении t 2 . Получаем значение λ = – и решение х (2) = [– ,– ] T .

Из рассмотренного примера и предыдущего изложения следует, что если система векторов t, j = 1,...,N , или система сопряженных направлений, построена, то точку оптимума квадратичной функции можно найти в результате реализации в точности N одномерных поисков, которые проводятся вдоль каждого из N направлений t, j = 1,...,N . Таким образом, нерешенными остаются лишь вопросы, связанные с построением системы векторов t. Если матрица С известна, то матрицу преобразования Т можно найти с помощью метода Гаусса - Жордана (как это выполнено в приложении А). Метод Гаусса - Жордана позволяет представить матрицу С в виде произведения

C = P T DP , откуда (3.30)

(P )C (P ) = D и T = P (3.31)

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

Свойство параллельного подпространства

Пусть заданы квадратичная функция q (x ), две произвольные несовпадающие точки x (1) и х (2) , а также направление d . Если точка y (1) минимизирует q (x (1) +λ d ), a точка y (2) минимизирует q (x (1) + λ d ), то направление (y (2) - y (1)) сопряжено с d .

Рис. 3.10 иллюстрирует сформулированное свойство для случая двух переменных. Нетрудно видеть, что поиск, проводимый из точки y (1) или y (2) в направлении (y (2) - y (1)), обеспечивает получение точки минимума. Таким образом, в случае двух переменных реализация трех одномерных поисков позволяет построить систему сопряженных направлений и, кроме того, найти точку оптимума квадратичной функции. Прежде чем продолжать алгоритмические построения, докажем теорему о свойстве параллельного подпространства.

Рис. 3.10. Сопряженные направления на плоскости.

Напомним, что по определению С -сопряженные направления задаются системой вектор-столбцов матрицы Т , которая приводит матрицу С к диагональному виду:

ТC Т = D (3.32)

Поскольку все внедиагональные элементыD равны нулю, отсюда следует, что

(3.33)

где t - i -й столбец матрицы Т. Таким образом, мы получили возможность дать более удобное, эквивалентное и, по-видимому, более конструктивное определение сопряженности направлений.

Сопряженные направления

Пусть С - симметрическая матрица порядка NN ; направления s (1) , s (2) , s (3) ,..., s, r ≤ N , называются С -сопряженными, если эти направления линейно независимы и

s
C s= для всех i ≠ j . (3.34)

Опять обратимся к квадратичной функции общего вида

q(x ) = a + b T x+( 1 / t )x T C x.

Точки прямой, исходящей из х (1) в направлении d , задаются формулой

x = x+ λd .

Минимум q (x ) вдоль направления d определяется путем нахождения значения λ*, при котором q / λ=0. Вычислим эту производную по правилу дифференцирования сложной функции:

= =b+ xC d . (3.35)

По предположению теоремы минимум достигается в точке y (1) следовательно,

[(y (1))C b ] d = 0. (3.36)

Аналогично, так как минимум q (x ) при движении из точки х (2) в направлении d достигается в точке y (2) имеем

[(y (2))C b ] d = 0. (3.37)

Вычитая (3.36) из (3.37), получаем

(y (2) - y (1))C d = 0 (3.38)

В соответствии с данным выше определением направления d и (y (2) - y (1)) оказываются С -сопряженными, и свойство параллельного подпространства для квадратичных функций доказано.

Пример 3.5. Минимизация на основе свойства параллельного подпространства.

Опять рассмотрим квадратичную функцию q (x ) = 4 x+ 3 x - 4 xx+ x . Пусть заданы две точки х (1) = ,х (2) = и направлениеd = T . Первый поиск проводится вдоль прямой

x = +λ

и приводит к точке y (1) = [-,-](λ*= -). Второй поиск проводится вдоль прямой

x = +λ

и позволяет получить точку y (2) = [,– ](λ*=– ). Согласно свойству параллельного подпространства, направление

y (2) – y (1) = [,– ]– [– ,– ]= [,– ]

сопряжено с d = T

C [,– ].

Выше отмечалось, что в случае двух переменных оптимум q (x ) можно найти путем проведения поиска вдоль прямой, заданной направлением (y (2) – y (1)). Этот факт нетрудно проверить, поскольку минимум q (x ) вдоль прямой

x = [– ,– ]+λ [,– ]

достигается в точке х* = [– ,– ] T (λ* = – ), которая совпадает с полученным ранее решением.

В рассмотренных выше построениях для того, чтобы определить сопряженное направление, требовалось задать две точки и некоторое направление. Это не слишком удобно при проведении расчетов, поэтому предпочтительнее строить систему сопряженных направлений, исходя из одной начальной точки, что легко осуществить при помощи единичных координатных векторов е (1) , е (2) , е (3) ,..., е (N) . (Здесь рассматривается процедура построения сопряженных направлений в случае двух переменных, которая допускает очевидное обобщение для N-мерного пространства.) Пусть е (1) = ие (2) = . При заданной начальной точкех (0) вычислим значение λ (0) , которому соответствует минимум f (х (0) + λ (0) е (1)).

x (1) = х (0) + λ (0) е (1) .

и вычислим значение λ (1) , которому соответствует минимум f (х (1) + λ (1) е (2)). Положим

x (2) = х (1) + λ (1) е (2) .

x (3) = х (2) + λ (2) е (1) .

При этом направления (х (3) – х (1)) и е (1) оказываются сопряженными. Для того чтобы убедиться в этом, рассмотрим рис. 3.11. Заметим, что точка х х (0) в направление е (1) , а точка х (3) получена при поиске из точки х (2) в направлении е (1) . Следовательно, направление е (1) и (х (3) – х (1)) являются сопряжёнными согласно свойству параллельного подпространства. Далее если на следующей итерации провести поиск в направлении (x (3) – x (1)), то процедура поиска будет охватывать два сопряженных направления, и поскольку f (x ) предполагается квадратичной функцией двух переменных, в результате будет найдено решение х* .

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

В частности, нетрудно показать, что если точка y (1) найдена в результате поиска из точки х (1) вдоль каждого из М (< N ) сопряженных направлений, а точка y (2) получена в результате поиска из точки х (2) вдоль каждого из тех же М сопряженных направлений s (1) , s (2) , s (3) ,..., s ( M ) то вектор (y (2) – y (1)) задает направление, сопряженное со всеми выбранными М направлениями. Это утверждение известно как обобщенное свойство параллельного подпространства. Используя указанное свойство, можно обобщить метод построения сопряженных направлений, последовательные шаги реализации которого отражены на рис. 3.11 на случай пространства управляемых переменных более высокой размерности. Рис. 3.12 иллюстрирует построение сопряженных направлений в трехмерном пространстве.

Как показано на рис. 3.12, сначала поиск осуществляется вдоль трех координатных направлений е (1) , е (2) и е (3) затем эти направления последовательно заменяются вновь построенными сопряженными направлениями. Серия одномерных поисков из точки x (0) проводится в направлении е (3) , затем е (1) , е (2) и снова е (3) ; в результате построены сопряженные направления е (3) и (x (4) – x (1)). Направление е (1) заменяется новым направлением поиска, которое на рис. 3.12 обозначено цифрой 4 . Следующая серия поисков проводится в направлении 4 , затем е (2) , е (3) и снова 4 . Согласно обобщенному свойству параллельного подпространства, новое направление (x (8) – x (5)), обозначенное на рисунке цифрой 5 , сопряжено не только с 4 , но и с е (3) . Следовательно, направления е (3) , (x (4) – x (1)) и (x (8) – x (5)) образуют систему взаимно сопряженных направлений.

Рис. 3.11. Построение сопряженных направлений из одной точки.

Поэтому если провести дополнительный поиск из точки x (5) в направлении (x (8) – x (5)) (т. е. в направлении 5 на рисунке), то будет найдена точка x (9) , в которой должен достигаться оптимум квадратичной функции трех переменных f (x ) , поскольку поиск последовательно осуществляется в трех взаимно сопряженных направлениях. Таким образом, в трехмерном случае для нахождения точного (если, разумеется, оперировать недесятичными дробями) оптимума квадратичной функции требуется провести девять поисков вдоль прямой с использованием только значений функции. Алгоритм легко обобщается и в случае N -мерного пространства требует проведения последовательности N одномерных поисков, которая приводит к получению точки оптимума квадратичной функции. Ниже представлены шаги обобщенного алгоритма.

Рис. 3.12. Построение сопряженных направлений в трехмерном пространстве.

Метод сопряженных направлений Пауэлла

Шаг 1. Задать начальную точку х (0) и систему N линейно независимых направлений; возможен случай, когда s ( i ) = e ( i ) i = 1, 2, 3,..., N.

Шаг 2. Минимизировать f (x ) при последовательном движении по (N +1) направлениям; при этом полученная ранее точка минимума берется в качестве исходной, а направление s ( N ) используется как при первом, так и последнем поиске.

Шаг 3. Определить новое сопряженное направление с помощью обобщенного свойства параллельного подпространства.

Ш а г 4. Заменить s (l) на s (2) и т. д. Заменить s ( N ) сопряженным направлением. Перейти к шагу 2.

Для того чтобы применить изложенный метод на практике, его необходимо дополнить процедурами проверки сходимости и линейной независимости системы направлений. Проверка линейной независимости особенно важна в тех случаях, когда функция f (x ) не является квадратичной .

Из способа построения алгоритма следует, что в случае, когда целевая функция квадратична и обладает минимумом, точка минимума находится в результате реализации N циклов, включающих шаги 2, 3 и 4, где N - количество переменных. Если же функция не является квадратичной, то требуется более чем N циклов. Вместе с тем можно дать строгое доказательство того, что при некотором предположении метод Пауэлла сходится к точке локального минимума с суперлинейной скоростью (см. данное ниже определение).

Скорость сходимости. Рассматриваемый метод позволяет построить последовательность точек х ( k ) , которая сходится к решению x *. Метод называется сходящимся, если неравенство

≤1, где (3.39)

= x – х* , (3.40)

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

, (3.41)

где С - постоянная величина. Из формулы (3.39) следует, что при r = 1 имеет место неравенство С ≤ 1. Если r = 1 или r = 2, то алгоритм характеризуется линейной или квадратичной скоростью сходимости соответственно. При r = 1 и С = 0 алгоритм характеризуется суперлинейной скоростью сходимости.

Пример 3.6. Метод сопряженных направлений Пауэлла

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

f (x ) = 2 x + 4 xx – 10 x x+ x,

если задана начальная точка х (0) = T , в которой f (x (0)) = 314.

Шаг 1. s (1) = T , s (2) = T .

Шаг 2. (а) Найдем такое значение λ, при котором

f (x (0) + λs (2)) → min.

Получим: λ* - 0,81, откуда

x (l) = T - 0,81 T = T , f (x (l)) = 250.

(б) Найдем такое значение λ, при котором f (x (1) + λs (1)) → min.

λ* = – 3,26, x (2) = T , f (x (2)) = 1.10.

(в) Найдем такое значение λ, при котором f (x (2) + λs (2)) → min.

λ* = – 0.098, x (3) = T , f (x (3)) = 0.72.

Шаг 3. Положим s (3) = х (3) - x (1) = [-3.26,-0.098] T . После нормировки получим

s (3) = = [– 0,99955, – 0,03] T .

Положим s (1) = s (2) , s (2) = s (3) и перейдем к шагу 2 алгоритма.

Шаг 4. Найдем такое значение λ, при котором f (x (3) + λs (2)) → min.

λ* = – 0.734, x (4) = T , f (x (4)) = – 2,86.

Примечание. Если бы f (x ) была квадратичной функцией, то полученная точка являлась бы решением задачи (если пренебречь ошибкой округления). В данном случае итерации следует продолжить до получения решения.

Направления поиска, полученные в процессе реализации метода, показаны на рис. 3.13.

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

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