II Часть : безусловная оптимизация функции

 

Постановка задачи

Рассматривается задача оптимизации целевой скалярной функции  по аргументам (параметрам) , на вариации которых никаких ограничений не накладывается.

                                                             

    Моему варианту № 5 соответствуют следующие данные:

 

f(x₁, x₂) = 2 (х₁ – 5)² + (х₂ – 8)²

        

16	Модифицированный метод наилучшей пробы
	Метод простой градиентной оптимизации

 

 

Модифицированный метод наилучшей пробы

Суть метода

Этот метод в отличие от предыдущего позволяет выбирать наилучшее направление изменения функции (при этом оно не обязательно совпадает с антиградиентом функции).

Алгоритм метода

Из некоторой промежуточной точки поиска минимума целевой функции x ^{( k )} осуществляется m-случайных независимых пробных шагов:

                                                        (5.52)

Также, как и ранее (см. предыдущий метод) x ^{(к j )}- единичные случайные независимые векторы с равномерной функцией распределения вероятности внутри шара единичного радиуса (в частном случае – круга).

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

f(x^(k)+h_прx^(kj*)) = min f(x^(k)+h_прx^(kj)),                         (5.53)

                                  

В этом направлении - x^(kj*) совершается рабочий шаг движения:

 ,                                          (5.54)

где    .                                                 (5.55)

Из формул (5.52)-(5.55) следует, что эффективность метода определяется следующими параметрами метода, задаваемыми оператором:

h _пр, h _раб, m.

Они, как правило, входят в состав формальных параметров компьютерной подпрограммы, реализующей данный метод.

Замечание

Можно показать, что в пределе при m стремящемся к ¥ , направление x ^{( kj *)} стремится к антиградиенту функции, то есть:

                                            (5.56)

Преимущества метода

- Метод позволяет при количестве проб m < n получить направление x ^{( kj *)} близкое к антиградиенту функции.

- Метод просто программируется.

- Позволяет определить глобальный экстремум (в принципе).

Недостатки метода

- Метод не исключает выбор «наилучшего» из m-направлений, в котором функция f(x) будет возрастать!

- Накопленная при m-проб информация о поведении целевой функции используется не эффективно.

 

Модификация метода наилучшей случайной пробы

В ответ на 1-ый недостаток рассмотренного метода возникла идея дополнить процедуру (5.53) операцией, присущей методу простой случайной оптимизации.

(5.57)

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

 

Блок-схема модифицированного метода наилучшей пробы

1.

А while(Abs(A2-A1)> Eps) Do

B for i: =1 to m do

g1[i]: =Random(100)-50; g2[i]: =Random(100)-50;

НАЧАЛО

n: =2; m: =20; h: =0.1; hrab: =0.15; A1: =0;

A2: =A1;

A2: =F(X[n-1, 1], X[n-1, 2]);

2

Блок-схема основного метода:

 

2

then

else

g1[i]: =g1[i]/g3[i]; g2[i]: =g2[i]/g3[i];

B

g3[i]: =Power((g1[i]*g1[i])+(g2[i]*g2[i]), 0.5);

3

g3[i]: =1;

g3[i]=0

C for i: =1 to m do

 

 

КОНЕЦ

3

then

else

n: =n-2;

A1< A2

C

A

A1: =F(X[n-1, 1]+g1[i]*h, X[n-1, 2]+g2[i]*h);

X[n, 1]: =X[n-1, 1]+g1[i]*hrab; X[n, 2]: =X[n-1, 2]+g2[i]*hrab; n: =n+1;

Метод простой градиентной минимизации

Сущность метода

Метод характеризуется относительно малым постоянным шагом = h, который задаётся как параметр метода.

Идея метода видна из простого соотношения:

                      (5.75)

где  – i -я составляющая вектора - градиента функции в точке x ^{( k )}.

При заданном малом шаге h алгоритм метода определяется формулой (5.74).

Замечание

Хотя шаг поиска h должен быть малым, но не меньше порога чувствительности функции:

| f(x^(k+1)) - f(x^(k)) | > d

где d - максимальная вычислительная погрешность ПЭВМ.

Окончание численной процедуры поиска минимума функции может определяться выполнением следующего условия.

где  - евклидова норма вектора, - малая положительная величина, задаваемая как параметр.

Графически метод простой градиентной минимизации в двумерном пространстве иллюстрируется на рис. 5.18.

Рис. 5.18

Недостатки

· Основным недостатком метода является его низкая эффективность с точки зрения количества шагов поиска, а также с точки зрения затрат машинного времени.

· Метод склонен к зацикливанию в местах резкого изменения направления «оврага» целевой функции.

Преимущества

· Метод прост при программной реализации.

Метод надежен при использовании его в условиях сложной поверхности целевой функции.

Блок-схема метода простой градиентной минимизации:

НАЧАЛО

gradF[1]: = 100; gradF[2]: = 100; h: = 0.000001; CaseSwitch: = 0; Sol: = false;

alfa < > 0

CaseSwitch: = CSwitch(X[1], X[2])

then

else

А while (((Abs(gradF[1]) > Eps) and (Abs(gradF[2]) > Eps)) and (Sol = false)) do

gradF[1]: =…; gradF[2]: =…;

2

2

X[1]: = X[1] - h * gradF[1]; X[2]: = X[2] - h * gradF[2];

n = 1000

Sol: = true;

then

else

A

GetSolution: = Sol;

КОНЕЦ

 

Примеры работы программы:

 

В данном примере введена начальная точка (-10; -15) и точность 0, 01. Программа приходит к точке (5; 3), что является минимумом целевой функции.

    Метод простой градиентной оптимизации сходится за 399 итераций, а модифицированный метод наилучшей пробы за 845 итераций.

 

Выводы

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

    Метод простой градиентной оптимизации сходится за 399 итераций, а модифицированный метод наилучшей пробы за 845 итераций.

Листинг метода случайного поиска с направляющей сферой:

procedure TMetNaiProb.Executing(var X: TVectorMass; Eps: real; var n: integer);

var

h, hrab, A1, A2: real;

g1: array[1..100] of real;

g2: array[1..100] of real;

g3: array[1..100] of real;

m, i: integer;

begin

n: =2;

m: =20;

h: =0.1;

hrab: =0.3;

A1: =0;

A2: =F(X[n-1, 1], X[n-1, 2]);

while (Abs(A2-A1)> Eps) Do

begin

A2: =A1;

for i: =1 to m do

begin

g1[i]: =Random(100)-50;

g2[i]: =Random(100)-50;

g3[i]: =Power((g1[i]*g1[i])+(g2[i]*g2[i]), 0.5);

if g3[i]=0 then

g3[i]: =1;

g1[i]: =g1[i]/g3[i];

g2[i]: =g2[i]/g3[i];

end;

for i: =1 to m do

begin

A1: =F(X[n-1, 1]+g1[i]*h, X[n-1, 2]+g2[i]*h);

if A1< A2 then

begin

X[n, 1]: =X[n-1, 1]+g1[i]*hrab;

X[n, 2]: =X[n-1, 2]+g2[i]*hrab;

n: =n+1;

end;

end;

 

end;

n: =n-2;

 

end;

 

function TMetNaiProb.F(X1, X2: real): real;

begin

F: = Power(X1 - 5, 2) + 2 * Power(X2 - 3, 2);

end;

Листинг метода простой градиентной минимизации:

procedure TOptGradMeth.GetSolution(var X: TVectorMass; Eps: real; var n: integer);

var

gradF: TVector;

h, step: real;

begin

n: = 1;

h: = 0.1;

 

gradF[1]: = 100;

gradF[2]: = 100;

 

while ((Abs(gradF[1]) > Eps) or (Abs(gradF[2]) > Eps)) do

begin

gradF[1]: = (F(X[n, 1] + h, X[n, 2]) - F(X[n, 1], X[n, 2])) / h;

gradF[2]: = (F(X[n, 1], X[n, 2] + h) - F(X[n, 1], X[n, 2])) / h;

 

n: = n + 1;

X[n, 1]: = X[n - 1, 1] - h * gradF[1];

X[n, 2]: = X[n - 1, 2] - h * gradF[2];

end;

end;

 

function TOptGradMeth.F(X1, X2: real): real;

begin

F: = Power(X1 - 5, 2) + 2 * Power(X2 - 3, 2);

end;

⇐ Предыдущая123Следующая ⇒

Поделиться: