Федеральное агентство по образованию

Государственное образовательное учреждение высшего

профессионального образования

Самарский государственный технический университет

Факультет автоматики и информационных технологий

Кафедра информационно-измерительной техники
Расчетно-пояснительная записка


к курсовой работе        Оптимизация прямого поиска для определения минимума функции n переменных методом Нелдера-Мида.

 
по курсу      Системы автоматического проектирования
   Нормоконтроль   Петрова Т. А.

 

   Руководитель работы  Хавлин О.В. 
   Студент   Бромберг Е.Е.

  

   Группа      5-АИТ-5

  

   Срок выполнения ____________________________
   Работа защищена с оценкой___________
г. Самара 2008
 Реферат
Пояснительная записка содержит 16страниц, 5 рисунков и 2 источника.
ЭКСТРЕМУМ ФУНКЦИИ, БАЗИСНАЯ ТОЧКА, СИМПЛЕКС, ОТРАЖЕНИЕ, РАСТЯЖЕНИЕ, СЖАТИЕ, ДЛИНА ШАГА, МЕТОД НЕЛДЕРА-МИДА.
В пояснительной записке изложены основы прямого поиска для определения минимума функции n переменных. Выбран метод оптимизации поиска Нелдера-Мида. В расчетной части метод Нелдера-Мида реализован программно, в среде Turbo Pascal, представлены блок схема алгоритма оптимизации, листинг программы.

СОДЕРЖАНИЕ
Введение……………………………………………………...    1      Метод Нелдера-Мида…………………………………... 2      Блок –схема алгоритма………………………………….. 3      Листинг программы……………………………………... 4      Список используемой литературы………………………	4   5   9   10 16

ВВЕДЕНИЕ

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

Рассмотрим функцию двух переменных. Ее линии постоянного уровня представлены на рис. 1. Линией постоянного уровня называется кривая в двухмерном сечении пространственных параметров ( в данном случае – в плоскости ), значение функции на которой константа. Минимум функции лежит в точке , где  -где ряд значений от 0,1 до 1 с шагом 0,1.

1 МЕТОД НЕЛДЕРА-МИДА

Метод Нелдера-Мида является развитием симплексного метода Спендли, Хекста и Химсворта. Множество значений й равноудаленной точки в n
-мерном пространстве называется регулярным симплексом. Эта конфигурация рассматривается в методе Спендли, Хекста и Химсворта. Следовательно, в двумерном пространстве симплексом является равносторонний треугольник, а в трехмерном пространстве – правильный тетраэдр.

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

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

А. Найдем значения функции



в вершинах симплекса.

Б. Найдем наибольшее значение функции , следующее за набольшим значением функции , наименьшее значение функции  и соответствующие им точки .

В. Найдем центр тяжести всех точек, за исключением точки . Пусть центром тяжести будет



И вычислим .

Г. Удобнее всего начать перемещение от точки . Отразим точку  относительно точки , получим точку  и найдем .

Операция отражения иллюстрируется рис. 1. Если коэффициент отражения, то положение точки  определяется следующим образом:




Д. Сравним значения функции  и .

1. Если <, то мы получим наименьшее значение функции. Направление из точки  в точку  наиболее удобно для перемещения. Таким образом, мы производим растяжение в этом направлении и находим точку  и значение . Рисунок 2 иллюстрирует операцию растяжения симплекса. Коэффициент растяжения  можно найти из следующих соотношений:



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

3. Если > и >, то перейдите на шаг Е.

Е. Сравним значения функции  и .

1. Если >, то переходим непосредственно к шагу Е, 2.

Если <, то замещаем точку  на точку  и значение функции  на значение . Запоминаем значение > из шага Д,2. приведенного выше. Затем переходим на шаг Е, 2.

2. В этом случае >, поэтому ясно, что мы переместились далеко от точки  к точке . Попытаемся исправить это, найдя точку  с помощью шага сжатия, показанного на рисунке 3.

Если >, то сразу переходим к шагу сжатия и находим точку  из соотношения:



Если <, то сначала заменим точку  на точку , а затем произведем сжатие. Тогда точку  найдем из соотношения (см. рис.4):




Коэффициенты  в вышеприведенной процедуре являются соответственно коэффициентами отражения, сжатия и растяжения. Нелдер и Мид рекомендуют брать  

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





Где - произвольная длина шага, а - единичный вектор.

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

2 БЛОК – СХЕМА АЛГОРИТМА

Шаги этой процедуры представлены в виде блок-схемы алгоритма на рисунке 5.

3 ЛИСТИНГ ПРОГРАММЫ

Program Nidelermid;

Uses Crt;

Var n, i, j, g, h: integer;

S: array[1..10,1..10] of real;

x, xh,xg,xl,xo,xr,xc,xe: array[1..10] of real;

f: array[1..10] of real;

shag, l: integer;

al,be,ga: real;

k, fh, fl,fg,fo,fr,FE,fc,s1,s2,sig: real;

label 620,1520,1700,1920,2060,2200, 1300, 1600, 1440,2220;
function z(x1,x2,x3,x4: REAL): real;

begin

   Z:=100*(x2-x1*x1)*(x2-x1*x1)+(1-x1)*(1-x1);

   inc(shag);

end;
begin

    clrscr;

   shag:=0;

   g:=1;

   h:=1;

   l:=1;

   Writeln('Simpleksniy method Nidlera mida');

   Writeln('Function: F(x)=100(x1-x2^2)^2+(1-x1)^2');

   Writeln('Vvedite chislo peremennih');

   Readln(n);

   Writeln('Vvedite nachalnoe pribligenie');

   for j:=1 to n do

      readln(s[1,j]);

   Writeln('Vvedite dlinny shaga');

   Readln(k);
   for i:=2 to n+1 do

      for j:=1 to n do

         if j=i-1 then

            s[i,j]:=s[1,j]+k

            else s[i,j]:=s[1,j];

   Writeln('Vvedite Alfa, beta, gamma');

   readln(al, be, ga);

  

   for i:=1 to n+1 do

      begin

         for j:=1 to n do x[j]:=s[i,j];

        

         f[i]:=z(x[1],x[2],x[3],x[4]);

        

      end;
   620:

   fh:=-0.00000000000000000001;

   fl:=0.00000000000000000001;

   for i:=1 to n+1 do

      begin

         if f[i]>fh then

            begin

               fh:=f[i];

               h:=i;

            end;

         if f[i]<fl then

            begin

               fl:=f[i];

               l:=i;

            end; 

      end;

   fg:=0.00000000000000000001;

  

   for i:=1 to n+1 do

      if i<>h then

         if f[i]>fg then

            begin

               fg:=f[i];

               g:=i;

            end;

   for j:=1 to n do

      begin

         xo[j]:=0;

        

         for i:=1 to n+1 do

            if i<>h then xo[j]:=xo[j]+s[i,j];

         xo[j]:=xo[j]/n;

         xh[j]:=s[h,j];

         xg[j]:=s[g,j];

         xl[j]:=s[l,j];

      end;

  

   for j:=1 to n do x[j]:=xo[j];

   fo:=z(x[1],x[2],x[3],x[4]);

   writeln('Vichisliaem centr tiagest 1120');

  

   for j:=1 to n do

      begin

         xr[j]:=xo[j]+al*(xo[j]-xh[j]);

         x[j]:=xr[j];

      end;

   fr:=z(x[1],x[2],x[3],x[4]);

   writeln('Vipolniaetsia otragenie 1220', z(x[1],x[2],x[3],x[4]):3:5);

   if fr<fl then goto 1300;

   if fr>fg then goto 1600;

   goto 1520;

   1300:

      for j:=1 to n do

         begin

            xe[j]:=ga*xr[j]+(1-ga)*xo[j];

            x[j]:=xe[j];

         end;

   fe:=z(x[1],x[2],x[3],x[4]);

   if fe<fl then goto 1440;

   goto 1520;

   1440:

     for j:=1 to n do s[h,j]:=xe[j];

     f[h]:=fe;

     Writeln('Vipolnite rastiagenie 1480', z(x[1],x[2],x[3],x[4]):3:5);

     goto 2060;

   1520:

   for j:=1 to n do s[h,j]:=xr[j];

   f[h]:=fr;

   writeln('Vipolnenie otragenia 1560');

   goto 2060;

   1600:

   if fr>fh then goto 1700;

   for j:=1 to n do xh[j]:=xr[j];

   f[h]:=fr;

   1700:

   for j:=1 to n do

      begin

         xc[j]:=be*xh[j]+(1-be)*xo[j];

         x[j]:=xc[j];

      end;

   fc:=z(x[1], x[2],x[3],x[4]);

   if fc>fh then goto 1920;

   for j:=1 to n do s[h,j]:=xc[j];

   f[h]:=fc;

   writeln('Vipolnenie sjatia 1880', fc:3:5);

   goto 2060;

   1920:

   for i:=1 to n+1 do

      begin

         for j:=1 to n do

            begin

               s[i,j]:=(s[i,j]+xl[j])/2;

               x[j]:=s[i,j];

            end;

         f[i]:=z(x[1], x[2],x[3],x[4]);

        

      end;

   Writeln('Vipolnenie redikcii 2040');

   2060:

   s1:=0;

   s2:=0;

   for i:=1 to n+1 do

      begin

         s1:=s1+f[i];

         s2:=s2+f[i]*f[i];

      end;

   sig:=s2-s1*s1/(n+1);

   sig:=sig/(n+1);

   if sig<0.000000001 then goto 2220;

   2200:

   goto 620;

   2220:

   Writeln('Minimum naiden v tochke f=', z(x[1],x[2],x[3],x[4]):3:5);

   for j:=1 to n do Writeln('x',j,' =',xl[j]:3:5);

   Writeln('Kolichestvo vichisleniy ravno ', shag);

   readln;

  

end.

4 СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. M.J. Box, D.Davies and W.H.Swann, “Non-linear Optimization Techniques,” ICI Ltd Monograph No 5, Oliver and Boyd, 1969.

2. R.Hooke and T.A. Jeeves, “Direct search solution of numerical and statistical problem”, 212-219, 1961.