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

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

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

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

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

Кафедра информационно-измерительной техники 

Расчетно-пояснительная  записка 
 
 

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

  

по курсу      Системы автоматического проектирования 

   Нормоконтроль   Петрова Т. А.

 

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

   Студент   Бромберг Е.Е.

  

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

  

   Срок  выполнения ____________________________ 

   Работа защищена с оценкой___________ 
 
 
 
 
 
 
 
 
 
 

     г. Самара 2008  
 
 
 
 

  Реферат 

    Пояснительная записка содержит 16страниц, 5 рисунков и 2 источника. 

    ЭКСТРЕМУМ ФУНКЦИИ, БАЗИСНАЯ ТОЧКА, СИМПЛЕКС, ОТРАЖЕНИЕ, РАСТЯЖЕНИЕ, СЖАТИЕ, ДЛИНА ШАГА, МЕТОД НЕЛДЕРА-МИДА. 

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

 

 

ВВЕДЕНИЕ

    На  разработку методов прямого поиска для определения минимума функции 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