Метод случайного поиска. Алгоритм статистического градиента.

Особенность метода в том, что в процессе вычисления приближений x^k используются случайные вектора в качестве направления движения. Например,

x^{k + 1} = x^k + α_kξ, k=0,1,..., (1)

где α^k > 0 – длина шага, ξ = (ξ1,..., ξn) – реализация n-мерной случайной величины ξ с заданным распределением. Например, ξi – независимые случайные величины, равномерно распределенные на отрезке [-1, 1]. Т.о, любая реализация метода случайного поиска использует генератор случайных чисел, который по любому запросу выдает реализацию случайного вектора ξ с заданной функцией распределения.

Рассмотрим задачу f(x) → min_x∈Q, где Q⊆Rⁿ_. Пусть известно k-ое приближение x^k∈Q, k=0,1,….

Решение по алгоритму статистического градиента.

Пусть ξ1,..., ξs – реализации случайного вектора ξ. Вычислить разности для всех , . Пусть

Если , то . В противном случае выбрать новый набор ξ’1,..., ξ’s реализаций случайного вектора ξ и повторить действия.

Величины s>1, a>0, g>0 – параметры алгоритма, γ – длина шага сетки. Вектор p_k – статистический градиент. Если Q=Rⁿ,s=n и векторы ξi равны единичным векторам e_i, i=1,…, s, то данный алгоритм оказывается разностным аналогом градиентного метода.

Так как функция распределения случайного вектора ξ не зависит от номера итерации, то предложенные выше варианты метода случайного поиска называют методами случайного поиска без обучения. Эти алгоритмы не обладают способностью учитывать результаты предыдущих итераций и, обнаруживать более перспективные направления убывания минимизируемой функции. Как результат, они медленно сходятся. Методы случайного поиска, которые обладают способностью приспосабливаться к конкретным особенностям минимизируемой функции, назовем методами случайного поиска с обучением. Так как в этом случае функция распределения вектора ξ пересчитывается в зависимости от номера итерации и предыдущих результатов, то итерационный процесс (1) записывается теперь в виде

x^{k + 1} = x^k + α_kξ _k, k=0,1,..., (2)

На нулевой итерации функция распределения вектора ξ выбирается с учетом априорной информации о целевой функции. Если такая информация недоступна, то нулевую итерацию начинают со случайного вектора

ξ⁰ = (ξ⁰₁,..., ξ⁰_n), где ξ⁰₁,..., ξ⁰_n – независимые случайные величины, равномерно распределенные на отрезке [- 1, 1].

Не нашли, что искали? Воспользуйтесь поиском: