Растригин Л.А. Адаптация сложных систем

Подождите немного. Документ загружается.

т. е. потенциальных «претендентов» на перевод в l-й сегмент. Если это

множество не пусто, то для каждого его элемента определяется

прирост критерия при переводе этого элемента в I

(6.2.60)

Если наименьшее приращение отрицательно, то оно и определяет

номер элемента

(6.2.61)

с которым следует произвести операцию первого рода ‹kil›, т. е.

перенести его из I

в I

Если же такого элемента не найдется, т. е. не удовлетворяются

условия (6.2.59) или ∆Q

>0, то следует образовать множество ,

удовлетворяющее условию

(6.2.62)

из которого выбрать элемент с номером

(6.2.63)

где

(6.2.64)

и произвести операцию

первого рода ‹ljk›.

Если же элемента, обладающего свойствами (6.2.62) и ∆Q

<0, не

найдется, то следует обратиться к операции второго рода.

4. Для этого организуется случайный перебор всех возможных

обменов между k-м и l-м сегментами. Пусть i — номер случайно

выбранного элемента из I

, а j — номер случайно выбранного

элемента из I

. Тогда при одновременном выполнении условий

≤ ∆a'

+ a

;

≤ ∆a'

+ a

; (6.2.65)

∆Q

< 0

(выведенных с использованием выражения (6.2.49)) производится

операция второго рода ‹kilj›, после чего снова стохастически

выбирается пара наиболее связанных сегментов (см. п. 1).

Естественно, что в процессе такого случайного перебора следует

отбрасывать уже проверенные варианты пар элементов,

не удовлетворяющие (6.2.65). После завершения случайного перебора

следует обратиться к случайному выбору наиболее связанной, но

другой случайной пары сегментов (см. п. 1).

Если ни одна из т(т—1)/2 пар сегментов, проверяемых подряд, не

дала улучшения критерия, то задачу локальной оптимизации можно

считать решенной (точнее, локально не улучшаемой).

Так как задача об оптимальном разрезании графа, вообще говоря,

имеет многоэкстремальный характер, то найденное оптимальное

решение локально и зависит от первоначального разрезания. Поэтому,

варьируя исходные агрегации, можно улучшить первоначальное

локальное решение.

Описанный алгоритм представлен в виде блок-схемы на рис. 6.2.4.

Его сходимость исследована в работе [271].

Детерминированный аналог этого алгоритма получается в случае,

когда оператор 1 случайного выбора заменяется на оператор выбора

пары сегментов с максимальной связностью, т. е.

(6.2.66)

Рис. 6.2.4. Блок-схема алгоритма поиска оптимального разрезания.

Пунктирная стрелка — для случая адаптивного разрезания (см. п.

6.2.3.6).

а оператор 2 случайного перебора — на выбор пары вершин,

обеспечивающих наиболее интенсивное уменьшение критерия:

(6.2.67)

где ∆Q

определено выше (6.2.49).

Такой детерминированный алгоритм рассмотрен в работе [224].

Преимущество случайного перебора перед полным (6.2.67) в данном

случае очевидно, так как условия (6.2.65) при случайном переборе

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

(6.2.67).

Приведем примеры работы этого алгоритма [115].

Пример 1. Рассмотрим граф с восемью вершинами (n=8) из работы

[27] (рис. 6.2.5). Матрица весов этого графа имеет вид

(6.2.68)

Веса вершин графа одинаковы и

равны единице (a

=l). Требуется

разрезать граф на два подграфа (т =

2) по четыре вершины в каждом (c

4).

Начальное разрезание выбирается

случайно, например:

(6.2.69)

и т. д.

Полученное с помощью описанного алгоритма оптимальное

разрезание имеет вид

(6.2.70)

и совпадает с полученным в работе [27], где

эта задача решена методом ветвей и границ (см. рис. 6.2.5).

Пример 2. В качестве другого примера рассмотрим задачу

определения оптимального сечения для устройства сопряжения двух

ЭВМ одного типа с несимметричным стыком [112]. Эта задача

сводится к задаче разрезания графа. Устройство

сопряжения представлено в виде неориентированного графа со

взвешенными ребрами (рис. 6.2.6). Вершина 19 — первая ЭВМ,

вершина 20 — вторая ЭВМ. Число вершин графа n=22. Веса вершин

одинаковы и равны единице. Матрица весов В графа имеет

следующий вид:

Требуется разрезать граф на два подграфа (m=2) так, чтобы сумма

весов ребер между подграфами была минимальна, а число

вершин в каждом подграфе не превышало с=21. Кроме того,

вершины 19 и 20 должны находиться в разных подграфах. Начальное

разрезание выбирается случайным (рис. 6.2.6):

Q (U

) = 7. (6.2.71)

Условие «неподвижности» вершин 19 и 20 учитывается тем, что

они не входят в число вершин, претендующих на перенос.

Рис. 6.2.5. Исходный граф примера 1. Пунктиром показано оптимальное раз-

резание.

Рис. 6.2.6. Граф устройства сопряжения двух ЭВМ. Единичные веса связей не

обозначены. Пунктиром показано исходное разрезание. Оптимальное разрезание

получается включением в «пунктирную» зону вершин 1, 2, 3 и 6.

Первая структура, полученная предложенным алгоритмом, имеет

вид

(6.2.72)

Содержательный анализ этой задачи показал, что критерий

качества может иметь «площадки». Для их преодоления в выражения

(6.2.61), (6.2.63) и (6.2.65) алгоритма были добавлены равенства, что

обеспечило возможность движения вдоль площадок минимизируемой

функции Q(U). Это дало возможность получить лучшее решение, чем

предыдущее:

(6.2.73)

Таким образом, предложенный алгоритм эффективно

решает задачу об оптимальной агрегации (разрезании)

графа.

Отметим, что описанный алгоритм является локальным в силу

релаксации на каждом шаге, т. е. неухудшения критерия Q(U). Это

обеспечивает надежность отыскания локального минимума

минимизируемого критерия. Однако задача об оптимальном

разрезании достаточно сложного графа имеет ярко

выраженный многоэкстремальный характер. Существующие точные

методы ее решения типа «ветвей и границ» требуют очень больших

затрат машинного времени, а эвристические детерминированные

методы позволяют находить лишь локальное решение данной задачи.

Поэтому необходима разработка таких методов, которые совмещают в

себе быстродействие эвристических процедур с возможностью

нахождения глобального экстремума. Это обстоятельство заставляет

рассмотреть глобальные алгоритмы случайного поиска для решения

задачи агрегации графа.

6.2.3.5. Алгоритм глобальной

минимизации критерия

оптимальности Q(U) [114]

Будем «глобализировать» алгоритм, описанный в подразделе

6.2.3.4. Это можно сделать двумя способами. Прежде всего, применим

случайный выбор исходных разрезаний:

(6.2.74)

удовлетворяющих ограничениям 5 на размер

сегментов. Локальный спуск с помощью описанного выше алгоритма

из каждой начальной точки (6.2.74) дает локальные оптимумы

, ..., U

. (6.2.75)

Естественно глобальный оптимум оценивать лучшим из ло-

кальных:

Другой мерой, «глобализирующей»

алгоритм, является введение возможности ухудшения критерия. Для

этого достаточно формулы (6.2.61), (6.2.63) и (6.2.65) записать

соответственно в виде

(6.2.76)

∆Q

< α,

где в ограничениях вместо нуля введен параметр α. При α>0 возможно

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

«перевала» в зону глобального экстремума. Очевидно, что на эту меру

следует идти лишь попав в локальный экстремум.

Рис. 6.2.7. Поведение связности графа в процессе адаптации. Штриховкой от-

мечены интервалы времени, когда α > 0.

Алгоритм глобального разрезания в этом случае представляется

таким образом. При α = 0 достигается локальный экстремум U

который запоминается вместе с Q

= Q(U

). Далее параметр а на

некоторое число шагов увеличивается и затем снова α = 0. Полученное

локальное значение критерия Q

= Q(U

) сравнивается с Q

. Если

, то вместо Q

и U

запоминаются как лучшее решение Q

, в противном случае поиск продолжается, и т. д. Легко заметить,

что в результате работы алгоритма шансы найти глобальный экст-

ремум со временем увеличиваются.

Приведем пример работы этого алгоритма [114]. Рассматривается граф

с n = 60, который необходимо разрезать на семь подграфов, т. е. т = 7

при ограничениях с = 9. Веса всех вершин графа одинаковы и равны

единице (a

= 1). Значения функции качества в локальных минимумах

были следующими: i 1 2 3 4 5 6 7 8 9 10 11 12

Q(U

) 875 874 863 853 855 853 857 848 868 871 870 877

Начальное значение функции качества Q(U

) = 1242. В качестве

глобального решения получено разрезание, при котором функция

качества имеет значение Q(U

) = 848.

На рис. 6.2.7 показана динамика поведения критерия при поиске. В

моменты A

и A

вводились рандомизированные изменения начальных

условий, что вызвало резкое увеличение критерия.

Таким образом, разумное оперирование обоими средствами

глобализации позволяет эффективно и без лишних затрат оценивать

глобальный экстремум в задаче о разрезании.

6.2.3.6. Адаптивная агрегация графа

с переменными свойствами в детерминированной среде

Рассмотрим случай, когда параметры (6.2.4) агрегируемого графа

Г изменяются во времени или под действием среды:

= a

(X, t); (6.2.77)

= b

(X, t),

причем эти зависимости детерминированны и среда изменяется

достаточно медленно, т. е. производная X(t) мала по модулю.

Тогда оптимальная агрегация (разрезание) U

(6.2.16) также

изменяется и возникает задача ее отслеживания, т. е. адаптации к

изменяющимся параметрам графа. Это обычная задача адаптации к

новым условиям, причем ограничения S могут нарушаться. Алгоритм

адаптивной агрегации должен иметь возможность как устранять

возникающие нарушения ограничений S, так и минимизировать

критерий.

Воспользуемся описанным выше алгоритмом устранения на-

рушения ограничений S (см. п. 6.2.3.3) и алгоритмом поиска

оптимального разрезания (см. п. 6.2.3.4). Связь этих алгоритмов

показана на рис. 6.2.3 и 6.2.4 пунктирными стрелками. В алгоритме

устранения нарушения ограничений S (см. рис. 6.2.3) таких стрелок

две: а и б. Стрелка а обозначает переход при устранении ограничений,

а стрелка б — при невозможности это сделать. В последнем случае для

решения задачи необходимо расширение ресурсов С (6.2.13).

Блок-схема адаптации, объединяющая оба рассмотренных выше

алгоритма, приведена на рис. 6.2.8. Здесь стрелки а и б соответствуют

пунктирным стрелкам а и б на рис. 6.2.3.

Рис. 6.2.8. Блок-схема

адаптивной агрегации из-

меняющегося графа.

Как видно, алгоритм адаптации работает следующим образом.

После устранения нарушения ограничений (или проверки их

выполнения) производится локальная оптимизация агрегации графа, за

которой снова следует проверка выполнения ограничений, и т. д.

Эффективность работы такого алгоритма гарантируется медленностью

изменения параметров (6.2.77) графа. Поэтому оптимальную

агрегацию U

(X,t) удается отследить описанным образом.

Однако часто среда X изменяется стохастически в соответствии со

своими неизвестными, но определенными статистическими

свойствами, которые удобно описывать плотностью распределения

состояний среды. Рассмотрим этот случай.

6.2.3.7. Стохастическая задача агрегации

графа в соответствии с решением

(6.2.18)

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

(6.2.78)

отличающуюся от (6.2.18) детерминированным характером ог-

раничений S, имеющих вид (6.2.15). В этом случае можно считать, что

среда влияет лишь на матрицу связей графа, т. е.

A = const;

B = B (X). (6.2.79)

Будем предполагать, что состояния среды Х

,...,X

являются

случайными независимыми реализациями неизвестного, но

определенного случайного процесса, имеющего плотность рас-

пределения р(Х), которая, вообще говоря, может изменяться во

времени. Случайные состояния {Х

} среды определяют, в со-

ответствии с (6.2.79), случайные графы {Г

} = {А, B(X

)}, которые и

являются исходным материалом для агрегации.

Необходимо решить (6.2.78), располагая только наблюдениями Х

..., X

. Это обычная адаптация, которая состоит в том, что на каждом k-

м этапе решается задача

(2.6.80)

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

ледовательность U

,...,U

сходилась к оптимальной агрегации U*.

Рассмотрим две модели образования случайных графов Г

(k=1,...,N).

Пусть для простоты

B = X (6.2.81)

(более общий случай выводится аналогично). Здесь X — случайная

матрица п×п, характеризующая конкретное состояние среды

X = || x

n×n

(6.2.82)

Бернуллиевская модель предполагает независимость весов b

графа. Матрица X в этом случае имеет независимые случайные

элементы, стохастические свойства которых p

(х

) должны быть

заданы при моделировании. Генерирование случайных графов; Г

здесь не вызывает трудностей.

Марковская модель графа Г

опирается на интерпретацию

случайной матрицы X как конечной реализации дискретного

марковского процесса с конечным числом (n) состояний. В этом

случае элемент х

матрицы X определяется как число обращений к

переходу от i-гo состояния к j-му за время реализации.

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

P = || p

n×n

(6.2.83)

марковской цепи, можно легко генерировать случайные матрицы X,

характеризующие случайные реализации графа Г. Легко заметить, что

матрица X является смещенной оценкой стохастической матрицы Р.

Действительно,

(6.2.84)

Рис. 6.2.9. Структура стохасти-

ческой матрицы взаимосвязей

вершин графа в экспериментах

(примеры 1—3 п. 6.2.3.7).

(6.2.85)

Такая модель позволяет

удобно анализировать

процесс получения оптимального

разрезания графа адаптивным методом,

опирающимся на наблюдения X

(k = 1,

..., N). Применяя в данном случае на

каждом этапе алгоритм, рассмотренный

в предыдущем подразделе (см. рис.

6.2.8), можно быть уверенным, что этот

процесс сойдется к оптимальному

разрезанию, решающему задачу

(6.2.78).

Проиллюстрируем сказанное на

нескольких экспериментальных при-

мерах.

где