3.3.2. Алгоритм наилучшей пробы

Этот алгоритм отличается от предыдущего тем, что на каждой итерации с помощью датчика случайных чисел формируется некоторое заданное количество s реализаций ¹,…,^sслучайного вектора  и вычисляются значения функции f(X) в тех пробных точках

Y^j= X^k+ ^j, j=1,…,s, (3.22)

которые принадлежат допустимой области R. Если все эти точки оказываются вне области R, то пробы повторяются с уменьшенным значением . В качестве очередного (k+1)–го приближения выбирается пробная точка, в которой значение функции оказалось наименьшим. Таким образом, (k+1)-я точка X^k+1 минимизирующей последовательности определяется из соотношения

f(X ^k+1)=min {f(Y^j) | Y^jR,1js}, (3.23)

т.е. рабочий шаг выполняется в направлении наилучшей пробы. Все остальные операции  те же, что и в предыдущем алгоритме.

Величины s1 и 0 являются параметрами данного алгоритма, выбором которых можно улучшить его сходимость.

3.3.3. Алгоритм статистичекого градиента

В этом алгоритме, как и в предыдущем, в начале каждой итерации выбирается s реализаций ¹,…,^S случайного вектора  и определяются пробные точки

Y^j= X^k+ ^j,

где 0 – величина пробного шага. Далее, для всех Y^jR вычисляются значения функции f(X) и составляются разности f ^j= f(X^k)  f(Y^j). Затем формируется новое направление

P^k = ,

где сумма берется только по тем j, 1js для которых Y^jR и по этому направлению делается шаг величиной .

Если точка X= X^k+P^k, полученная в результате этого шага, принадлежит допустимой области R, то полагают X^k+1=X и переходят к выполнению следующей итерации. Если же XR, то повторяют описанные построения с новым набором из s реализаций случайного вектора . Если все Y^jR, j=1,…,s то следует повторить пробы с уменьшенной величиной пробного шага .

Построенный таким образом вектор P^k называется статистическим градиентом. Такое название связано с тем, что в случае, когда REⁿ, s=n, ^j=e^j, где e^j– единичные координатные векторы, описанный алгоритм превращается в разностный аналог градиентного метода и направление P^k при 0 становится направлением антиградиента f(X) функции в точке X^k.

Величины s1, 0, 0 являются параметрами алгоритма, существенно влияющими на качество итерационной процедуры.

3.3.4. Порядок выполнения работы

1. Кратко описать рассмотренные варианты метода случайного поиска.

2. Составить рабочие алгоритмы для каждого из них.

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

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

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

3.3.5. Задания для лабораторной работы

Решить задачи нелинейного программирования

1. f(X)=x₁²+x₂²4x₁2x₂+5min; 2.f(X)=x₁²+x₂²16x₁10x₂+89min;

g₁(X)= x₁2x₂+1  0, g₁(X)= 2x₁²+12x9x₂+27  0,

g₂(X)= 0,25x₁²x₂²+1  0, g₂(X)= 5x₁²+16x₂+80  0,

g₃(X)= x₁ 0, g₄(X)= x₂  0. g₃(X)= x₁ 0, g₄(X)= x₂ 0.

3. f(X)=x₁²+x₂²14x₁4x₂+53min; 4. f(X)=x₁²+9x₂²10x₁18x₂+34min;

g₁(X)= 2x₁²25x₂+125  0, g₁(X)=x₁x₂+5  0,

g₂(X)= x₁²+2x₁+4x₂+3  0, g₂(X)= 0,5x₁²+x₂+4,50,

g₃(X)= x₁ 0, g₄(X)= x₂ 0. g₃(X)= x₁ 0, g₄(X)= x₂ 0.

5. f(X)=x₁²+4x₂²10x₁16x₂+41min; 6. f(X)=x₁²+4x₂²8x₁16x₂+32min;

g₁(X)= x₁²+4x₁x₂+1  0, g₁(X)= 2x₁²+4x₁+x₂1  0,

g₂(X)= x₁²+4x₁+3x₂3 0, g₂(X)= x₁x₂+10,

g₃(X)= x₁ 0, g₄(X)= x₂ 0. g₃(X)= x₁ 0, g₄(X)= x₂ 0.

7. f(X)=x₁²+x₂²4x₁2x₂+5min; 8. f(X)=x₁²+9x₂²10x₁36x₂+61min;

g₁(X)= x₁x₂+20, g₁(X)= x₁²+4 x₁4x₂+12 0,

g₂(X)= x₁²+x₂0, g₂(X)= 3x₁²+7x₂+270,

g₃(X)= x₁ 0, g₄(X)= x₂ 0. g₃(X)= x₁ 0, g₄(X)= x₂ 0.