6.2.3.7. Стохастическая задача агрегации графа в соответствии с решением (6.2.18)

Рассмотрим для простоты следующую задачу:

отличающуюся от (6.2.18) детерминированным характером ограничений имеющих вид (6.2.15). В этом случае можно считать, что среда влияет лишь на матрицу связей графа, т. е.

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

Необходимо решить (6.2.78), располагая только наблюдениями Это обычная адаптация, которая состоит в том, что на каждом этапе решается задача

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

(более общий случай выводится аналогично). Здесь X — случайная матрица характеризующая конкретное состояние среды

Бернуллиевская модель предполагает независимость весов графа. Матрица X в этом случае имеет независимые случайные элементы, стохастические свойства которых должны быть заданы при моделировании. Генерирование случайных графов; Г здесь не вызывает трудностей.

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

Таким образом, задавая стохастическую матрицу

марковской цепи, можно легко генерировать случайные матрицы X, характеризующие случайные реализации графа Г. Легко заметить, что матрица X является смещенной оценкой стохастической матрицы Р. Действительно,

где

Такая модель позволяет удобно анализировать процесс получения оптимального разрезания графа адаптивным методом, опирающимся на наблюдения Применяя в данном случае на каждом этапе алгоритм, рассмотренный в предыдущем подразделе (см. рис. 6.2.8), можно быть уверенным, что этот процесс сойдется к оптимальному разрезанию, решающему задачу (6.2.78).

Проиллюстрируем сказанное на нескольких экспериментальных примерах.

Рис. 6.2.9. Структура стохастической матрицы взаимосвязей вершин графа в экспериментах (примеры 1-3 п. 6.2.3.7).

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

Оптимальная агрегация априори очевидна:

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

где — число вершин графа, которое на шаге совпадает с оптимальной агрегацией

В экспериментах ресурсы С не ограничивались и объем Т составлял 128, т. е. матрица (6.2.82) строилась на базе 128 элементов марковской цепи.

Пример Исходная агрегация имела три сегмента:

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

Пример Начальная агрегация, как и в предыдущем примере, была трехсегментной (6.2.87).

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

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

Таблица 6.2.3. (см. скан)

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

Пример 3. . Начальные условия (6.2.88) сохраняются. Результаты работы алгоритма адаптации приведены в табл. 6.2.3. Любопытно, что критерий качества агрегации изменялся незначительно ввиду большой связности оптимальной сегментации, которая, тем не менее, была найдена за восемь этапов адаптации.

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

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