Растригин Л.А. Адаптация сложных систем
Подождите немного. Документ загружается.
Пусть для простоты веса вершин одинаковы и равны единице, т. е.
а
i
= 1. Граф имеет n = 16 вершин, связанных между собой в
соответствии со стохастической матрицей Р, состоящей из двух
элементов р
1
и р
2
, значительно отличающихся друг от друга (p1>>p2).
На рис. 6.2.9 представлена структура этой матрицы.
Оптимальная агрегация U
*
априори очевидна:
(6.2.86)
Для оценки эффективности
получаемой агрегации U
*
естественно ввести коэффициент близости к
оптимальной агрегации на N-м. этапе адаптации:
(6.2.87)
где n
N
— число вершин графа, которое на N-м шаге
совпадает с оптимальной агрегацией U
*
.
В экспериментах ресурсы С не ограничивались и объем Т составлял
128, т. е. матрица (6.2.82) строилась на базе 128 элементов марковской
цепи.
Пример 1. p
1
= l / 8; р
2
= 0. Исходная агрегация имела три сегмента:
(6.2.88)
что соответствовало k
0
= 0,56.
Результаты работы алгоритма адаптации приведены в табл. 6.2.1,
из которой видно, что оптимальная агрегация получена на седьмом (N
= 7) этапе адаптации и далее не изменяется. При этом исходная
неоптимальная трехсегментная агрегация (m
0
= 3) автоматически
перестроилась в оптимальную двухсегментную (m
7
= 2).
Пример 2. p
1
= 7 / 64; p
2
= l / 64. Начальная агрегация, как и в
предыдущем примере, была трехсегментной (6.2.87).
Результаты работы алгоритма адаптации (табл. 6.2.2) интересны
тем, что оптимальная агрегация была получена уже на третьем этапе
U
3
= U
*
, а на пятом произошло ухудшение агрегации. Дело в том, что
случайные реализации графа В могут достаточно сильно отклоняться
от среднего значения и тем самым вносить существенные искажения в
результаты, полученные -ранее. Чтобы избежать этого, можно
воспользоваться стан-
Таблица
6.2.1
Этап
адапта-
ции
N
Агрегация
U
N
на
N
-м этапе
адаптации
Коэф.
близости к
оптим.
агрегации
k
N
Критерий
качества
Q
N
0
Согласно (6.2.88)
0,56
72
1
I
1
=
(1,
2,
3,
4,
5)
0,6
61
I
2
=
(7, 8, 9, 10, 11, 12)
I
3
=
(6, 13, 14, 15, 16)
2
I
1
=
(1,
2,
3,
4)
0,7
32
I
2
=
(5, 7, 8,
9, 10, 11, 12)
I
3
=
(6 13 14 15 16)
3
I
1
=
(1,
2,
3,
4)
0,75
0
I
2
=
(5, 6, 7, 8, 9, 10, 11, 12)
I
3
=
(13141516)
4
То же, что при
N
=
3
0,75
0
5
То же, что при
N
=
4
0,75
0
8
I
1
=
(1,
2,
4, 13, 14, 15, 16)
0
,9
37
I
2
=
(5,6,7,8,9,10,11,12)
I
3
=
(3)
7
I
1
=
(1,2,3,4,13,14,15,16)
1
0
I
2
=
(5, 6,7, 8,
9, 10, 11, 12)
8
То же что при
N
=
7
1
0
9
То же, что при
N
=
8
1
0
10
То же, что при
N
=9
1 0
Таблица 6.2.2*
N U
N
k
N
Q
N
0 Согласно (6.2.88) 0,56 75
1
I
1
=
(1,
2,
3,
4,
16)
0,6
52
I
2
=
(9 7 10)
I
3
=
(5, 6, 8,
11
, 12, 13, 14)
2
I
1
=
(1,
2,
3,
4,
13,
14,
16)
0,9
33
I
2
=
(7)
I
3
=
(5, 6. 8. 9, 10, 11, 12, 15)
3
I
1
=
(1,
2,
3,
4,
13,
14,
15,
16)
1
12
I
2
=
(5, 6, 7,
8,
9, 10, 11, 12)
4
То же, что при
N
=
3
1
11
5
I
1
=
(1,
2,
4,
13, 14,
15,
16)
0,9
22
I
2
=
(3,5,6,7,
8,
9, 10, 11, 12)
6
I
1
=
(1,2,3,4,13,14,15,16)
1
15
I
2
=
(5, 6, 7, 8, 9, 10, 11, 12)
7
То же, что при
N
=
6
1
18
8
То же, что при
N
=
7
1
15
9
То же, что пр
и
N
=
8
1
17
10 То же
,
что п
р
и
N
=9 1 20
* Обозначения те же, что в табл. 6.2.1.
Таблица 6.2.3*
N U
N
k
N
Q
N
0 Согласно (6.2.88) 0,56 78
1
/
1
=
(
1
,
2
,
3,
4
)
0,75
56
I
2
=
(
5
,
6
,
7
,
8
,
9
,
10
,
11
,
12
)
I
3
=
(13, 14, 15, 16)
2
/
1
=
(2,
3,
8)
0,75
4
5
I
2
=
(
1
,
4
,
5
,
6
,
7
,
9
,
10
,
11
,
12
)
I
3
=
(
1
3,
14
,
1
5,
1
6)
3 /
1
=
(
3
,
8
)
0
,
75 35
I
2
=
(
4
,
5
,
6
,
7
,
9
,
10
,
11
,
12
,
14
)
I
3
=
(
1
,
2
,
13
,
15
,
16
)
4 /
1
=
(
2
)
0
,
75 50
I
2
=
(
4
,
5
,
6
,
7
,
8
,
10
,
11
,
12
,
13
)
I
3
=
(1, 3, 9, 14, 15, 16)
5 /
1
=
(
1
,
3
,
9
,
13
,
14
,
15
,
16
)
0
,
8 45
I
2
=
(
2
,
4
,
5
,
6
,
7
,
8
,
10
,
11
,
12
)
6 /
1
=
(
1
,
2
,
3
,
4
,
10
,
13
,
16
)
0
,
8 37
I
2
=
(
5
,
6
,
7
,
8
,
9
,
11
,
12
,
14
,
15
)
7
/
1
=
(1,
2,
3,
4,
11,
13,
15,
16)
0,9
36
I
2
=
(5,
6,
7,
8,
9,
1
0,
12
,
14
)
8
/
1
=
(1, 2, 3
, 4, 13, 14. 15, 16)
1
39
I
2
=
(
5
,
6
,
7
,
8
,
9
,
10
,
11
,
12
)
9 То же
,
что п
р
и
N
=8 1 40
10
То же, что при
N
=
9
1
37
* Обозначения те же, что в табл. 6.2.1 и 6.2.2.
дартным приемом, используемым в общей теории адаптации — не
«обрабатывать до конца» полученную информацию. Например, можно
остановить алгоритм адаптации не по критерию исчерпывания
случайного перебора, а раньше — по критерию заданного числа шагов.
Пример 3. p1 = 6 / 64; р
2
= 2 / 64. Начальные условия (6.2.88)
сохраняются. Результаты работы алгоритма адаптации приведены в
табл. 6.2.3. Любопытно, что критерий качества агрегации изменялся
незначительно ввиду большой связности оптимальной сегментации,
которая, тем не менее, была найдена за восемь этапов адаптации.
Таким образом, описанные эксперименты убедительно доказывают
эффективность предложенного алгоритма адаптивной агрегации при
работе со стохастическими графами.
Теперь рассмотрим случай эволюционирующего стохастического
графа, когда плотность распределения состояний X среды изменяется
во времени, т. е. имеет вид
p (X, t). (6.2.89)
6.2.3.8. Адаптивная агрегация графа,
функционирующего в нестационарной среде
Здесь оптимальная агрегация U
*
изменяется во времени, т. е.
агрегированный граф эволюционирует вместе со средой:
U
*
= U
*
(t). (6.2.90)
Алгоритм адаптивной агрегации (см. рис. 6.2.8) должен «от-
слеживать» этот дрейф оптимальной агрегации.
Пример. Дрейф матрицы (n=16) переходных вероятностей
моделировался путем изменения границ вероятностей p
1
=7/64 и
р
2
=1/64 (рис. 6.2.10) таким образом, что каждый сегмент при
оптимальном разрезании содержал всегда восемь смежных вершин
(первая и шестнадцатая вершины смежные). На рис. 6.2.10 пунктиром
показано очередное состояние матрицы, а стрелкой — направление
дрейфа границ. Буквой i обозначен промежуток между i-й и (i+1)-й
строкой (столбцом). Дрейф матрицы представляется следующей
формулой:
i → i + l для i=1,...,16-l;
i → i + l - 16 для i>16-l. (6.2.91)
Скорость этого дрейфа была выбрана равной l вершинам,
меняющим принадлежность к сегменту за один этап работы ло-
кального алгоритма агрегации. Матрица реализации строилась на базе
128 шагов марковской цепи при равновероятно выбранной начальной
вершине. Ресурсы С не ограничивались.
Результаты проведенных экспериментов (табл. 6.2.4) показывают,
что оптимальная агрегация находилась на каждом этапе работы
алгоритма. Здесь k
N
' — исходное значение коэффициента
соответствия с оптимальной аг-
регацией на N-м этапе, a k
N
—
значение этого коэффициента после
агрегации (оно всегда было равно 1).
Стрелками показаны переходы
состояний графа.
На рис. 6.2.11 показано поведение
минимизируемого критерия в
процессе агрегации. Здесь j —
моменты пересегментации (т. е.
использования одной из операций ψ),
N — моменты скачкообразного
дрейфа матрицы на величину l пос-
ле полной обработки алгоритма
Р
ис. 6.2.10. Схема дрейфа матрицы
переходов марковской цепи (пример л.
6.2.3.8
)
.
Таблица 6.2.4
Рис. 6.2.11. Поведение критерия качества агрегации в процессе дрейфа при
адаптивной агрегации.
агрегации. Пунктиром показано поведение критерия Q без
адаптации.
Эксперименты наглядно показали, что описанный алгоритм
эффективно отслеживает изменяющуюся агрегацию графа и поэтому
может быть рекомендован для адаптации системы, функционирующей
в изменяющейся среде, структура которой описывается графом.
6.2.4. Некоторые обобщения
задачи об агрегации графа
Постановку задачи об агрегации графа, рассмотренную в под-
разделе 6.2.1, можно обобщить следующим образом. Введем функцию
отношения между l-м и k-м сегментами φ(l,k). Частный случай такой
функции уже рассматривался в п. 6.2.2.2 и 6.2.2.4, где она выражала
расстояние между l-м и k-м сегментами.
В общем случае функция φ(l,k) выражает степень увеличения
потерь от расположения вершин графа при агрегации в разных
сегментах. Так, для стандартной задачи агрегации (см. подраздел
6.2.1) эта функция имеет вид характеристической:
(6.2.92)
а для задачи оптимального расположения
блоков информации на
цилиндрах магнитного диска (см. п. 6.2.2.3) она принимает вид
φ (l, k) = | l - k |. (6.2.93)
Критерия оптимальности агрегации графа теперь легко записать в
форме
(6.2.94)
где l
i
— номер сегмента, содержащего i-ю вершину графа ( ), a k
j
—
номер сегмента, содержащего j-ю вершину ( ). Очевидно, что эта
принадлежность определяется агрегацией U (6.2.10), т. е.
l
i
= ζ (U, j); (6.2.95)
k
j
= ζ (U, j),
где ζ — процедура определения принадлежности данной вершины
одному из сегментов, или, точнее, — процедура определения номера
сегмента, содержащего данную вершину при имеющейся
агрегации U. Реализация такой процедуры, очевидно, не вызывает
трудностей.
Задача, которую следует решать при оптимальной агрегации
графа, теперь принимает вид
(6.2.96)
Преимущество записи
критерия в виде (6.2.94) заключается в том, что он определен явно на
исходном графе Г, что упрощает организацию операций по
перенесению вершин из одного сегмента в другой. Рассмотрим
условия осуществления указанных операций преобразования
агрегации.
Операция первого рода (см. п. 6.2.3.2) преобразует агрегацию
согласно (6.2.42) и (6.2.43) таким образом, что критерий качества
изменяется на величину
(6.2.97)
Легко видеть, что при (6.2.92) это выражение вырождается в (6:2.46).
При функции φ вида (6.2.93) получаем
(6.2.98)
Очевидно, что при ∆Q<0 операцию следует считать успешной,
а в противном случае — неудачной.
Теперь рассмотрим операцию второго рода (6.2.47). Она изменяет
критерий качества следующим образом (воспользуемся здесь
коммутативностью (6.2.50)):
(6.2.99)
При φ, имеющей вид характеристической функции (6.2.92), это
выражение совпадает с (6.2.49). Аналогично можно записать его для
модульного представления (6.2.93). Учет полученных соотношений,
определяющих успех или неуспех той или иной операции, в
алгоритмах адаптивной агрегации п. 6.2.3.4 не представляет труда.
Этим и определяется алгоритм поиска оптимальной агрегации графа с
произвольным видом соотношения φ(k, l) между сегментами.
Примеры адаптивной агрегации стохастического графа (п = = 16) с
соотношением φ вида (6.2.93) между сегментами и марковской
моделью состояния среды X приведены в работе [116].
§ 6.3. Адаптация
процессов распределения памяти в
вычислительной сети
6.3.1. Формулировка задачи
Рассмотрим вычислительную сеть, состоящую из n ЭВМ, каждая
из которых имеет собственную память объемом c
i
(i = l, ... ..., n). Кроме
того, в сети имеется k ЭВМ, играющих роль банков данных, в которых
сосредоточена вся информация, необходимая для решения задач,
поступающих в сеть. Пусть эта информация представляет собой
множество блоков
{а
j
} (j = 1, ..., т), (6.3.1)
где a
j
— объем (например, в битах) j-го блока информации.
Каждая ЭВМ может обратиться в любой банк данных за любым
числом блоков из множества (6.3.1) и получить необходи-
мые данные, затратив на это определенное время, зависящее от
длины очереди, объема требуемой информации и расстояния
между этой ЭВМ и соответствующим банком или числа пунктов
коммутации между ними.
Помимо этого, каждая ЭВМ в пределах своего объема памяти
c
i
может иметь некоторое количество информации, обращение к
которой не требует дополнительного времени.
Заявки на обслуживание, поступающие в сеть, содержат перечень
той информации из банков данных, которую необходимо
использовать при решении каждой задачи-заявки. Будем характе-
ризовать j-ю заявку множеством I
j
номеров информационных блоков
банков данных, используемых при обслуживании этой заявки в
сети.
Дисциплину обслуживания в такой сети естественно связать со
средним временем решения задач, что реализуется путем решения
задачи на той ЭВМ, в памяти которой имеется необходимая для
этой задачи информация.
Таким образом, цель состоит в том, чтобы определить два пра-
вила:
1) дисциплину обслуживания, т. е. правило направление оче
редной заявки на одну из ЭВМ сети, руководствуясь при этом
сведениями о требуемых блоках информации, состоянии памяти
всех ЭВМ сети и их загрузке;
2) правило формирования памяти ЭВМ сети.
6.3.2. Сведение задачи распределения памяти
к задаче математического программирования
Формализуем задачу. Пусть и
ij
— двоичная переменная, вы-
ражающая наличие (и
ij
=1) или отсутствие (и
ij
=0) в памяти i-й
ЭВМ j-го блока информации. Очевидно, что имеет место следующее
ограничение, связанное с ограниченностью объема памяти каждой
ЭВМ:
(6.3.2)
Пусть поток задач, решаемых сетью,
образуется из k различных потоков, каждый из которых
характеризуется определенным распределением вероятностей
использования блоков информации (6.3.1):
P
l
= (p
1l
, ..., p
ml
) (l = 1, ..., k), .... (6.3.3)
где p
jl
— вероятность того, что при решении задачи l-го потока
требуется j-й блок информации. Будем для удобства считать эти
вероятности нормированными, т. е.
(6.3.4)
(хотя это и необязательно, так как для решения задачи
обычно необходимо несколько блоков).
Определим вероятность попадания задачи l-го потока на i-ю ЭВМ
при следующей дисциплине обслуживания: «направлять задачу туда,
где больше необходимой информации». Эта вероятность
(6.3.5)
Аналогично можно определить вероятность
того, что задача-l-го потока, направленная на i-ю ЭВМ,
найдет там необходимую для решения информацию, т.
е. не придется обращаться к банку данных. Пусть эта вероятность
p''
li
= p
li
(U). (6.3.6)
Теперь, располагая интенсивностями потоков решаемых задач
(естественно их считать пуассоновскими)
λ
1
, ..., λ
k
(6.3.7)
и интенсивностями решения задач каждой ЭВМ (их можно считать
экспоненциальными)
µ
1
, ..., µ
n
, (6.3.8)
можно сформулировать простейшую задачу определения опти-
мального расположения блоков информации (6.3.1) на ЭВМ сети,
минимизирующего обращаемость к банку данных в процессе
функционирования сети:
(6.3.9)