ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 211
Скачиваний: 1
ПОИСК С САМООБУЧЕНИЕМ
147
где
W<*>= ( ш ^ ) , . . . , wn^). |
(2.1.42) |
Теперь в общем виде определены все величины, необ ходимые для составления матрицы переходных вероят ностей (2.1.23). После нахождения вектора предельных вероятностей Р = (ри •. •, Рп) для этой цепи Маркова оп ределяется средний выход автомата, т. е. среднее смеще ние в пространстве X на одном шаге поиска:
|
т |
2п |
|
М[АХ}= |
£Pi(2 |
4iMU))- |
(2.1-43)' |
|
i=l |
j=l |
|
В этой формуле сумма |
|
||
M[AX/W«>] = J^ijAX") |
(2.1.44) |
||
является |
средним |
выходом |
автомата при его нахожде |
нии в состоянии W*'*, т. е. средним смещением в прост |
|||
ранстве |
X при значении вектора памяти W = W<*>. Сред |
||
нее смещение по направлению градиента определяется как скалярное произведение векторов Л1[АХ] и гради
ентного |
вектора |
а = ( а ь . . . , ап) |
оптимизируемой |
функ |
||||
ции Q (X). |
|
|
|
|
|
|
|
|
Далее |
рассмотрим |
несколько |
конкретных |
видов |
фор |
|||
мулы самообучения |
(2.1.3). Пусть функция |
4r = 4 R ( W N _ B |
||||||
A X J V - I , |
A Q V - i ) |
является |
д е т е р м и н и р о в а н н о й и |
|||||
имеет вид |
|
|
|
|
|
|
|
|
|
W N - I - 6 sign AQ'JV-I sign A X J V _ B |
|
|
|||||
|
|
|
|
|
|
если |
I I |
^d]/n; |
|
T~~~, |
|
|
|
если |
\VfN\>dyn, |
||
|
1 |
1 |
|
|
|
|
(2.1.45) |
|
где вектор sign A X определяется как |
|
|
||||||
sgn A X = (sgn |
Axu |
sgn |
Axn); |
|
(2.1.46) |
|||
10*
ГЛАВА II
|
148 |
|
|
sgnz = Jf — 1, если 2 < 0 ; |
(2.1.47) |
||
Б |
\ + 1 , если 2 |
$гО. |
|
Постоянная б здесь определяется формулой
|
|
|
|
|
|
|
(2.1.48) |
|
где k — любое |
фиксированное натуральное |
число |
(k — |
|||||
= 1, 2, |
3,... ); |
d^O. |
Предполагается, |
что каждая ко |
||||
ордината |
wi (1=1,..., |
п) |
вектора памяти |
W=(wi,... |
||||
...,wn) |
может |
находиться в одном из следующих |
2k+1 |
|||||
состояний: |
|
|
|
|
|
|
|
|
wi = d, |
( £ - 1 ) 6 , (/г — 2)6, .... б, 0, - б , - 2 6 , . . . , - |
|
||||||
|
-(k-l)6,-d. |
|
|
|
(2.1.49) |
|||
Тогда вектор памяти W может находиться в одном из |
||||||||
(2k + 1) X (2k + 1) состояний, т. е. множество |
внутренних |
|||||||
состояний |
автомата |
(2.1.5) |
содержит |
(2k + 1) X |
(2k+1) |
|||
элементов. Самообучение заключается в переходе век
тора W из одного состояния |
в другое W<J> в соот |
ветствии с формулой (2.1.45). |
|
Видно, что формула (2.1.45) определяет вероятност ный автомат, вероятности переходов которого зависят от его выходов. Переходы этого автомата определяются стохастическими матрицами (2.1.11) и (2.1.12). По строим эти матрицы. Для удобства перепишем формулу (2.1.45) в виде двух формул в отдельности для случая
нештрафа (AQ'JV<0) и для случая |
штрафа ( A Q ' J V ^ O ) : |
для AQ'JV <0 |
|
WJV-I + 6 sign Д Х Л ' _ Ь если |
| W A - | <d^n; |
|
(2.1.50) |
для A Q V ^ O имеем
Wjv_i — 6 sign A X J V - I , если |WA -| ^d^n;
(2.1.51)
если \WN\>d]ln.
|
ПОИСК С САМООБУЧЕНИЕМ |
149 |
— |
Первая из полученных формул (2.1.50) задает матрицы Ao(i) ( / = 1 . • • •, v), а в т о р а я — (2.1.51) — матрицы Ai(/)
(j=l,...,v).
На рис. 2.1.2 показаны пространства {X} и {W} для
Рис. 2.1.2. Пространство выходов ДХ(') и пространство состоя ний W<J'> автомата.
AQ'<0
4X = 4 X W |
АХ-АХЮ |
Рис. 2.1.3. Переходы автомата при нештрафе (AQ'<0).
ГЛАВА II
|
|
150 |
|
|
|
|
|
|
|
|
|
|
|
•случая, |
когда |
п = 2 и когда |
количество состояний W ( i ) |
||||||||||
вектора W равно |
количеству |
возможных |
смещений Д Х ^ |
||||||||||
в пространстве |
{X}, т. е. когда |
m = 2 n = 4. |
Там же по |
||||||||||
казана |
нумерация |
векторов |
ДХ<-<) и W ( ! ) . На рис. 2.1.3 |
||||||||||
представлены |
полученные по формуле |
(2.1.50) переходы |
|||||||||||
автомата из состояния W<*>> в состояние |
W'i2> при не |
||||||||||||
штрафе |
(AQ'<0) |
|
для различных |
значений |
выхода ДХ( ^ |
||||||||
( / = 1 , 2, 3, 4) |
автомата. Исходя |
из данного |
на рис. 2.1.3 |
||||||||||
графа |
переходов |
при b^d |
|
можно написать |
следующие |
||||||||
матрицы Л 0 (/) переходных вероятностей: |
|
|
|
||||||||||
|
|
1 0 |
0 |
0 |
|
|
|
0 |
1 0 |
0 |
|
||
Л0 (1) |
= |
1 0 |
0 |
0 |
А0{2) |
= |
0 |
1 0 |
0 |
|
|||
1 0 |
0 |
0 |
0 |
1 0 |
0 |
|
|||||||
|
|
|
|
|
|
||||||||
|
|
1 0 |
0 |
0 |
|
|
|
0 |
1 0 |
0 |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
(2.1.52) |
|
|
0 |
0 |
1 0 |
|
|
|
0 |
0 |
0 |
1 |
|
|
Л ( 3 ) = |
0 |
0 |
1 |
0 |
Л0 |
(4) |
= |
0 |
0 |
0 |
1 |
|
|
0 |
0 |
1 0 |
0 |
0 |
0 |
1 |
|
||||||
|
|
|
|
|
|
||||||||
|
|
0 |
0 |
1 0 |
|
|
|
0 |
0 |
0 |
1 |
|
|
На рис. 2.1.4 показаны полученные по формуле (2.1.51) переходы автомата из одного состояния в другое при штрафе (AQ'^O) для различных ДХ^'>. Исходя из дан ного на рисунке графа имеем следующие матрицы пере ходных вероятностей A j (/) (/=1,2,3,4) :
|
|
0 |
0 |
0 |
|
|
0 |
0 |
1 0 |
|
Al(l) |
= |
0 |
0 |
0 |
|
Л, (2) |
0 |
0 |
1 0 |
|
0 |
0 |
0 |
|
0 0 |
1 0 |
|||||
|
|
|
|
|||||||
|
|
0 |
0 |
0 |
|
|
0 0 |
1 0 |
||
|
|
|
|
|
|
|
|
|
(2.1.53) |
|
|
|
0 |
1 0 |
0 |
|
1 0 |
0 0 |
|||
Л,(3) |
= |
0 |
1 0 |
0 |
Л.(4) |
1 0 |
0 0 |
|||
0 |
1 0 |
0 |
1 0 |
0 0 |
||||||
|
|
|
||||||||
|
|
0 |
1 0 |
0 |
|
1 0 |
0 0 |
|||
ПОИСК С САМООБУЧЕНИЕМ
151
Рис. 2.1.4. Переходы автомата при штрафе (AQ'SsO).
Матрицы Л0 (/) |
и А\(1) удовлетворяют равенствам |
|||
Л 1 ( 1 ) = Л 0 ( 4 ) ; Л 1 ( 2 ) = Л 0 ( 3 ) ; |
|
4 ) |
||
Л , ( 3 ) = Л 0 ( 2 ) ; Л 1 ( 4 ) = Л 0 ( 1 ) . |
|
|
||
Определим вид следующей |
матрицы: |
|
||
Л (/) = Qi (/) [ (/ - 5 (/)) Л 0 |
(/) + S (/) Л, (/) ] |
(2.1.55) |
||
|
|
|
(/=1,2,3,4) . |
|
Учитывая равенства (2.1.54), имеем: |
|
|||
^(1) =С2*(1)[(/ - 5(1))Л 0 (1) |
+ 5 ( 1 ) Л 0 ( 4 ) ] ; |
|
||
Л (2) =Qi(2)[(I |
— S(2))Л0(2) |
+ 5 ( 2 ) Л 0 ( 3 ) ] ; |
|
|
4 ( 3 ) = Q , ( 3 ) [ ( / - S ( 3 ) M o ( 3 ) + S ( 3 M o ( 2 ) ] ; |
( 2 ' L 5 6 > |
|||
Л (4) = Q j ( 4 ) [ ( / —S(4))Л0 (4) |
+ 5 ( 4 ) Л 0 ( 1 ) ] . |
|
||
ГЛАВА II
152
Отметим, что если во вторых слагаемых этих формул матрица S(j) зависит от номера /, то матрица А0 зависит •от номера (5 — / ) . Суммируя равенства формулы (2.1.56), находим
4 |
|
|
Л= ^ |
[Qi(/) |
(IS(j))+Qt(5-j)S(5-j)]A0(j). |
*-1 |
|
(2.1.57) |
Поскольку матрицы Q,(/) и S(j) диагональные, матрица
Q(!)=Qi(j)(I-S(j))+Qi(5-j)S(5-i) |
(2.1.58) |
также является диагональной. Ее элементы, как не трудно понять, вычисляются по формуле
9i 0") = 9 f j ( l - S j ) +q{,(v+i-j)Sv+i-h |
(2.1.59) |
где v — количество выходов автомата;
.qij\ — элементы матрицы (2.1.13);
Sj и s„+i_j определяются формулой (2.1.10).
Используя формулы (2.1.59) и (2.1.57), находим мат рицу (2.1.60) переходных вероятностей цепи Маркова,
описывающей |
функционирование |
алгоритма |
самообуче |
|||||||
ния |
(2.1.45) в случайной |
среде |
(2.1.10). В этой |
матрице |
||||||
Qii |
(1 \ / = 1 . . - . , 4 ) |
— элементы |
матрицы Qif, |
SJ (/== |
||||||
= 1,...,4) |
— |
вероятность |
штрафа |
действия |
ДХ^'' авто |
|||||
мата, определяемая формулой (2.1.10). |
|
|
||||||||
|
|9и ( 1 |
- S i ) |
+quSi |
912(1 |
- s 2 |
) |
+913S3 |
|
|
|
|
921(1 |
— S\) |
+924^4 |
922(1 |
— S2) +923S3 |
|
|
|||
|
'981 (1 |
- S i ) |
+934S4 |
932 (1 |
- s 2 ) |
+933S3 |
|
|
||
|
941 (1 |
~ s l ) |
+944S4 |
942(1 |
- s 2 ) |
+943S3 |
|
|
||
|
91з (1 |
- S 3 ) |
+912S2 |
9 H ( 1 |
- s 4 ) |
+9llSl |
|
|
||
|
923 (1 — S3) +922S2 |
924 ( 1 |
- s 4 ) |
|
+ 9 2 1 S 1 |
|
(2.1.60) |
|||
|
9зз(1 - S 3 ) |
+ 9 3 2 S 2 |
934(1 -Si) |
|
+ 9 3 l S i |
|
||||
|
|
|
|
|||||||
|
943 (1 — S 3 ) -f-<742s 2 |
944(1 |
- s 4 ) |
+<74iSi |
|
|
||||