Методы случайного поиска

Основой для этого метода служит итерационный процесс.

х=х+, k=0,1,… (1)

где >0 – величина шага; =(,…,) – некоторая реализация n-мерного вектора . Будем считать, что координаты вектора - это независимые случайные величины, равномерно распределенные на [-1;1].

Приведем алгоритм метода случайного поиска. Он может использоваться как самостоятельная min-ая процедура или входить в состав других алгоритмов.

Алгоритм с возвратом при неудачном шаге.

ШАГ 0:

Выбрать параметр точности >0, начальный шаг >0, коэффициент уменьшения шага >1, предельное число неудачных попыток N, начальную точку Х. Вычислить f(x).

ШАГ1:

Положить счетчик числа неудачных попыток j=1.

ШАГ2:

Получить реализацию случайного вектора .

ШАГ3:

Найти пробную точку y=х+, вычислить f(y).

ШАГ4:

Если f(y)<f(x), то положить х=у, f(x)=f(y) и перейти к шагу 3. Иначе – к шагу 5

ШАГ5:

Положить j=j+1. Если jN, то перейти к шагу 2, иначе – к шагу 6.

ШАГ6:

Проверка условия достижения точности. Если <, то поиск завершить, полагая х*=х, f*=f(x). Иначе – положить =/и перейти к шагу 1.

Иллюстрация работы алгоритма в производстве Е.

Пунктиром показаны неудачные попытки определения точки хиз (1), не приводящие к уменьшению f(x).

Замечание:

На практике предельное число неудачных попыток N обычно полагают равными 3n, где n-число переменных целевой функции.

Дата добавления: 2014-01-07