Материалы сайта
Это интересно
Модифицированный метод Хука-Дживса
Содержание: 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, но с уменьшенной длиной шага. На практике удовлетворительным является уменьшение шага (шагов) в десять раз от начальной длины. 4. Если b2[pic]b1, то производится поиск по образцу. В. При поиске по образцу используется информация, полученная в процессе исследования, и минимизация функции завершается поиском в направлении, заданном образцом. Эта процедура производится следующим образом: 3. Разумно двигаться из базисной точки 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[pic] x2[pic] x1+x2[pic]. Блок-схема данного метода Нет Да Да Нет Да Нет Блок-схема единичного исследования Да Нет Нет Да Да Нет Нет Да Текст программы 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