Математика

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



                                 Содержание:



      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

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