ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 215
Скачиваний: 1
ГЛАВА II
|
|
164 |
|
|
|
|
|
|
Далее |
рассмотрим |
такой |
алгоритм |
самообучения, |
||||
когда |
р а с п р е д е л е н и е |
в ы х о д о в |
АХ^\ определяе |
|||||
мое формулой (2.1.2), |
п р е д с т а в л я е т |
б - ф у н к ц и ю , |
||||||
т. е. когда |
каждому состоянию |
WW автомата |
соответст |
|||||
вует |
один |
определенный |
его выход |
ДХ^') и |
функция |
|||
(2.1.3), определяющая переходы внутренних состояний
автомата, является случайной и не зависит |
от вектора |
ДХ: |
|
Pw(W)=p(W J V /W w _ , I A Q ' J V - I ) . |
(2.1.91) |
Эта зависимость реализуется заданием двух стохастиче ских матриц А0 и А\. Конкретный алгоритм самообуче ния, т. е. конкретный автомат, будет задан, если будут заданы конкретные матрицы А0 и А\. Такой алгоритм самообучения представляет собой вероятностный авто мат со случайными переходами и детерминированными выходами.
Пусть каждая координата wi (1=1, п) вектора
памяти W = ( w \ , . . . , wn) |
может находиться в одном из 2k |
состояний: |
|
o>,u> = d - ( / _ l ) 6 |
(2.1.92) |
(}=\,...,2k),
где w№ — j-e состояние памяти по 1-й координате.
Здесь
(rf>0)
d — число, задающее верхнюю и нижнюю границу изме нения координат Wi вектора W;
k — фиксированное натуральное число, характеризую щее количество дискрет обучения по одной коор динате.
Тогда вектор памяти W может находиться в одном из (2k)2 состояний, т. е. множество внутренних состояний автомата содержит (2k)2 элементов. Этот случай соот ветствует п = 2.
ПОИСК С САМООБУЧЕНИЕМ
165
Часто удобнее задавать не автомат, описывающий пе
реходы |
вектора W, а |
к о л л е к т и в |
и з п |
н е з а в и с и |
|
м ы х |
а в т о м а т о в , |
где каждый |
автомат |
коллектива |
|
описывает переходы по одной координате Wi |
(1=1, |
2, ... |
|||
... , п) |
вектора W [12—16]. В этом случае задаются |
пере |
|||
ходные матрицы каждого автомата из коллектива. По том по этим матрицам строятся матрицы переходных вероятностей всего коллектива автоматов, представляю щего более сложный автомат и задающего переходы век тора W из одних состояний в другие. Пусть стохастичес
кие матрицы порядка |
(2k) X(2k) |
|
r,i<°)(/) |
- r 1 , 2 f e W ( / ) |
|
Ro(l) |
|
(2.1.94) |
/•2ft,.( 0 ) (0 - r 2 h , 2 h ( 0 ) ( 0 |
|
|
rn^(l) |
ri,2ft( 1 ) (0 |
(2.1.95) |
|
|
|
W > ( 0 |
••r2 f t l 2 fc( 1 ) (0 |
! |
|
(1=1,..., |
n) |
являются переходными матрицами /-го автомата указан
ного коллектива (Ro(l) — при нештрафе; R\(l) — |
при |
||
штрафе). Обозначим через W( ( 'i' |
l i ' ' J состояние |
век |
|
тора памяти W, 1-я координата (/.= 1, . . . , |
п) которого |
на |
|
ходится в состоянии U, а через W^'i |
h |
in) — состояние, |
|
1-я координата которого находится в состоянии ji. Тогда
вероятность перехода |
W(»'i |
ч) |
->W<ip |
ь) |
будет опре |
||
деляться по формуле |
|
|
|
|
|
|
|
/>(W<^-.in )->W(i |
зп)) |
=P(w^b). >- W^M, . . . |
|
||||
. . . , Wn^"''-^ ffi>„<i»>) |
Я г. |
(I) |
|
|
(2.1.96) |
||
|
|
i=\ |
(ii,ji= |
|
\,...,2l). |
||
|
|
|
|
||||
Рассмотрим более |
подробно |
случай, |
когда |
п = 2. Из |
|||
формулы (2.1.96) получаем |
при |
нештрафе |
(AQ'<0) |
||||
P(W'<Pi-1 )2 '! +v.)-^ W((^-i)2ft+V2)/c = |
0) |
=Р(ш,(Рь |
•Wi (Р0- |
||||
ГЛАВА II
166
|
|
• даа(7.)/с |
= 0) =р<°> |
-l)2ft+72 |
||||
|
|
|
|
|
|
(P,-l)2ft+Vi,(P2 |
||
|
= r<°) |
(1)Г<°> (2), |
|
|
|
(2.1.97) |
||
где |
|
|
|
|
|
|
|
|
= |
2 |
2fe; |
p 2 = l , 2 |
2ft; |
|
|
||
Y i = |
1, 2, |
2fe; |
y 2 = l , 2 , . . . , 2 f t . |
|
|
|||
При |
штрафе |
(AQ'^O) |
имеем |
аналогичное |
выражение: |
|||
р |
|
|
=/-(1) (П/-С) (2) |
|
(2 1 98) |
|||
Следовательно, для вектора W имеем блочные переход |
||||||||
ные матрицы |
|
|
|
|
|
|
|
|
Л 0 |
= |
|
|
|
|
|
|
(2.1.99) |
|
|
|
|
|
|
|
|
(2.1.100) |
где блоки Рг-/°) и / V 1 ' (г, / = 1 , |
2&) равны |
следующим |
||||||
матрицам порядка (2k) X(2&): |
|
|
||||||
Я„<°> = г„№(1)Я 0 (2); |
|
|
|
|
(2.1.101) |
|||
Р«<»=г„<"(1)/?,(2). |
|
|
|
|
(2.1.102) |
|||
Здесь Ро (2) |
и Ri |
(2) — матрицы (2.1.94) и |
(2.1.95) при |
|||||
/ = 2 ; |
Г ц т (1) и |
г,/1 » |
(1) |
— |
элементы |
тех |
же матриц |
|
при / = 1.
В некоторых случаях коллектив состоит из одинаковых автоматов, которые переходят из данного состояния только в соседние состояния. При этом переходы авто мата такие, что при штрафе ( A Q ' ^ 0 ) автомат старается менять свое действие, т. е. с большей вероятностью пере ходит в ту сторону, где происходит смена его действия (выхода АХ); при нештрафе ( A Q ( , ) < 0 ) автомат старается
ПОИСК С САМООБУЧЕНИЕМ
167
закреплять это действие, т. е. удаляется от состояния, где происходит смена его действия.
Пусть в состояниях от d до-^- вероятность штрафа дей ствия автомата меньше, чем вероятность нештрафа, а в состояниях от — ^ до —d имеет место обратное. Тогда
матрицы |
переходных |
вероятностей |
Ro(l) |
и R\(l) ав |
|||||
томатов |
целесообразно |
задать |
[2, |
13] в |
виде матриц |
||||
Я о ( 0 = Я о = |
|
|
|
|
|
|
|||
г, г2 |
0 |
0 • о о о о о- • 0 0 0 |
|
||||||
г, 0 г2 |
0 • о о |
0 0 0- • 0 0 0 |
|
||||||
0 |
0 |
0 |
0 |
г, 0 г2 0 0 |
•0 0 0 |
(2.1.103) |
|||
0 |
0 |
0 |
0 |
0 г2 |
0 г, 0 • 0 0 0 |
||||
|
|||||||||
0 |
0 |
0 |
0 |
о о 0 0 0 |
г2 |
0 г, |
|
||
0 |
0 |
0 |
0 |
о о 0 0 0 |
0 Г 2 Г! |
|
|||
|
|
ft ft |
|
|
|
|
|
|
r2 |
0 |
0 • • 0 |
0 |
0 |
0 |
0 • • 0 |
0 |
0 |
/"2 0 |
Г\ |
0 • • 0 |
0 |
0 |
0 |
0 • • 0 |
0 |
0 |
0 |
0 |
0 |
0 • • r2 |
0 |
|
0 |
0 • • 0 |
0 0 |
(2.1.104) |
|
0 |
0 |
0 |
0 • • 0 Г\ |
0 |
г2 |
0 • • 0 0 0 |
||||
|
||||||||||
0 |
0 |
0 |
0 • • 0 |
0 |
0 |
0 0 • •• гх |
0 г2 |
|
||
0 |
0 |
0 |
0 • • 0 |
0 |
0 |
0 |
0 • • 0 |
Г\ Г2 |
|
|
ГЛАВА II
168-
Эти матрицы должны быть стохастическими, т. е.
ri + r a = l . |
|
|
|
|
(2.1.105) |
|
|
При этом |
предполагается, что имеет место неравенство |
||||||
r i > r 2 . |
|
|
|
|
|
(2.1.106) |
|
Из формул (2.1.102) |
и |
(2.1.101) |
и |
матриц |
(2.1.103) |
и |
|
(2.1.104) |
следует, что |
в |
этом случае |
матрицы Л 0 и |
Л, |
||
имеют блочный вид (см. матрицы |
(2.1.107) |
и (2.1.108)). |
|||||
В этих матрицах подматрицы Л ( 0 ) , ^ 2 ( 0 ) и /V 1 ), / у 1 ) равны
Pli°) = rlRM; р 2 ( 0 ) = Г 2 ^ ( 0 ) . |
|
|
|
(2.1.109) |
||||
|
|
|
|
|
|
(2.1.110) |
||
|
|
/уо) |
/уо> |
0 |
0 ••• |
0 |
0 |
|
|
|
Р,(0) |
0 |
|
0 ••• |
0 |
0 |
|
|
|
0 |
0 |
0 0 • • Л ( 0 ) |
0 |
|||
|
|
0 |
0 |
0 |
0 •• • |
0 |
/у°> |
|
|
|
0 |
0 |
0 |
0 • • |
0 |
0 |
|
|
|
0 |
0 |
0 |
0 • • |
0 |
0 |
|
|
|
|
|
|
к |
|
|
|
|
|
/ у 1 ) |
|
0 |
0 ••• |
0 |
0 |
|
|
|
/ у п |
0 |
Л ( 1 ) |
0 ••• а |
0 |
||
Ах |
= |
0 |
0 |
0 |
0 • • Я2 (1) |
0 |
||
0 |
0 |
0 |
0 • • |
0 |
Я,<1) |
|||
|
|
|||||||
|
|
о |
о |
о |
о - |
о |
о |
|
|
|
о |
о |
0 |
0 - 0 |
|
о |
|
ПОИСК С САМООБУЧЕНИЕМ
169 |
|
|
|
|
где /?<°) и /?0> — матрицы |
(2.1.103) и |
(2.1.104); |
||
Г) и г 2 — отличные |
от |
нуля |
элементы этих |
|
матриц, |
удовлетворяющие |
условиям |
||
(2.1.105) |
и (2.1.106). |
|
|
|
Таким образом, в двумерном |
случае |
(я = 2) |
переход |
|
ные матрицы автомата поиска выражаются через пере ходные матрицы одномерных автоматов поиска, умно женных на переходные вероятности этих автоматов. Ана логичным свойством обладают переходные матрицы ав томата поиска в я-мерном случае, если этот автомат об разован из коллектива одинаковых независимых автома тов, действующих по всем параметрам оптимизируемого объекта. Это обстоятельство облегчает исследование процесса оптимизации в многомерном пространстве.
/у°> |
0 |
|
|
|
|
|
(2.1.107) |
|
0 |
/ у о |
|
|
|
|
|
||
) |
|
|
|
|
|
|||
|
|
|
|
Р 2 < 0 ) |
0 |
Pi №) |
|
|
|
|
|
|
0 |
Р2<°> |
/ у о ) |
|
|
0 |
0 |
0 •• |
0 |
0 |
0 |
|
||
0 |
0 |
0 •• |
0 |
0 |
0 |
> к |
||
|
|
|
|
|
|
|
||
р,(1) |
0 |
0 |
- |
0 |
0 |
0 |
(2.1.108) |
|
0 |
/ у п |
0 |
- |
0 |
0 |
0 |
||
|
||||||||
О |
О |
0 - Л ( 1 ) |
0 |
Р2<>) |
|
|||
0 |
0 |
0 ••• |
о |
/ у ° |
P2(i) |
|
||