Диссертация (1150919), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

(При неизвестной матрице Ai параллельно с вектором состояний оценивают и самуматрицу Ai ).Пусть xbit — оптимальная оценка xit в момент времени t, Γit — ковариационная матрица ошибки оценки xbitΓit = E(bxit − xit )(bxit − xit )T .MiОбозначим Yt t — агрегированный вектор наблюдений всех сенсоровиз группы Mti . В силу модели наблюдений (2.1) можем записать(1.5)MtiYtiMii= BMt xit + Vt t , BMt . .. Mi =  B j  Vt t = ..... .vti,j  ....Фильтр Калмана задается соотношениями(1.6)MiMiixbt+1 = Ai xbt − Kt t (BMt xbit − Yt t ) =...Mi  P= Ai xbt − Kt t  j∈Mti Bj xbit − yti,j  ,...(1.7)MiiΓit+1 = Ai Γit (Ai )T − Kt t BMt Γit (Ai )T + Riw ,Miгде матричные функции Kt t , называемые калмановскими коэффициен-20тами усиления, определяется по формулеMtiMiiii= Ai Γit (BMt )T (Qt t + BMt Γit (BMt )T )−1 ,KtMtiQt ... 0MiMi= EVt t (Vt t )T =  0 Qi,jt0000 ....Используя матричное тождество рекуррентные соотношения для матриц Γit можно переписать в видеMiMiiMiiMiMiΓit+1 = (Ai − Kt t BMt )Γit (Ai − Kt t BMt )T + Kt t Qt t (Kt t )T + Riw ,илиMiiiiiΓit+1 = Ai (Γit − Γit (BMt )T (Qt t + BMt Γit (BMt )T )−1 BMt Γit (Ai )T + Riw .(Детальный вывод формул (1.6)-(1.7) и соотношений для Γit+1 можнонайти в [9]).Функционал (1.3) принимает вид:(1.8)Φt ({Mti })=Xcosts (mj({Mti }))+j∈NXT r[Γit+1 ] + costc · |Mti |,i∈Mгде T r[·] — след матрицы.Так как первое и последнее слагаемые в (1.7) не зависят от Mti , томинимизация функционала (1.8) эквивалентна решению следующей задачи(1.9)Φ0t ({Mti }) =Xcosts (mj ({Mti })) +j∈N+costc ·XMii∈M|Mti |=Xcosts (mj ({Mti }))+j∈N21iT r[−Kt t BMt Γit (Ai )T ]++XMiMiiMiiT r[−(Gt t )T (Qt t + BMt Γit (BMt )T )−1 Gt t ] + costc · |Mti | → min,i{Mt }i∈MMtiгде обозначено Gti= BMt Γit (Ai )T .Обратимся к (1.5).

Размер блочной матрицы BMtiравенmi,tPmyj × nxi .j=1Таким образом, в каждый момент времени t при вычислении матрицыmmi,ti,tPPMtiKt требуется обращать матрицу размераmyj × myj , что при больj=1j=1шом значении mi,t требует существенных вычислительных затрат. Исходя из этой проблемы, необходимо разработать методы, с помощью которых можно оценивать состояния движущихся объектов при большомколичестве как объектов слежения, так и наблюдателей.В [19] было исследовано применение рандомизированного подхода наряду с фильтром Калмана для решения указанной проблемы. В результате исследования было показано, что если использовать только некоторуючасть измерений в процедуре оценивания, можно понизить требования квычислительным ресурсам устройств и при этом незначительно потерятьв качестве оценивания. На базе этой идеи в диссертации предложена модификация поискового алгоритма стохастической аппроксимации, сутькоторой состоит в оценивании только некоторой части всего вектора параметров.Количество отслеживаемых объектов обычно заранее неизвестно.

Кроме того, дополнительную трудность представляет присвоение разнымисенсорами одинаковых номеров объектов. После выбора алгоритма разбиения на группы для определения точного количества объектов можно воспользоваться тем или иным алгоритмом устойчивой кластеризации. На начальной стадии можно использовать алгоритм K-means (илиGM M -clustering) для разбиения множества {y0i,j } последовательно на Kкластеров (K = 1, 2, .

. . , Kmax ) и вычисления для каждого K соответствующей функции дисторсии, вычисляющей отношение максимального размера кластера к минимальному расстоянию между кластерами.Обычно точка изгиба этой функции соответствует истинному значению22количества кластеров. Более подробно методы машинного обучения, вчастности кластеризации, рассмотрены в работах [3, 21, 57].Далее рассмотрим подробнее класс алгоритмов стохастической аппроксимации.1.1.2Стохастическая аппроксимацияНесмотря на такие преимущества использования распределенных систем как большая гибкость, адаптируемость и надежность, на практикерешение осложняется наличием ряда трудностей, среди которых ограничения пропускной способности каналов данных, помехи при передачи данных, сетевые задержки, обрывы связей между наблюдателями,ограниченные вычилительные возможности.

Для решения задач в условиях неопределенностей активно используются методы стохастическойоптимизации. Как правило, цель оптимизации состоит в минимизации(максимизации) некоторого функционала F (θ) по отношению к неизвестному параметру системы θ. Во многих практических приложенияхсущественным ограничением является отсутствие возможности аналитического вычисления значений функции F (θ). В этом случае экспериментатору могут быть доступны лишь зашумленные значения этой функциив выбранных точках. В противовес детерминированной оптимизации,где аналитическая форма функционала известна и процесс оптимизацииполностью детерминирован, процесс стохастической оптимизации включает в себя некоторую случайную составляющую (например, алгоритмоптимизации использует зашумленные значения функции F (θ) или накаждой итерации следующий шаг делается в случайном направлении).Одним из важных классов методов, применяемых в стохастическойоптимизации, является стохастическая аппроксимация.

Изначально, этотметод был введен Г. Роббинсом и С. Монро в 1951 году [92], и получил свое дальнейшее развитие в работе Дж. Кифера и Дж. Вольфовицадля решения задач оптимизации [65]. В 1954 году алгоритм стохастической аппроксимации был расширен Дж. Р. Блюмом на многомерный23случай [47]. В этом случае для оптимизации в d-мерном пространствеобычная процедура алгоритма, базирующаяся на конечно-разностныхаппроксимациях градиента функции, при конструировании последовательности оценок использует 2d наблюдений на каждой итерации (дванаблюдения для аппроксимации каждой компоненты d-мерного вектораградиента).

В конце 1980-х и начале 1990-х Н. О. Граничин [11,12] и Б. Т.Поляк с А. Б. Цыбаковым [32, 86] предложили использовать поисковыеалгоритмы стохастической аппроксимации с рандомизацией на входе, которые используют на каждой итерации только одно (или два) значенияисследуемой функции в точке (или точках) на линии, проходящей черезпредыдущую оценку в случайно выбранном направлении. В западной литературе похожие алгоритмы предложил Дж. С. Спалл [96, 97], назвавих “одновременно возмущаемая стохастическая аппроксимация” (англ.Simultaneous Perturbation Stochastic Approximation, SPSA).Приведем общие процедуры поискового алгоритма стохастическойаппроксимации из [9].

Пусть пробное одновременное возмущение ∆n , n =1, 2, . . . — наблюдаемая последовательность независимых случайных векторов из Rd с функциями распределения Pn (·), {αn } и {βn } — последовательности положительных чисел, стремящихся к нулю, θ̂0 ∈ Rd —фиксированный начальный вектор. Для построения последовательноститочек измерений {xn } и оценок θ̂n рассматриваются алгоритмы с однимнаблюдением:x = θ̂nn−1 + βn ∆n , yn = Fwn (xn ) + vn ,(1.10)θˆn = θ̂n−1 − αn Kn (∆n )yn ,βnили с двумя наблюдениями:x = θ̂2nn−1 + βn ∆n , x2n−1 = θ̂n−1 − βn ∆n ,(1.11)θˆn = θ̂n−1 − αn Kn (∆n )(y2n − y2n−1 ),2βnгде Kn (·) : Rd → Rd — некоторые вектор-функции (ядра), Fwn (xn ) —24исследуемая функция, {wn } — неконтроллируемая последовательностьслучайных величин, vn — аддитивные помехи.Как правило, решение задачи стохастической оптимизации в условиях неопределенностей подразумевает нахождение такого набора параметров системы, при котором достигается минимальное или максимальное значение некоторого функционала среднего риска, который впрактических приложениях зачастую может иметь разный вид в процессе функционирования системы.

Такие функционалы будем называтьдалее нестационарными. При анализе систем точки, в которых функционал достигает оптимального значения, часто связывают с некоторыминоминальными значениями параметров системы. При нестационарномфункционале среднего риска говорят о задаче отслеживания изменений параметров системы. Для оптимизации функционалов типа среднегориска активно используются оценки метода максимального правдоподобия и алгоритмы стохастической аппроксимации с убывающим до нуляразмером шага [47, 65, 92].

Д. П. Деревицкий и А. Л. Фрадков в [15, 16]при анализе динамики алгоритмов адаптации, основанном на построенииприближенных усредненных моделей, обосновали возможность использования алгоритмов стохастической аппроксимации с неубывающим донуля размером шага. Позже рандомизированные алгоритмы стохастической аппроксимации с пробным одновременным возмущением на входеи неубывающим до нуля размером шага использовались для решениязадач оптимизации нестационарных функционалов в [7, 8, 55, 114].

В статьях Н. О. Амелиной, А. Л. Фрадкова и соавторов [1, 2, 39] для агентовв сети с нелинейной динамикой состояний при случайно изменяющейсяструктуре связей и наблюдениях со случайными задержками и помехамис помощью метода усредненных моделей исследовались алгоритмы консенсусного мультиагентного децентрализованного управления загрузкойсети, основанные на методе стохастической аппроксимации с неубывающим до нуля размером шага.Поисковой алгоритм стохастической аппроксимации допускает параллельное или распределенное исполнение.

Цель распределенной опти25мизации обычно состоит в нахождении минимума или максимума некоторой целевой функцииf¯(x) =nXf j (x)j=1посредством взаимодействия между агентами. Здесь x ∈ Rd — векторрешения, а f j (x) : Rd → R представляет собой целевую функцию (функцию потерь) агента j, которая в общем случае известна только ему.

Появление распределенных алгоритмов оптимизации можно проследить достатей 70-х и 80-х годов [41,50,103]. На сегодняшний день существует рядподходов для случая, когда функция f j (x) является выпуклой. В частности, был предложен “метод попеременного направления множителей”(англ. Alternating Direction Method of Multipliers) [43], а также субградиентный метод [78,93]. Для невыпуклых задач в работах [51,115] получилразвитие большой класс распределенных алгоритмов на основе использования различных “функционально-суррогатных модулей”. Для случаев,когда градиент целевой функции неизвествен, либо может быть измерен только приближенно (зашумлен), методы стохастической аппроксимации используются в [48, 112, 113].

Характеристики

Список файлов диссертации