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

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

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

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

После чего вычисляются 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.