Минимизация функции многих переменных методом конфигураций

Пусть задана функция n переменных F(x₁ , x₂ , ..., x_n ). Поиск минимального значения начинаем с некоторой начальной точки P_i  и начального шага S_1i  = d. Вычисляем значение функции в точках F(P₁ , ..., P_i -d, ..., P_n ), F(P₁ , ..., P_i , ..., P_n ), F(P₁ , ..., P_i +d, ..., P_n ). Если из этих трех значений функция минимальна в крайней точке, то принимаем ее за начальную, если в средней точке (P₁ , ..., P_i , ..., P_n ), то она принимается за начальную, а размер шага по x_i  уменьшается на коэффициент r и становится равным по i-му аргументу S_1i  = S_1i r. Вычисления прекращаются, если размер шага по всем аргументам становится меньше d₁  или количество вычислений функции F становится больше m₂ .

Если нашли ошибку в алгоритме - сообщите!

Реализации алгоритма на различных языках:

Блоксхемы:

Реализация алгоритма на AlgoPascal:

unit ConfigurationOptimizeUnit;

declaration
    (********************************
    оптимизируемая функция.
    принимает массив элементов с индексами
    от 1 до n.
    ********************************)
    function F(X:array of Real):Real;
    
interface ConfigurationOptimize;

implementation

(***************************************************************
Поиск минимума функции методом конфигураций.
Параметры:
    d           - начальный шаг
    r           - коэффициент уменьшения шага
    e           - размер шага, при котором метод останавливается
    N           - размерность задачи
    MaxSteps    - максимальное число шагов
    var X:      - начальное приближение. Сюда же помещается
                  результат.
***************************************************************)
procedure ConfigurationOptimize(
    d:          Real;
    r:          Real;
    e:          Real;
    N:          Integer;
    MaxSteps:   Real;
    var X:      array of Real);
var
    i:      Integer;
    k:      Integer;
    y:      array of Real;
    s1:     array of Real;
    s2:     Real;
    s4:     Real;
    ws:     array of Boolean;
begin
    SetBounds(S1, [1,N]);
    SetBounds(Y,  [1,N]);
    SetBounds(WS, [1,N]);
    k:=0;
    for i:=1 to n do
        S1[i]:=d;

    repeat
        k:=k+1;
        for i:=1 to n do
            ws[i]:=True;
        s2:=F(X);
        for i:=1 to n do
            y[i]:=x[i];
        for i:=1 to n do
        begin
            y[i]:=y[i]+s1[i];
            s4:=F(y);
            if s4<s2 then
                s2:=s4
            else
            begin
                s1[i]:=-s1[i];
                y[i]:=y[i]+2*s1[i];
                s4:=F(y);
                if s4<s2 then
                    s2:=s4
                else
                begin
                    y[i]:=y[i]-s1[i];
                    ws[i]:=False;
                end;
            end;
        end;
        d:=r*d;
        for i:=1 to n do
        begin
            if ws[i] then
            begin
                x[i]:=y[i];
                d:=AbsReal(s1[i]);
            end
            else
            begin
                s1[i]:=s1[i]*r;
                if d<AbsReal(s1[i]) then
                    d:=AbsReal(s1[i]);
            end;
        end;
    until (d<e) or (k>maxsteps);
end;

end.

Бочканов Сергей, Быстрицкий Владимир
Copyright © 1999-2004
При поддержке проекта MANUAL.RU