§ 6.2. Адаптивная агрегация графов [291]

6.2.1. Постановка задачи

Пусть имеется ориентированный граф, определяемый парой

Здесь А — конечное множество вершин графа, каждая из которых имеет вес

— вес вершины; В — множество ребер, каждое из которых определяется своим весом. Эти веса образуют матрицу

где — вес ребра, связывающего вершину с Нулевой вес соответствует отсутствию ребра.

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

Это состояние изменяется во времени непредсказуемым об разом, т. е.

Введем агрегированный граф

который получается из Г (6.2.1) путем объединения его вершин:

где

— множество номеров вершин графа Г, объединенных (агретированных) в одну вершину а) графа

— матрица графа Г, где

Как видно, агрегация определяется однозначно:

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

при соблюдении ограничений на веса его вершин:

где

— заданные верхние границы весов агрегированного графа Г, которые определяются выделенными ресурсами.

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

где ограничения имеют вид

Решение этой задачи естественно назвать оптимальной агрегацией. Она должна изменяться во времени ввиду изменения свойств среды X, влияющей на веса вершин и ребер (6.2.4) исходногр графа.

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

Если свойства среды неизменны, т. е. то задача адаптации сводится к оптимизационной задаче (6.2.14), которую обычно называют задачей о разрезании графа.

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

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

Далее, рассматриваемая задача является типичной задачей структурной адаптации, поскольку полностью отсутствуют непрерывные составляющие в решении

И наконец, это типичная задача эволюционной адаптации (см. § 1.5), так как при незначительном изменении агрегации (например, при «перебросе» одной вершины) минимизируемая функция изменится также незначительно, что позволяет воспользоваться поисковым методом при отыскании оптимальной агрегации.

Рассмотренная постановка задачи имеет детерминированный характер, так как изменение состояния среды X однозначно определяет параметры (6.2.4) задачи.

Однако часто имеет место стохастическая среда, состояние которой изменяется определенным, но известным стохастическим образом где — плотность распределения измеряемых состояний среды. При этом естественно осреднить критерий (6.2.11) и ограничения (6.2.12) по X:

Теперь задача синтеза оптимальной агрегации принимает вид

где ограничение может иметь различный вид. Например: ограничение путем осреднения

где

и

ограничение по максимуму

где

и

и т. д. — в зависимости от содержательной постановки решаемой задачи.

Задачу (6.2.18) называют задачей стохастического программирования: ее минимизируемый критерий и ограничения являются стохастическими характеристиками, зависящими от свойств среды, т. е. от Неопределенность свойств среды исключает использование методов математического программирования и заставляет искать другие пути решения задачи (6.2.18). Адаптация является, пожалуй, единственным надежным способом решения этой сложной задачи.