ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 169
Скачиваний: 0
ВВЕДЕНИЕ
|
28 |
|
|
|
|
|
|
|
|
Будем говорить, что |
автомат А обладает |
целесообраз |
|||||||
ным поведением в среде С, если |
|
|
|
||||||
W(A,C)>—{a1 |
+ a2+ |
|
+ а.л). |
|
(0.4.16) |
||||
Д л я автомата, совершающего |
свои |
действия равноверо |
|||||||
ятно и независимо от реакции |
среды, |
|
|
|
|||||
W=—у(a. l |
+ a2+ ... |
|
+ак). |
|
|
(0.4.17) |
|||
Очевидно, |
что W(A, |
C)^W. |
В работе [28] рассмотрены |
||||||
множества |
автоматов |
с |
целесообразным |
поведением в |
|||||
стационарных случайных |
средах. |
|
|
|
|||||
Рассмотрим |
поведение |
автомата в |
с о с т а в н о й |
с л у |
|||||
ч а й н о й |
с р е д е |
[28], |
т. е. в среде, свойства которой |
||||||
изменяются |
случайным |
образом. |
Будем |
считать, |
что |
среда, с которой взаимодействует автомат, состоит из стационарных случайных сред С( а >, переключение кото рых осуществляется по марковской схеме.
Рассмотрим цепь Маркова |
|
K(CW, ...,СМ, А), |
(0.4.18) |
имеющую v состояний С*1 *,..., С м , причем переходы из одного состояния в другое задаются матрицей переход ных вероятностей
|
>\2 |
А = |
(0.4.19) |
6ui |
би: |
|
V2 |
Состояние С ( а ) цепи Маркова соответствует стацио
нарной случайной |
среде |
|
|||
С^ |
= С{а^\ |
а2 |
(а) |
(0.4.20) |
|
Будем |
говорить, |
что автомат находится в составной |
|||
среде |
К, |
если |
в |
каждый |
момент времени он находится |
в одной |
из сред С<а> ( а = 1, 2, . . . , v), т. е. если его дейст |
||||
вия у |
и значения |
входной переменной х связаны форму |
|||
лами |
(0.4.8) и |
(0.4.9); если при этом в момент t авто |
мат находился в среде С ( а ) , то в момент t+ 1 он будет находиться в среде С(Р> с вероятностью ба р-
ВВЕДЕНИЕ
29
Обозначим через \р№ ( р = 1 , . . . , у ; г'= 1, 2, ... , т ) такое состояние системы автомат — составная среда, при
котором |
автомат |
находится в |
состоянии щ, а |
состав |
ная среда |
— в состоянии С(Р>. Тогда вероятность |
p i j ( P ) ( v ) |
||
перехода |
системы |
из состояния |
i|3i<P) в состояние TJ)J(V) |
выражается формулой
PijM W = [Pa^au
где Ilcjj(x)||
Ра г ( Р ) и 1— р а / Р )
(1) + (1 - paW) |
ац (0) ]6P V , |
(0.4.21) |
— переходные |
матрицы |
(x = 0,1) ав |
томата A;
—соответственно вероятности проиг
рыша и выигрыша автомата А в среде С<Р> при действии yat — F(Ui);
Р а ^ = - ^ ^ - |
(0.4.22) |
1 + а„ <Р> |
|
l _ p ^ ( W = _ i Z | 2 L _ . |
(0.4.23) |
Матрица |
|
Л(х(Р),Л) = ||р«<Р^)[| |
(0.4.24) |
(Р, v = 1 , . . . . о; |
t , / = l , . . . , m ) |
является стохастической. Следовательно, поведение сис темы автомат — составная среда описывается некоторой цепью Маркова. В случае эргодической цепи Маркова (0.4.24) математическое ожидание выигрыша W(A,K) автомата А в среде К вычисляется по формуле
W(A, К) = 2 |
2 |
а«(Р)аа(Р). |
(0.4.25) |
||
|
а=1 |
р = 1 |
|
|
|
Здесь аа ( Р> — суммарная вероятность таких |
состояний |
||||
системы, в которых автомат производит действие |
уа, а |
||||
составная среда находится в состоянии С ( Р ) . |
|
|
|||
Простейшая |
составная случайная среда, |
когда |
у = 2, |
||
задается матрицей переходных вероятностей |
|
|
|||
Л = |
1 - 6 |
б |
|
(0.4.26) |
|
б |
1 - 6 |
|
|||
|
|
|
|
Здесь параметр б представляет собой среднюю частоту переключения состояний составной среды.
ВВЕДЕНИЕ
|
30 |
|
|
|
|
|
|
Автоматы |
с |
формируемой |
структурой |
в |
случайных |
||
средах |
[28, |
32, |
33]. Структура |
автомата |
задается пере |
||
ходными матрицами ||а^(л;)|| |
(х = 0,1), которые опреде |
||||||
ляют |
переходы |
состояний u(t)^{uu |
u2,...,um} |
автомата |
при том или ином значении входной переменной х, и
функцией y(t)=F(u(t)), |
определяющей |
действия |
y(t)^ |
||
^{уи |
У2,---,Ук} |
автомата, или, в случае автомата со |
|||
случайными действиями, |
вероятности |
действий |
авто |
||
мата в зависимости от его состояний. |
|
|
Для автоматов с формируемой структурой матрицы переходов изменяются в зависимости от значений вход ной переменной х.
Изменения переходных матриц ||ajj(x)|| осуществля ются следующим образом. Пусть в момент t под воз
действием входной |
переменной |
x{i) |
состояние щ перехо |
|||||
дит в состояние Uj, а затем, в момент |
входная |
пере |
||||||
менная |
принимает |
значение х ( £ + 1 ) = 0 (выигрыш) |
либо |
|||||
x(t+l)=l |
(проигрыш). Величина |
переходной |
вероят |
|||||
ности aij(t+\) |
увеличивается |
в |
случае |
x(t+l)=0 |
и |
|||
уменьшается |
при |
x(t+l)=l, |
а |
остальные |
элементы |
|||
aik(t,x(t)) |
(&¥=/) |
i-й строки |
изменяются |
таким |
обра |
зом, чтобы сохранилась стохастичность матрицы, т. е. чтобы соблюдалось условие
m
(0.4.27)
Остальные строки матрицы ||a,-j(x)|| не изменяются. В каждый момент времени t изменяется лишь одна из мат риц \\a(t,x(t) || (х=0,1), и именно та, которая соответст вует значению х, равному x(t).
Предложено несколько алгоритмов изменения элемен тов переходных матриц [32—36]. Например, в работе [32] рассмотрены следующие, весьма общие, формулы изме нения переходных вероятностей:
|
~a[l-x(t + l)]+ |
( - l ) i ( f + l ) e . J t ( ( ) ( l _ f l ) ; ' |
(0.4.28) |
|
|
a[l-x(t+\)]ai.x(t) |
(f) |
|
|
flfft*<0 |
(*+!) =fl[i-*(f+i)]+ |
( _ i)*<t+i)flij.*<t> ( i - a ) |
(0.4.29) |
|
Здесь |
a = const; 0 < a < l . |
|
|
|
ВВЕДЕНИЕ
31
Некоторые основные сведения о цепях Маркова. Из изложенного видно, что функционирование автоматов в случайной среде описывается цепью Маркова. Поэтому исследование автомата в случайной среде сводится к ис следованию соответствующей цепи Маркова. Приводим основные положения о цепях Маркова [29, 30].
Под |
цепью |
Маркова |
будем понимать некоторую сис |
||||
тему U, которая в каждый момент времени может нахо |
|||||||
диться в одном из m |
состояний ии |
и2,...,ит |
и |
меняет |
|||
свое состояние только |
в дискретные моменты |
времени |
|||||
t\, h , - - - , tN- |
Вероятностный переход |
системы |
U из од |
||||
ного состояния в другое задается некоторой |
переходной |
||||||
вероятностью |
pij(N). Это вероятность перехода |
из t-ro |
|||||
состояния в /-е в момент времени t = N. В общем |
случае, |
||||||
когда |
вероятности переходов Pij(N) |
зависят |
от |
времени |
|||
t = N, |
цепи называются |
неоднородными цепями Маркова. |
|||||
Если pij |
не зависят от времени tN, т. е. |
|
|
|
|||
P i i |
W |
= P |
|
|
|
|
(0.4.30) |
то цепь Маркова называется однородной. Такая цепь за дается матрицей переходных вероятностей
Рп |
|
Plm |
я — |
|
(0.4.31) |
Рт\ |
|
|
где рц (i, |
/ = 1 |
т) — вероятность перехода из t-ro |
состояния |
в /-е. При этом должно выполняться условие |
|
стохастичности |
матрицы я, т. е. |
|
2 |
1 |
(0.4.32) |
3 = 1
( i = l , . . . , т).
Для полного задания цепи Маркова необходимо иметь также вектор начальных вероятностей
Р<°>=(р, <»>,..., рт <°>), |
(0.4.33) |
||
где Pi(0> ( i = l , . . . , m ) |
— вероятность |
того, что |
система |
U в момент времени |
t = 0 находится в состоянии |
щ. |