6.2.3.8. Адаптивная агрегация графа, функционирующего в нестационарной среде

Здесь оптимальная агрегация изменяется во времени, т. е. агрегированный граф эволюционирует вместе со средой:

Алгоритм адаптивной агрегации (см. рис. 6.2.8) должен «отслеживать» этот дрейф оптимальной агрегации.

Пример. Дрейф матрицы переходных вероятностей моделировался путем изменения границ вероятностей (рис. 6.2.10) таким образом, что каждый сегмент при оптимальном разрезании содержал всегда восемь смежных вершин (первая и шестнадцатая вершины смежные). На рис. 6.2.10 пунктиром показано очередное состояние матрицы, а стрелкой — направление дрейфа границ. Буквой обозначен промежуток между строкой (столбцом). Дрейф матрицы представляется следующей формулой:

Скорость этого дрейфа была выбрана равной вершинам, меняющим принадлежность к сегменту за один этап работы локального алгоритма агрегации. Матрица реализации строилась на базе 128 шагов марковской цепи при равновероятно выбранной начальной вершине. Ресурсы С не ограничивались.

Результаты проведенных экспериментов (табл. 6.2.4) показывают, что оптимальная агрегация находилась на каждом этапе работы алгоритма. Здесь — исходное значение коэффициента соответствия с оптимальной агрегацией на этапе, а k — значение этого коэффициента после агрегации (оно всегда было равно 1). Стрелками показаны переходы состояний графа.

На рис. 6.2.11 показано поведение минимизируемого критерия в процессе агрегации. Здесь — моменты пересегментации (т. е. использования одной из операций ), N — моменты скачкообразного дрейфа матрицы на величину после полной обработки алгоритма

Рис. 6.2.10. Схема дрейфа матрицы переходов марковской цепи (пример п. 6.2.3.8).

(кликните для просмотра скана)

Рис. 6.2.11. Поведение критерия качества агрегации в процессе дрейфа при адаптивной агрегации.

агрегации. Пунктиром показано поведение критерия без адаптации.

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