Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Метод Хука-Дживса (Метод конфигураций).
|
|
В иностранной литературе метод Хука - Дживса.
Алгоритм состоит из двух этапов. На первом этапе исследуются точки вблизи базисной, выбранной в качестве начального приближения. На втором этапе производится поиск в благоприятном направлении, гарантирующем уменьшение функции.
Сначала задаются начальные значения оптимизируемого вектора параметров х0 и вектора приращений Δ х0. После чего вычисляются F(х0) в базисной точке b1. Затем каждая переменная по очереди изменяется прибавлением длины шага Δ х, в направлении х1. Если это приводит к уменьшению значения функции, то она заменяется на f(х10+ Δ х1) и базисная точка перемещается в этом направлении х1+ Δ х1 (b2).
В противном случае вычисляется функция f(х1 - Δ х1 ), которая заменяет собой исходную, если она меньше ее и точка перемещается в новое положение х10 – Δ х1 (b2)..
Если уменьшения функции не происходит, то осуществляется переход к новому х, т.е. к х2 и расчеты повторяются до тех пор пока не переберутся все n переменных.
Если окажется, что точки совпадают b1 = b 2, а уменьшение функции не происходит, то уменьшается длина вектора приращений Δ х0 (в 10 раз).
Если точки не совпадают, то происходит поиск по образцу (второй этап метода). При этом используется информация, полученная на предыдущем этапе. Поиск идет в направлении заданном образцом и приводящим к успеху, т.е. от точки b1 к точке b2
где 
– новая искомая точка, μ – множитель (при μ =2 ).
И исследование функции продолжается в окрестности новой базисной точки. Если функция уменьшается, то получается новая базовая точка и следует повторить шаг поиска по образцу. В противном случае продолжается исследование в базовой точке b 2 (первый этап метода).
Процесс итераций завершается, когда длина шага будет уменьшена до заданного малого значения 
.
— Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта.
— Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы).
— SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание.
SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней. Зарегистрироваться и Начать продвижение
Обследование широкого диапазона возможных значений оптимизируемых параметров по начальным значениям может дать гарантию определения глобального минимума.
Алгоритм эффективен при минимизации функций f(x) с прямолинейными “оврагами”.
Он представлен программой №1, написанной на языке Турбо Паскаль.
Программа №1
program FUNXUK;
var Z: real;
var I, Ik, N: integer;
type s=array[1..10] of real; var X: s;
procedure FUNK;
begin
Z: =100*sqr(X[2]-sqr(X[1]))+sqr(1-X[1]); Ik: =Ik+1;
{ Z: =sqr(X[1]+10*X[2])+5*sqr(X[3]-X[4])+
sqr(sqr(X[2]-2*X[3]))+10*sqr(sqr(X[1]-X[4])); }
end;
procedure NadMida;
type vec=array[1..10] of real; var Fz, Xo, Xe, Xr, Xl, Xh, Xg, Xc: vec;
type mat=array[1..10, 1..10] of real; var S: mat;
var Fl, Fh, Fc, Fo, Fr, Fg, Fe, K, S1, S2, Sig, Xb, alfa, beta, gamma: real;
var I, J, G, H, L: integer;
label 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11;
begin Ik: =0;
writeln(' Введите число переменных'); read(N);
writeln(' Введите начальное приближение');
for I: =1 to N do
read(S[1, I]);
writeln(' Введите длину шага'); read(K);
for I: =2 to N+1 do begin
for J: =1 to N do
begin
if J=I-1 then begin S[I, J]: =S[1, J]+K; goto 1; end;
S[I, J]: =S[1, J];
1: end;
end; { alfa: =1; beta: =0.5; gamma: =2; }
writeln(' Введите alfa, beta, gamma'); read(alfa, beta, gamma);
for I: =1 to N+1 do begin
for J: =1 to N do
X[J]: =S[I, J];
Funk;
Fz[I]: =Z; end;
10: Fh: =-1E+20; Fl: =1E+20;
for I: =1 to N+1 do begin
if Fz[I]> Fh then begin Fh: =Fz[I]; H: =I; end;
if Fz[I]< Fl then begin Fl: =Fz[I]; L: =I; end;
end;
Fg: =-1E+20;
for I: =1 to N+1 do begin
if I=H then goto 2;
if Fz[I]> Fg then begin Fg: =Fz[I]; G: =I; end;
2: end;
for J: =1 to N do begin
Xo[J]: =0;
for I: =1 to N+1 do begin
if I=H then goto 3;
Xo[J]: =Xo[J]+S[I, J];
3: end;
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];
Funk;
Fo: =Z;
for J: =1 to N do begin
Xr[J]: =Xo[J]+Alfa*(Xo[J]-Xh[J]);
X[J]: =Xr[J];
end;
Funk;
Fr: =Z;
if Fr< Fl then goto 4;
if Fr> Fg then goto 5;
goto 7;
4: for J: =1 to N do begin
Xe[J]: =Gamma*Xr[J]+(1-Gamma)*Xo[J];
X[J]: =Xe[J];
end;
Funk; Fe: =Z;
if Fe< Fl then goto 6;
goto 7;
6: for J: =1 to N do
S[H, J]: =Xe[J];
Fz[H]: =Fe;
goto 8;
7: for J: =1 to N do
S[H, J]: =Xr[J];
Fz[H]: =Fr;
goto 8;
5: if Fr> Fh then goto 9;
for J: =1 to N do
Xh[J]: =Xr[J];
Fz[H]: =Fr;
9: for J: =1 to N do begin
Xc[J]: =Beta*Xh[J]+(1-Beta)*Xo[J];
X[J]: =Xc[J];
end;
Funk; Fc: =Z;
if Fc> Fh then goto 11;
— Разгрузит мастера, специалиста или компанию;
— Позволит гибко управлять расписанием и загрузкой;
— Разошлет оповещения о новых услугах или акциях;
— Позволит принять оплату на карту/кошелек/счет;
— Позволит записываться на групповые и персональные посещения;
— Поможет получить от клиента отзывы о визите к вам;
— Включает в себя сервис чаевых.
Для новых пользователей первый месяц бесплатно. Зарегистрироваться в сервисе
for J: =1 to N do
S[H, J]: =Xc[J];
Fz[H]: =Fc;
goto 8;
11: 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;
Funk; Fz[I]: =Z;
end;
8: S1: =0; S2: =0;
for I: =1 to N+1 do begin
S1: =S1+Fz[I];
S2: =S2+Fz[I]*Fz[I];
end;
Sig: =S2-S1*S1/(N+1); Sig: =Sig/(N+1);
if Sig< 1E-10 then begin
for J: =1 to N do
writeln(Xl[J]);
writeln(Fz[L]);
writeln(Ik); readln;
end else
goto 10;
end;
procedure XUKA;
label 1, 2;
var I, J, PS, BS: integer;
var K, H, FI, FB, F: real;
type t=array[0..10] of real; var Y, P, B: t;
begin
writeln('Введите число переменных N='); readln(N);
writeln('Введите начальное приближение');
for I: =1 to N do begin writeln('Введите X[', I, ']='); readln(X[I]); end;
writeln('Введите шаг H='); readln(H); K: =H;
for I: =1 to N do begin Y[I]: =X[I]; P[I]: =X[I]; B[I]: =X[I]; end;
FUNK; F: =Z; FI: =F; PS: =0; BS: =1; J: =1; FB: =FI;
1: X[J]: =Y[J]+K; FUNK; F: =Z;
if F< FI then begin Y[J]: =X[J]; FUNK; F: =Z; FI: =F;
if J=N then goto 2;
J: =J+1; goto 1; end;
X[J]: =Y[J]-K; FUNK; F: =Z;
if F< FI then begin Y[J]: =X[J]; FUNK; F: =Z; FI: =F;
if J=N then goto 2;
J: =J+1; goto 1; end;
X[J]: =Y[J]; begin FUNK; F: =Z; FI: =F;
if J=N then goto 2;
J: =J+1; goto 1; end;
2: if FI< (FB-1E-18) then begin for I: =1 to N do
begin P[I]: =2*Y[I]-B[I]; B[I]: =Y[I]; X[I]: =P[I]; Y[I]: =X[I]; end;
FUNK; F: =Z; FB: =FI; PS: =1; BS: =0; FI: =F; J: =1;
goto 1;
end;
if ((PS=1)and(BS=0)) then begin
for I: =1 to N do begin P[I]: =B[I]; Y[I]: =B[I]; X[I]: =B[I]; end;
FUNK; F: =Z; BS: =1; PS: =0; FI: =F; FB: =F; J: =1;
goto 1; end
else begin K: =K/10;
if K< 1E-15 then begin
for I: =1 to N do writeln('X[', I, ']=', X[I]: 3, ' Ik=', Ik); exit;
end;
J: =1; goto 1; end;
end;
begin Ik: =0; {XUKA; } NadMida; readln; end.
Программа состоит из 3-х процедур. Процедура расчета минимизируемой функции FUNXUK, процедура метода Хука – Дживса (XUKA), процедура метода Нелдера-Мида (NаdMida).
В MATLAB имеется стандартный оператор, реализующая метод Нелдера-Мида. Для использования этого оператора необходимо запрограммировать в m - файле исследуемую функцию, например, funk(x), где x – вектор, задать начальное приближение x0 и вызвать функцию [M, f]=fminsearch(@funk, [ x0]). Получим вектор M координат искомых точек минимума и минимальное значение функции f.
|
|