Метод Хука-Дживса (Метод конфигураций).

В иностранной литературе метод Хука - Дживса.

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

Сначала задаются начальные значения оптимизируемого вектора параметров х⁰ и вектора приращений Δ х⁰. После чего вычисляются F(х⁰) в базисной точке b₁. Затем каждая переменная по очереди изменяется прибавлением длины шага Δ х, в направлении х₁. Если это приводит к уменьшению значения функции, то она заменяется на f(х₁⁰+ Δ х₁) и базисная точка перемещается в этом направлении х₁+ Δ х₁ (b₂).

В противном случае вычисляется функция f(х₁ - Δ х₁ ), которая заменяет собой исходную, если она меньше ее и точка перемещается в новое положение х₁⁰ – Δ х₁ (b₂)..

Если уменьшения функции не происходит, то осуществляется переход к новому х, т.е. к х₂ и расчеты повторяются до тех пор пока не переберутся все n переменных.

Если окажется, что точки совпадают b₁ = b ₂, а уменьшение функции не происходит, то уменьшается длина вектора приращений Δ х⁰ (в 10 раз).

Если точки не совпадают, то происходит поиск по образцу (второй этап метода). При этом используется информация, полученная на предыдущем этапе. Поиск идет в направлении заданном образцом и приводящим к успеху, т.е. от точки b₁ к точке b₂

где – новая искомая точка, μ – множитель (при μ =2 ).

И исследование функции продолжается в окрестности новой базисной точки. Если функция уменьшается, то получается новая базовая точка и следует повторить шаг поиска по образцу. В противном случае продолжается исследование в базовой точке b ₂ (первый этап метода).

Процесс итераций завершается, когда длина шага будет уменьшена до заданного малого значения .

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

Алгоритм эффективен при минимизации функций 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 – вектор, задать начальное приближение x⁰ и вызвать функцию [M, f]=fminsearch(@funk, [ x⁰]). Получим вектор M координат искомых точек минимума и минимальное значение функции f.