10 ЛАБОРАТОРНАЯ РАБОТА. Пояснительная записка содержит 16страниц, 5 рисунков и 2 источника
![]()
|
Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Самарский государственный технический университет Факультет автоматики и информационных технологий Кафедра информационно-измерительной техники Расчетно-пояснительная записка к курсовой работе Оптимизация прямого поиска для определения минимума функции n переменных методом Нелдера-Мида. по курсу Системы автоматического проектирования Нормоконтроль Петрова Т. А. Руководитель работы Хавлин О.В. Студент Бромберг Е.Е. Группа 5-АИТ-5 Срок выполнения ____________________________ Работа защищена с оценкой___________ г. Самара 2008 Реферат Пояснительная записка содержит 16страниц, 5 рисунков и 2 источника. ЭКСТРЕМУМ ФУНКЦИИ, БАЗИСНАЯ ТОЧКА, СИМПЛЕКС, ОТРАЖЕНИЕ, РАСТЯЖЕНИЕ, СЖАТИЕ, ДЛИНА ШАГА, МЕТОД НЕЛДЕРА-МИДА. В пояснительной записке изложены основы прямого поиска для определения минимума функции n переменных. Выбран метод оптимизации поиска Нелдера-Мида. В расчетной части метод Нелдера-Мида реализован программно, в среде Turbo Pascal, представлены блок схема алгоритма оптимизации, листинг программы.
ВВЕДЕНИЕ На разработку методов прямого поиска для определения минимума функции n переменных было затрачено много усилий. Методы прямого поиска являются методами, в которых используются только значения функции. Один из наиболее надежных метод Нелдера-Мида, являющийся одним из самых эффективных, если ![]() Рассмотрим функцию двух переменных. Ее линии постоянного уровня представлены на рис. 1. Линией постоянного уровня называется кривая в двухмерном сечении пространственных параметров ( в данном случае – в плоскости ![]() ![]() ![]() ![]() 1 МЕТОД НЕЛДЕРА-МИДАМетод Нелдера-Мида является развитием симплексного метода Спендли, Хекста и Химсворта. Множество значений ![]() Идея метода состоит в сравнении значений функции в ![]() ![]() В данном методе симплекс перемещается с помощью трех основных операций: отражение, растяжение и сжатия. Рассмотрим основные шаги процедуры: А. Найдем значения функции ![]() в вершинах симплекса. Б. Найдем наибольшее значение функции ![]() ![]() ![]() ![]() В. Найдем центр тяжести всех точек, за исключением точки ![]() ![]() И вычислим ![]() Г. Удобнее всего начать перемещение от точки ![]() ![]() ![]() ![]() ![]() Операция отражения иллюстрируется рис. 1. Если ![]() ![]() ![]() ![]() Д. Сравним значения функции ![]() ![]() 1. Если ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() 2. Если ![]() ![]() ![]() ![]() ![]() ![]() ![]() 3. Если ![]() ![]() ![]() ![]() Е. Сравним значения функции ![]() ![]() 1. Если ![]() ![]() Если ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() 2. В этом случае ![]() ![]() ![]() ![]() ![]() ![]() Если ![]() ![]() ![]() ![]() Если ![]() ![]() ![]() ![]() ![]() ![]() ![]() Коэффициенты ![]() ![]() Рекомендация основана на результатах экспериментов с различными комбинациями значений. Эти значения параметров позволяют методу быть эффективным, но работать в различных сложных ситуациях. В данной программе точка ![]() ![]() ![]() ![]() Где ![]() ![]() Обозначения, используемые в программе, в целом соответствуют обозначениям, приведенным в тексте. 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] 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 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 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. |