Методы случайного поиска
Алгоритм 1 (с возврaтом при неудaчном шaге). Шаг 0. Выбрать параметр точности e > 0, начальный шаг a >0, коэффициент уменьшения шага g >1, предельное число неудачных попыток N, начальную точку х. Вычислить f (х). Шаг 1. Положить счетчик числа неудачных попыток j= 1. Шаг 2. Получить реализацию случайного вектора x. Шаг 3. Найти пробную точку y=x+ax/||x||, вычислить f (у). Шаг 4. Если f (у)< f (х), то положить х = у, f (х) = f (у) и перейти к шагу 3. Иначе – перейти к шагу 5. Шаг 5. Положить j =j + 1. Если j < N, то перейти к шагу 2, иначе к шагу. Шаг 6. Проверка условия достижения точности. Если a < e, то поиск завершить, полагая х*=х, f *= f (х). Иначе – положить a = a/у и перейти к шагу 1. Иллюстрация построения последовательности (3.41) с помощью описанного алгоритма для функции двух переменных приведена на рис. 3.10, где пунктиром показаны неудачные попытки определения хk+1 из (3.41), не приводящие к уменьшению f (х).
Рис. 3.10. Иллюстрация работы алгоритма 1 в пространстве Е2. Замечание. На практике предельное число неудачных попыток N обычно полагают равным 3п, где п – число переменных целевой функции. Алгоритм 2 (наилучшей пробы). Этот алгоритм отличается от предыдущего только шагами 2 и 3: Шаг 2. Получить т реализации случайного вектора x: x1, …, xm Шаг 3. Найти пробные точки yi =
|
, i = 1,.., т, выделить f (уi). Найти уk из условия f (уk)= 
и положить у= уk.
