Сформулируйте алгоритм случайного поиска с возвратом.

Выбираем случайную точку X⁰, считаем в ней значение функции, задаем постоянный шаг h. Из этой точки делаем в случайном направлении пробный шаг (h), ну и считаем значение функции в получившейся точке (назовём её X¹), дальше сравниваем значения функции в предыдущей точке и в текущей. Если шаг удачный, то он считается рабочим (то есть новый шаг мы будем делать из точки X¹), иначе происходит возврат в точку X⁰ и снова делается пробный шаг, и так до тех пор, пока не найдет то что ищем.

Это был в общих словах алгоритм поиска, теперь всякие примечания, дополнения и тому подобные вещи (Вдруг кому интересно):

∆X^k+1 = h ξ, шаг удачный

-∆X, шаг неудачный

Где ξ = (ξ₁,..,ξ_n), где ξ_i - нормированные случайные числа, такие что i² = 1

Вектор ξ равномерно распределен в n-мерном пространстве, т.е. отдельные реализации этого вектора направлены равновероятно во всех направлениях пространства параметров.

Для выполнения условия i² = 1 элементы вектора нормируют, используя соотношение ξ_i =

, где ξ_i⁰— случайные числа, равномерно распределенные в интервале (-1,1)

Эти числа получают масштабированием случайных чисел r_i, равномерно распределенных в интервале (0, 1), в соответствии с формулой: ξ_i⁰ = -1+2r_i

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

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

Если целевая функция является линейной, то неудачный шаг можно использовать для нового шага в направлении, противоположном неблагоприятному. Такой алгоритм называется поиском с линейным пересчетом.

При неудачном j -ом шаге, новым центром поиска служит точка X_j+1=X_j -2∆X_j

Дата добавления: 2015-11-14