Локальный случайный поиск по статистическому градиенту.

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

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

При наличии случайных параметров регулярную функцию качества представим в виде случайной функции

где — вектор состояний поиска; — вектор случайных помех.

Зная вероятностные характеристики параметров например плотность распределения можно осреднить функцию по этим параметрам и перейти вновь к осредненной регулярной функции качества

или

где — математическое ожидание.

Из (11.46) можно сделать вывод о том, что получение функции качества в детерминированном виде связано с необходимостью вычисления интеграла либо при жестких ограничениях на характер случайных воздействий либо при известных вероятностных характеристиках изменения таких воздействий. Однако обычно имеется только информация об отдельных реализациях случайной функции .

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

В результате замены на условия экстремума принимают следующий вид:

или, учитывая линейность операций, можно записать

Осуществляя итеративную процедуру стохастической аппроксимации, определяем состояние х, соответствующее экстремальному значению , постепенно приближаясь к нему:

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

В том случае, если представима в виде скалярной функции скалярного аргумента х и случайного параметра процедура стохастической аппроксимации сводится к процедуре определения корня этой скалярной функции или к так называемой процедуре Роббинса—Монро.

Пусть

где — скалярная функция от параметра состояния х

Функцию можно представить в виде суммы регулярной составляющей и случайной составляющей причем математическое ожидание т. е. случайная составляющая центрирована.

В результате поиска определяют корень х регулярной составляющей т. е.

в соответствии с процедурой

где а — знак наклона регулярной составляющей в точке х (для минимума для максимума а — постоянная, определяющая наклон аппроксимированной прямой к

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

где — интервал оценки производной, то поиск экстремума функции сводится к поиску корня функции регрессии регулярной части в соответствии с процедурой Кифера—Вольфовица:

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

После этого вычисляется вектор статистической оценки градиента в точке т. е.

Рис. 11.11

В пределе при статистическая оценка совпадает с направлением градиента функции качества, поэтому рабочий шаг производится в направлении полученной оценки

где - норма вектора статистического градиента; а — величина рабочего шага.

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