Стратегии поиска.

Существуют две различные стратегии выбора точек, в которых производится вычисление значений функции. Если все точки задаются заранее, до начала вычислений, - это пассивная (параллельная) стратегия. Если эти точки выбираются последовательно в процессе поиска с учетом результатов предыдущих вычислений, - это последовательная стратегия. Примером реализации пассивной стратегии является метод равномерного поиска, примером последовательной стратегии является метод дихотомии.

Стратегия поиска включает в себя три этапа:

1. выбор начального интервала неопределенности. Границы [a₀, b₀] интервала должны быть такими, чтобы функция f(x) была унимодальной.

2. Уменьшение интервала неопределенности.

3. Проверку условия окончания. Поиск заканчивается, когда длина текущего интервала неопределенности [a_к, b_к] оказывается меньше установленной величины.

Ответом является множество точек, принадлежащих последнему интервалу неопределенности, среди которых каким-либо образом выбирается решение задачи x^*.

В некоторых методах заранее задается или находится количество N вычислений функции. В этом случае продолжительность поиска ограничена (пассивная стратегия).

Для эвристического выбора начального интервала неопределенности применяется алгоритм Свенна.

Алгоритм Свенна:

1) задать произвольно следующие параметры: x₀ - некоторую точку, t > 0 - величину шага. Положить k=0;

2) вычислить значение функции в трех точках: x₀ - t, x₀, x₀+ t;

3) проверить условие окончания:

а) если , то начальный интервал неопределенности найден:

;

б) если , то функция не является унимодальной, а требуемый интервал неопределенности не может быть найден. Вычисления при этом прекращаются (рекомендуется задать другую начальную точку x₀);

в) если условие окончания не выполняется, то перейти к шагу 4;

4) определить величину:

а) если , то ; a₀ = x₀; x₁ = x₀ + t; k=1;

б) если , то ; b₀ = x₀; x₀ = x₀ - t; k=1;

5) найти следующую точку ;

6) проверить условие убывания функции:

а) если f(x_k+1) < f(x_k) и , то а₀ = x_k;

если f(x_k+1) < f(x_k) и , то b₀ = x_k;

в обоих случаях положить k=k+1 и перейти к шагу 5;

б) если , то процедура завершается.

При положить b₀ = x _k+1, а при положить a₀ = x _k+1.

В результате имеем [a₀, b₀] - искомый начальный интервал неопределенности.

Для оценки эффективности алгоритмов уменьшения интервала неопределенности при заданном числе N вычислений функции введем критерий.

Определение 2. Характеристикой R(N) относительного уменьшения начального интервала неопределенности называется отношение длины интервала, получаемого в результате N вычислений функции, к длине начального интервала неопределенности:

Пример1. Найти начальный интервал неопределенности для поиска минимума функции f(x)=(x-5)²

Воспользуемся алгоритмом Свенна.

1. Зададим x₀=1, t=1. Положим k=0.

2⁰. Вычислим значения функции в точках x₀- t =0, x₀=1, x₀ + t =2:

f(0)=25, f(1)=16, f(2)=9.

3⁰. - условия окончания не выполняются. Переходим к шагу 4.

4⁰. Так как f(0)>f(1)>f(2), то ; a₀=1; x₁=x₀+ t =2; k=1

5⁰. Найдем следующую точку .

6⁰. f(x₂)=(4-5)²=1, f(x₁)= (2-5)²=9. Так как f(x₂)=1 < f(x₁) и , то a₀=x₁=2.

Положим k=2 и перейдем к шагу 5.

5¹. Найдем следующую точку .

6¹. Так как f(x₃)=9 > f(x₂)=1 и , то поиск завершен и правая граница b₀=x₃=8.

Поэтому начальный интервал неопределенности имеет вид [a₀, b₀]=[2, 8].

Метод равномерного поиска