Автоматика и телемеханика, № 5, 2015
© 2015 г. О.Н. ГРАНИЧИН, д-р физ.-мат. наук (oleg_granichin@mail.ru) (Санкт-Петербургский государственный университет)
ПОИСКОВЫЕ АЛГОРИТМЫ СТОХАСТИЧЕСКОЙ АППРОКСИМАЦИИ С РАНДОМИЗАЦИЕЙ НА ВХОДЕ1
В статье наряду с детальным обзором развития псевдоградиентных алгоритмов стохастической аппроксимации с рандомизированными возмущениями на входе рассматривается вопрос об их применимости в оптимизационных задачах с линейными ограничениями и обсуждаются новые возможности их применения для мультиагентного управления при балансировке загрузки узлов вычислительных сетей. Обоснования состоятельности алгоритмов и их оптимальной скорости сходимости опираются на основополагающие работы Б.Т. Поляка.
1. Введение
Развитие средств контроля и вычислительной техники позволяет в настоящее время перейти к решению многих практических задач "на лету", встраивая "умные" блоки в контуры управления простых и сложных систем, в технологические процессы, в разнообразные системы поддержки принятия решений и т.п. В приложениях важную роль играют решения задач оптимизации [1].
Использование математических методов неразрывно связано с формированием моделей исследуемых явлений, представляющих собой только приближение реальных процессов. Допустимый класс неопределенностей в модели и скорость работы алгоритма оптимизации — ключевые вопросы обоснования того или иного оптимизационного метода. Типичным подходом в теории является выбор близкой к реальным процессам математической модели и включение в нее различных помех, относящихся, с одной стороны, к грубости математической модели и, с другой — характеризующих неконтролируемые внешние возмущения объекта или системы [2]. При рассмотрении проблем оптимизации стохастическая постановка не только является наиболее адекватной реальным процессам, но и часто позволяет предлагать обоснованные решения для вычислительно "сложных" или плохо обоснованных задач.
Традиционные методы описания динамических систем предполагают выбор некоторого пространства состояний X С М^, ^ € М, и составление уравнения динамики
х = А(х, и, -ш, в)
для зависящей от времени переменной состояния х € X. Управляющая переменная и характеризует контролируемые внешние воздействия на систему (играет роль "посредника" с внешним миром), неконтролируемые воздействия
1 Работа выполнена при поддержке Министерства образования и науки РФ (УИН RFMEFI60414X0035).
характеризуются переменной w. Вид уравнений динамики обычно задается с точностью до некоторого набора констант 9 € В (обычно конечномерного), называемого параметрами системы.
После удачного и обоснованного выбора математической модели одной из основных задач, возникающих при анализе динамических систем, является получение или уточнение информации о реальных параметрах системы (идентификация системы). Эта информация может в дальнейшем использоваться при прогнозировании поведения системы или при формировании закона управления. Для всех математических моделей результатом эксперимента является математический объект — число, множество чисел, кривая и т.п. Наряду с описанием динамики процесса выбирают ту или иную модель наблюдений. Любые измерения дают всегда значения величин, заведомо усредненные как по некоторой пространственной области, так и по некоторому промежутку времени. Обычно набор наблюдений у в момент времени Т может быть представлен как двойной интеграл по некоторому условному распределению Ру(■)
т
у = J йг^ Ру(^х|
т-6 м
где продолжительность интервала времени 5 и некоторое подмножество пространства состояний М С X (часто М С дХ ) определяются характеристиками регистрирующих приборов. Принципы построения современных вычислительных устройств наиболее адекватны обработке последовательных наблюдений, получаемых в дискретные моменты времени. После дискретизации и некоторых упрощающих предположений для модели наблюдений можно получить выражение вида
уг = Вг(хг, и, wt, 9) + Уг, г = 1, 2,...,
в котором Вг(-) — некоторые функции, а у = щ + Уг(9) понимается как стандартная ошибка в наблюдении (помеха), состоящая обычно из статистической (случайной) погрешности и систематической -йг (погрешности модели). О неконтролируемых воздействиях на систему wt также обычно делаются стандартные статистические предположения. В этом случае статистическую погрешность Уг можно включить как дополнительный компонент в wt, а можно по смыслу отождествлять с систематической погрешностью -йг. В противовес статистическим погрешностям wt о систематических обычно делаются предположения только об ограниченности, а в остальном они могут быть произвольными.
Возможна ли постановка задачи об идентификации неизвестных параметров системы при произвольных систематических внешних погрешностях?
Далее будет описан один из возможных подходов, позволяющих с оптимизмом смотреть на перспективы решения такого типа задач. Ключевой особенностью этого подхода является возможность включения рандомизации в модель таким образом, чтобы она была независимой с внешними помехами. Для рассмотренной выше модели динамики "в быстром времени" без су-
щественного ограничения общности систематическую погрешность можно рассматривать как внешнюю помеху, которая не связана с изменением текущих (мгновенных) переменных системы.
Другая проблема, с которой сталкиваются при синтезе законов управления, — недостаточная вариативность последовательности наблюдений: "■управляющие воздействия должны быть направляющими, но в известной мере и изучающими" (А.А. Фельдбаум, [3]). Например, если цель адаптивного управления состоит в минимизации отклонения вектора состояния системы от заданной траектории, то это часто приводит к вырожденной последовательности наблюдений. В то время как для успешного проведения идентификации неизвестных параметров системы должно быть обеспечено "разнообразие" наблюдений.
Теория оценивания неизвестных параметров при статистических неопределенностях достаточно хорошо развита [4, 5]. Трудности в использовании стандартных подходов приводят к необходимости поиска алгоритмов, работоспособных при минимальных предположениях о статистических свойствах помех. Альтернативой являются методы, использующие оценки множеств, гарантированно содержащих неизвестные параметры [6-9], но доставляемые такими методами решения зачастую слишком консервативны.
В последнее время в научной литературе активно развиваются рандомизированные методы решения [10-13]. С одной стороны, в задачах требующих большого объема "перебора" вариантов алгоритмы, основанные на случайном выборе, позволяют за ограниченное время добиваться хороших результатов с определенной вероятностью. С другой стороны, возможность рандомизации процессов наблюдений позволяет во многих случаях компенсировать негативное влияние систематических внешних погрешностей.
Статья организована следующим образом. После введения следует раздел, в котором представлена история развития псевдоградиентных алгоритмов стохастической аппроксимации (СА). Далее в разделе 3 дается постановка задачи об оптимизации нестационарного функционала типа среднего риска при линейных ограничениях, предлагается модернизированный вариант поискового алгоритма СА с двумя измерениями на каждой итерации и с рандомизированными возмущениями на входе, формулируются основные предположения и основной теоретический результат статьи о слабой верхней оценке предельной невязки при ограниченных характеристиках дрейфа параметров и почти произвольных внешних помехах в наблюдениях. В разделе 4 рассматривается пример балансировки загрузки узлов вычислительной сети с использованием поискового алгоритма СА с двумя измерениями на каждой итерации и с рандомизированными возмущениями на входе. В заключении перечислены пять замечательных характеристик рассматриваемых в работе алгоритмов.
2. Псевдоградиентные алгоритмы стохастической аппроксимации
Алгоритм стохастической аппроксимации (СА) был предложен Роббинсом и Монро в 1951 г. [14], в следующем году он был развит Кифером и Воль-фовицем для решения задач оптимизации [15]. В 1954 г. алгоритм СА был
распространен Блюмом для многомерного случая [16]. При этом для случая оптимизации в d-мерном пространстве (в € Rd) традиционная процедура СА, которая основана на конечно-разностных аппроксимациях вектора-градиента исследуемой функции, использует на каждой итерации 2d наблюдений для построения последовательной оценки (два наблюдения для приближения каждой из компонент d-мерного вектора-градиента). В конце 80-х -начале 90-х гг. XX в. автором в [17, 18] и Поляком с Цыбаковым в [19, 20] были предложены поисковые алгоритмы стохастической аппроксимации с рандомизацией на входе, которые используют на каждой итерации всего одно (или два) значение исследуемой функции в точке (или точках) на линии, проходящей через предшествующую оценку в случайно выбираемом направлении (как в алгоритме случайного поиска [21]). В англоязычной литературе похожие алгоритмы предложил использовать Спал [22, 23], назвав их SPSA (simultaneous perturbation stochastic approximation).
Алгоритмы СА, в которых изменение оценки на каждой итерации происходит в направлении, в среднем совпадающем с направлением вектора-градиента исследуемой функции, называются псевдоградиентными (или квазиградиентными ). Свойства сходимости псевдоградиентных алгоритмов СА в нелинейном (общем) случае детально исследованы в [24], а в линейном -в [25].
Алгоритмы СА первоначально появились как инструменты статистики, но позже выделились в отдельную область в теории управления [26]. В знаменитой лаборатории №7 ИПУ РАН исследовались применения псевдоградиентных алгоритмов СА в адаптации, при построении оптимальных и робастных алгоритмов [27-33]. Широкое международное признание получил "ускоряющий" алгоритм Поляка с усреднениями [34, 35]. Сейчас СА широко применяется в разнообразных приложениях в таких областях, как идентификация неизвестных параметров систем, адаптивное управление, адаптивная обработка сигналов, адаптивное размещение ресурсов в коммуникационных сетях и др.
Традиционно в алгоритмах СА предполагался в
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.