Метод прямого поиска (конфигураций).

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

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

Сначала задаются начальные значения оптимизируемого вектора х⁰ и вектора приращений Δ х⁰.

После чего вычисляются F(х⁰) в точке b₁. Затем каждая переменная по очереди изменяется прибавлением длины шага Δ х, в направлении х₁.

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

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

Если умножения функции не происходит, то осуществляется переход к новому х, т.е. к х₂ и

расчеты повторяются до тех пор пока не переберутся все n переменных. Если окажется, что точки совпадают l₁=l ₂ а уменьшение функции не происходит, то уменьшается длина шага (в 10 раз).

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

b_i³ = b_i¹ +μ (b_i+1² - b_i¹ )

где i – очередные точки, μ – множитель (при μ =2 b_i³ = 2b_i+1² - b_i¹ )

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

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

Алгоритм эффективен при min-ции f(x) с прямолинейными “оврагами”

procedure XUKA;

var I, J, PS, BS, N: integer; var K, H, FI, FB, Z: real;

type t=array[0..10] of real; var Y, P, B: t;

label 1, 2, 3, 4, 5, 6, 7, 8;

begin

H: =0.1; N: =3; K: =H;

for I: =1 to N do

begin Y[I]: =x[I]; P[I]: =x[I]; B[I]: =x[I];

end;

FUNK; Z: =F; FI: =F;

PS: =0; BS: =1; {исследование вокруг базисной точки}

J: =1; FB: =FI;

4: x[J]: =Y[J]+k; FUNK; Z: =F;

if Z< FI then goto 1;

X[J]: =Y[J]-K; FUNK; Z: =F;

if Z< FI then goto 1;

x[J]: =Y[J]; goto 2;

1: Y[J]: =x[J];

2: FUNK; Z: =F; FI: =F; {исследующий поиск}

if J=N then goto 3;

J: =J+1; goto 4;

3: if FI< (FB-1E-8) then goto 5;

{если функция уменьшалась – произвести поиск по образцу}

if ((PS=1) and (BS=0)) then goto 6;

{но если исследование проводилось в точке образца и уменьшение функции не достигнуто, то необходимо изменить базисную точку в 6: иначе уменьшить длину шага в 7: }

6: for I: =1 to N do

begin

P[I]: =B[I]; Y[I]: =B[I]; x[I]: =B[I];

end;

FUNK;

Z: =F; BS: =1; PS: =0; FI: =Z; FB: =Z; J: =1; goto 4; {замена базисной точки}

7: K: =K/10; J: =1; goto 4;

if K< 1E-8 then goto 8; {если поиск не закончен, то провести исследование вокруг новой базисной точки}

{поиск по образцу}

5: for I: =1 to N

begin P[I]: =2*Y[I]-B[I]; B[I]: =Y[I]; X[I]: =P[I]; Y[I]: =X[I];

end;

FUNK;

Z: =F; FB: =FI; PS: =1; BS: =0; FI: =Z;

{далее исследование вокруг последней точки образца}

J: =1; goto 4;

8: writeln(x[1]: 3, x[2]: 3, x[3]: 3);

end;

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

Существует метод Нелдера-Мида (поиск по деформируемому многограннику). Он также требует для реализации знание лишь оптимизируемой функции. Эффективен до n 6.