Методика анализа полумарковской системы высокой размерности
Запропоновано методику аналізу напівмарковської системи великої розмірності, основану на технології фазового укрупнення станів системи. Описано ітераційну процедуру, що реалізує цю методику. Запропонований декомпозиційний підхід дозволяє вихідну складну задачу звести до розв’язання послідовності сут...
Gespeichert in:
| Veröffentlicht in: | Проблемы управления и информатики |
|---|---|
| Datum: | 2013 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/207603 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Методика анализа полумарковской системы высокой размерности / Л.Г. Раскин, П.Е. Пустовойтов // Проблемы управления и информатики. — 2013. — № 2. — С. 86–92. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860064964325146624 |
|---|---|
| author | Раскин, Л.Г. Пустовойтов, П.Е. |
| author_facet | Раскин, Л.Г. Пустовойтов, П.Е. |
| citation_txt | Методика анализа полумарковской системы высокой размерности / Л.Г. Раскин, П.Е. Пустовойтов // Проблемы управления и информатики. — 2013. — № 2. — С. 86–92. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Запропоновано методику аналізу напівмарковської системи великої розмірності, основану на технології фазового укрупнення станів системи. Описано ітераційну процедуру, що реалізує цю методику. Запропонований декомпозиційний підхід дозволяє вихідну складну задачу звести до розв’язання послідовності суттєво більш простих.
It is suggested the analysis method of high dimension semi-Markovian system, based on technology of system states phase enlargement. It is described the iteration procedure, which realizes this method. The offered decomposition approach allows dimension reducing of initial complicated problem to the sequence of more simple problems.
|
| first_indexed | 2025-12-07T17:06:38Z |
| format | Article |
| fulltext |
© Л.Г. РАСКИН, П.Е. ПУСТОВОЙТОВ, 2013
86 ISSN 0572-2691
МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ И
ИССЛЕДОВАНИЕ СЛОЖНЫХ УПРАВЛЯЕМЫХ СИСТЕМ
УДК 681.324
Л.Г. Раскин, П.Е. Пустовойтов
МЕТОДИКА АНАЛИЗА ПОЛУМАРКОВСКОЙ
СИСТЕМЫ ВЫСОКОЙ РАЗМЕРНОСТИ
Введение
Принципиальная особенность задач анализа и оценки эффективности систем
с большим числом состояний заключается в том, что сложность этих задач поли-
номинально растет с увеличением размерности системы. Реальный путь преодо-
ления возникающего здесь «проклятия размерности» состоит в декомпозиции,
осуществляемой с помощью процедуры фазового укрупнения состояний систе-
мы [1, 2]. Реализация этой идеи позволяет исходную сложную задачу свести к по-
следовательности более простых. Известная технология фазового укрупнения со-
стояний разработана для случая, когда моделью процесса является марковская
цепь [3]. Более эффективная методика анализа многоразмерных марковских си-
стем предложена в [4]. Вместе с тем реальные потоки случайных событий, опре-
деляющих функционирование систем, не являются пуассоновскими. Исследуем
задачу анализа систем высокой размерности, поведение которых описывается по-
лумарковским процессом (ПМП).
Постановка задачи
Рассмотрим задачу анализа полумарковской системы высокой размерности
на примере многовходовой компьютерной сети. Пусть на вход компьютерной се-
ти поступает суперпозиция нескольких, например m типов потоков заявок. Будем
считать известными законы распределения случайной продолжительности интер-
валов между заявками и, кроме того, законы распределения продолжительности
обслуживания для каждого из входных потоков. Функционирование системы
определим как процесс случайного блуждания на множестве возможных состоя-
ний.
Будем считать, что процесс функционирования системы полумарковским [5, 6].
Для описания этого процесса достаточно задать множество возможных состояний
и начальное состояние, а также матрицу независимых функций распределения
),(tQij ,...,,2,1 ni ,...,,2,1 nj продолжительности пребывания процесса в со-
стоянии i до перехода в состояние j. Для полумарковской модели функционирова-
ния многовходовой компьютерной сети эти функции можно легко получить [7, 8].
С помощью набора )(tQij рассчитаем вероятности )(tPij перехода системы из со-
стояния i в состояние j за время t :
,)())(1()(
0
t
jk
ijikij dQQtP .ji (1)
Тогда
Международный научно-технический журнал
«Проблемы управления и информатики», 2013, № 2 87
)())(1(
0
)(
ijik
jk
jij dQQPp i (2)
— вероятность перехода из i в j вложенной в ПМП марковской цепи. Введем теперь
набор условных функций распределения )(tFij продолжительности пребывания в i
до перехода в j при условии реализации именно этого перехода. При этом
,
)(
)(
ij
ij
ij
p
tP
tF ,,,2,1 ni .,,2,1 nj (3)
В результате этих действий имеем матрицу условных законов распределения
))(( tFij и матрицу вероятностей переходов для марковской цепи, вложенной
в полумарковский процесс.
Определим, наконец, безусловные функции распределения продолжительности
пребывания в i до перехода в какое-либо другое состояние:
).()()( tPtFptF
ij ij
ijijiji
(4)
Дальнейшая процедура анализа полумарковской системы предусматривает рас-
чет финального распределения вероятностей состояний системы )....,,,( 21 nPPPP
Вычисление этого распределения выполняется в два этапа. Сначала, используя
матрицу )( ijp вероятностей переходов вложенной марковской цепи, отыщем
предельное распределение )( 21 n вероятностей состояний вложенной
марковской цепи. Затем найдем набор средних продолжительностей пребывания в
каждом из состояний системы до перехода:
,))(1(
0
dttFT ii .,,2,1 ni (5)
Теперь искомый набор финальных вероятностей ,iP ,,,2,1 ni рассчитывается
по формулам
,
1
n
i
ii
ii
i
T
T
P .,,2,1 ni (6)
Таким образом, исходная задача анализа асимптотического поведения ПМП ре-
дуцирована к существенно более простой задаче того же типа, но для марковской
системы. При этом возможность практической реализации изложенной методики
целиком зависит от возможности расчета предельного вектора ),( 21 n
которая, в свою очередь, определяется размерностью задачи. Если эта размер-
ность велика, то вектор )( 21 n целесообразно отыскивать по методике
фазового укрупнения состояний [4], специально ориентированной на анализ мар-
ковских цепей с большим и сверхбольшим числом состояний. Реализуем эту ме-
тодику применительно к задаче анализа полумарковской системы.
Основные результаты
Все множество состояний разбивается на некоторое число, например m под-
множеств. Одно из этих подмножеств выделяется, состояния остальных укрупня-
ются. Получаемая при этом группа укрупненных состояний вместе с состояниями
выделенного подмножества образует систему состояний, обрабатываемых на оче-
редной итерации. С помощью формул, приведенных выше, рассчитываются веро-
ятности переходов из укрупненных состояний в укрупненные, из укрупненных —
88 ISSN 0572-2691
в неукрупненные, из неукрупненных — в укрупненные, затем для полученной си-
стемы рассчитывается предельный вектор. На следующей итерации разукрупне-
нию подвергаются состояния следующего укрупненного подмножества, и эта но-
вая система анализируется по той же схеме. Вычисления продолжаются до тех
пор, пока не стабилизируется получаемое на каждой итерации предельное рас-
пределение вероятностей состояний. Рассмотрим эту методику подробнее.
Множество возможных состояний системы }...,,2,1{ nI разобьем на m
подмножеств:
},...,,,{ 21 mIIII ,
1
m
k
k II
,
21
kk II
и перенумеруем состояния этих подмножеств следующим образом:
}....,,,{...,},...,,,{...,},...,,,{ 2121112111 1 mmnmmmnn iiiIiiiIiiiI
Решение задачи начнем с начального распределения вероятностей:
)),...,,,(...,),...,,,(...,),...,,,((
)0()0(
2
)0(
1
)0()0(
2
)0(
1
)0(
1
)0(
12
)0(
11
)0(
1 mmnmmnn
....,,2,1,...,,2,1,
1
,
)0(
1
njm
n
nn j
m
Любое распределение, содержащее вероятности всех состояний системы, назовем
полным. Предположим, что после проведения k итераций получено k-е приближе-
ние )(k к предельному вектору в виде
))....,,,(...,),...,,,(...,),...,,,((
)()(
2
)(
1
)()(
2
)(
1
)(
1
)(
12
)(
11
)(
1
k
mn
k
m
k
m
k
n
kkk
n
kkk
m
(7)
Выполним некоторые подготовительные расчеты, необходимые для получе-
ния )1( k -го приближения из (7). Пусть — номер выделяемого на очередной
итерации подмножества состояний. Состояния каждого из остальных подмно-
жеств объединяем в соответствующее подмножеству укрупненное состояние.
Вероятности пребывания системы в каждом из этих укрупненных состояний
равны сумме вероятностей пребывания в состояниях соответствующего подмно-
жества. Таким образом, если укрупненное состояние qI содержит состояния с
номерами ,...,,, 21 qqnqq iii то вычисляемая на очередном шаге вероятность пребы-
вания системы в этом укрупненном состоянии
)(k
Iq
вычисляется по формуле
....,,1,1...,,3,2,1,
1
)()(
mq
q
q
n
s
k
qs
k
I
(8)
Проведем уточнение распределения вероятностей состояний для выделенно-
го на этой итерации множества состояний. Для пары состояний ),( 21 ss с помо-
щью (1) рассчитаем вероятность перехода из состояния 1s в состояние 2s за
время t :
.)())(1()(
0
,,,
2
21121
t
sk
ssksss dttdQtQtP
Международный научно-технический журнал
«Проблемы управления и информатики», 2013, № 2 89
При этом вероятность перехода из 1s в 2s для марковской цепи, вложен-
ной в ПМП, равна
),(
2121 ,, ssss Pp ,...,,2,11 ks ....,,2,12 ks (9)
Далее с учетом (2)–(5) имеем
,
)(
)(
21
21
21
,
,
,
ss
ss
ss
p
tP
tF
,)()(
12
21211 ,,
ss
sssss tFptF
,))(1(
0
11
dttFT ss ....,,2,11 ks
Теперь, используя (6), рассчитаем условное распределение вероятностей для
выделенного подмножества состояний :
,
1
11
1
k
s
ss
ss
s
T
T
P ,...,,2,11 ks
где )...,,,(
21 kss — предельное распределение вероятностей для вложенной
марковской цепи с матрицей переходов, определяемой (9). При этом безусловное
распределение вероятностей для -го выделенного подмножества имеет вид
).1(
)()(
11
q
k
Is
k
s q
P
В результате получаем систему со множеством возможных состояний
}...,,,...,,,,...,,,{ 121121 mn IIiiiIII
и распределением вероятностей пребы-
вания системы в этих состояниях:
)....,,,...,,,,...,,,(~ )()()()(
2
)(
1
)()()()(
1121
k
I
k
I
k
n
kkk
I
k
I
k
I
k
m
Такое распределение будем называть групповым.
Рассчитаем вероятности переходов в этой новой системе. Их численное зна-
чение зависит от типа соответствующих состояний. Вероятности перехода из со-
стояний выделенного подмножества l в состояния этого же подмножества оста-
ются такими же, какими они были в исходной матрице переходов, т.е.
.),(,~
21,
)(
, 2121
Isspp ss
k
ss
Вероятность перехода из какого-либо неукрупненного состояния si в какое-
либо укрупненное состояние VI равна сумме истинных вероятностей переходов
из этого неукрупненного состояния si во все состояния подмножества ,VI т. е.
....,,1,1...,,2,1,,~
1
,
)(
, mVIspp
vn
q
Vqs
k
Vs
Вероятность перехода из укрупненного состояния VI в какое-либо неукруп-
ненное состояние si равна сумме произведений истинных вероятностей переходов
svqp , из состояний подмножества ,VI умноженных на условные вероятности
)(k
VqW пребывания системы в этих состояниях подмножества .VI В свою очередь,
90 ISSN 0572-2691
условная вероятность
)(k
VqW пребывания системы в этих состояниях Vqi подмноже-
ства VI вычисляется как отношение вероятности пребывания в этом состоянии, со-
ответствующей очередному полученному полному распределению, к сумме таких
вероятностей для всех состояний этого подмножества. Таким образом,
.~
1
1
)(
)(
,
)(
1
,
)(
,
v
v
v
V
n
q
n
q
k
Vq
k
Vq
sVq
k
Vq
n
q
sVq
k
sI
pWpp
Наконец, вероятность перехода из какого-либо укрупненного состояния
1VI
в другое укрупненное состояние
2VI вычисляется как сумма вероятностей пере-
хода системы из укрупненного состояния
1VI во все состояния, входящие в
укрупненное состояние ,
2VI т.е.
.~
2
2
1
1
1
1
11
11
2211
21 1 1
1
)(
)(
,
)(
v v
vVV
n
q
n
q
n
q
k
qV
k
qV
qvqv
k
II
pp
Таким образом, по формулам (8), (9) рассчитывается очередное групповое
распределение вероятностей пребывания системы на множестве полученных пос-
ле укрупнения состояний )(~ k и соответствующая очередному этапу укрупнения
матрица вероятностей переходов
}....,,,...,,,,...,,,{),(),~(
~
121121
)()(
mn
k
ij
k IIiiiIIIjipW
Подготовительные расчеты закончены. Теперь вычисляем новое групповое
распределение вероятностей по формуле
)()()1()1()1()1(
2
)1(
1
)1()1()1( .
~~)...,,,...,,,...,,,(~
121
kkk
I
k
I
k
n
kkk
I
k
I
k W
m
Групповое распределение используем для получения нового полного распре-
деления
))....,,,(...,),...,,,(...,),...,,,((
)1()1(
2
)1(
1
)1()1(
2
)1(
1
)1(
1
)1(
12
)1(
11
)1(
1
k
nm
k
m
k
m
k
n
kkk
n
kkk
m
Компоненты этого распределения вычисляются по формулам
,...,,2,1,~ )1()1(
ns
k
s
k
s
....,,2,1,...,,1,1...,,2,1,~
1
)(
)(
)1()1(
Vn
q
k
Vq
k
Vqk
V
k
Vq nqmV
v
Очередной шаг итерационного улучшения распределения вероятностей пребы-
вания системы на множестве возможных состояний системы завершен. На следую-
щем шаге выделяются состояния подмножества },,...,,{
1,12,11,11
niiiI
а состояния всех остальных подмножеств укрупняются в состояния ,...,,, 21 III
....,,2 mII Вся дальнейшая процедура совершенно аналогична описанной. Вы-
числения продолжаются до тех пор, пока на очередной )1( N -й итерации для
некоторого достаточно малого не будет выполнено неравенство
Международный научно-технический журнал
«Проблемы управления и информатики», 2013, № 2 91
.)()1( NN
Преимущества описанной процедуры расчета предельного вектора марков-
ской цепи состоят в следующем: во-первых, существенно снижается по сравне-
нию с исходной размерность решаемой на каждом шаге задачи, во-вторых, что не
менее важно, предложенная методика не содержит трудоемкой процедуры реше-
ния многоразмерной системы линейных алгебраических уравнений.
Эта процедура позволяет анализировать системы с числом состояний
порядка 10
4
, далее с ростом размерности задачи ее реализация затрудняется.
Возможное направление дальнейшего исследования для существенного по-
вышения эффективности методик укрупнения состояний заключается в использо-
вании многоэтапных, иерархических процедур укрупнения.
Заключение
Для полумарковской системы высокой размерности предложена декомпози-
ционная процедура, основой которой является фазовое укрупнение состояний ис-
ходной системы.
Вычислительная процедура решения задачи реализует итерационное улуч-
шение получаемого на очередном шаге приближения к искомому распределению
вероятностей состояний системы.
Предложенная процедура фазового укрупнения существенно снижает раз-
мерность задач, решаемых на каждом ее шаге.
Л.Г. Раскін, П.Є. Пустовойтов
МЕТОДИКА АНАЛІЗУ НАПІВМАРКОВСЬКОЇ
СИСТЕМИ ВЕЛИКОЇ РОЗМІРНОСТІ
Запропоновано методику аналізу напівмарковської системи великої розмірнос-
ті, основану на технології фазового укрупнення станів системи. Описано ітера-
ційну процедуру, що реалізує цю методику. Запропонований декомпозиційний
підхід дозволяє вихідну складну задачу звести до розв’язання послідовності
суттєво більш простих.
L.G. Raskin, P.Ye. Pustovoitov
ANALYSIS METHOD OF HIGH DIMENSION
SEMI-MARKOVIAN SYSTEM
It is suggested the analysis method of high dimension semi-Markovian system, based
on technology of system states phase enlargement. It is described the iteration proce-
dure, which realizes this method. The offered decomposition approach allows dimen-
sion reducing of initial complicated problem to the sequence of more simple prob-
lems.
1. Королюк В.С., Турбин А.Ф. Фазовое укрупнение сложных систем — Киев : Вища шк.,
1978. — 110 с.
2. Крол Г. Исследование сложных систем по частям. Диакоптика — М. : Изд-во иностр. лит.,
1965. — 216 с.
3. Кемени Дж., Снелл. Дж. Конечные цепи Маркова : Пер. с англ. — М. : Наука, 1970. —
271 с.
4. Раскин Л.Г. Анализ марковских цепей с использованием фазового укрупнения состояний //
Информационные технологии : Наука, техника, образование, здоровье. — Харьков : НТУ
«ХПИ», 1997. — С. 280–284.
5. Королюк В.С., Турбин А.Ф. Полумарковские процессы и их приложения. — Киев : Наук.
думка, 1976. — 181 с.
92 ISSN 0572-2691
6. Сильверстов Д.С. Полумарковские процессы с дискретным множеством состояний. — М. :
Сов. радио, 1980. — 272 с.
7. Крылов В.В., Самохвалова С.С. Теория телетрафика и ее приложения. — СПб. : БХВ-Пе-
тербург, 2005. — 288 с.
8. Кокс Д., Смит В. Теория восстановления : Пер. с англ. — М. : Сов. радио, 1967. — 198 с.
Получено 22.03.2012
|
| id | nasplib_isofts_kiev_ua-123456789-207603 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-12-07T17:06:38Z |
| publishDate | 2013 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Раскин, Л.Г. Пустовойтов, П.Е. 2025-10-10T10:45:27Z 2013 Методика анализа полумарковской системы высокой размерности / Л.Г. Раскин, П.Е. Пустовойтов // Проблемы управления и информатики. — 2013. — № 2. — С. 86–92. — Бібліогр.: 8 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207603 681.324 10.1615/JAutomatInfScien.v45.i4.50 Запропоновано методику аналізу напівмарковської системи великої розмірності, основану на технології фазового укрупнення станів системи. Описано ітераційну процедуру, що реалізує цю методику. Запропонований декомпозиційний підхід дозволяє вихідну складну задачу звести до розв’язання послідовності суттєво більш простих. It is suggested the analysis method of high dimension semi-Markovian system, based on technology of system states phase enlargement. It is described the iteration procedure, which realizes this method. The offered decomposition approach allows dimension reducing of initial complicated problem to the sequence of more simple problems. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Математическое моделирование и исследование сложных управляемых систем Методика анализа полумарковской системы высокой размерности Методика аналізу напівмарковської системи великої розмірності Analysis Method of High Dimension Semi-Markovian System Article published earlier |
| spellingShingle | Методика анализа полумарковской системы высокой размерности Раскин, Л.Г. Пустовойтов, П.Е. Математическое моделирование и исследование сложных управляемых систем |
| title | Методика анализа полумарковской системы высокой размерности |
| title_alt | Методика аналізу напівмарковської системи великої розмірності Analysis Method of High Dimension Semi-Markovian System |
| title_full | Методика анализа полумарковской системы высокой размерности |
| title_fullStr | Методика анализа полумарковской системы высокой размерности |
| title_full_unstemmed | Методика анализа полумарковской системы высокой размерности |
| title_short | Методика анализа полумарковской системы высокой размерности |
| title_sort | методика анализа полумарковской системы высокой размерности |
| topic | Математическое моделирование и исследование сложных управляемых систем |
| topic_facet | Математическое моделирование и исследование сложных управляемых систем |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/207603 |
| work_keys_str_mv | AT raskinlg metodikaanalizapolumarkovskoisistemyvysokoirazmernosti AT pustovoitovpe metodikaanalizapolumarkovskoisistemyvysokoirazmernosti AT raskinlg metodikaanalízunapívmarkovsʹkoísistemivelikoírozmírností AT pustovoitovpe metodikaanalízunapívmarkovsʹkoísistemivelikoírozmírností AT raskinlg analysismethodofhighdimensionsemimarkoviansystem AT pustovoitovpe analysismethodofhighdimensionsemimarkoviansystem |