ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 208
Скачиваний: 1
ГЛАВА II
138
WN = W(WN_U |
АХд'-ь A Q V - i ) . |
(2.1.3) |
В общем случае эта функция может быть и случайной. На изменение длины вектора памяти W накладывается ограничение
| W | ^ d y " n |
(2.1.4) |
(d = const), |
|
где я — размерность пространства {W}. |
|
Далее предполагается, что вектор памяти |
W, а также |
смещение АХ могут принимать значения из конечных множеств
W G { W < 4 , |
W(2), . . . , W<M >}; |
(2.1.5) |
|||
ДХе={ДХО>, АХ<2), . . ., ДХ<*>}. |
(2.1.6) |
||||
Что касается |
приращения |
функции |
качества AQ', то нас |
||
будут интересовать только два значения: |
|
||||
sgnAQ' = C |
= { 1' |
е с л и Д |
( ^ 0 ' |
( 2 17) |
|
|
I 0, |
если |
A Q ' < 0 . |
^ |
; |
Поиск с самообучением |
определим |
как вероятностный |
|||
автомат следующим образом. Пусть состоянием авто мата является вектор памяти W, выходом автомата — вектор смещения АХ, а его входом sgnAQ' = c. Тогда множество состояний, множество выходов и мно жество входов автомата будут определяться соответст венно формулами (2.1.5), (2.1.6) и (2.1.7). Функция пере ходов автомата будет определяться выражением (2.1.3), а функция выходов — соотношением (2.1.2). Отметим,
что по формуле (2.1.3) |
изменение |
состояний |
автомата |
WJV-1-^-WJV зависит также |
от выхода |
автомата |
ДХ^_1 на |
(N— 1)-м шаге. Таким образом, с учетом предположений (2.1.5) и (2.1.6) алгоритмы самообучения при случайном поиске описываются как вероятностные автоматы с ко нечным числом состояний и конечным числом выходов. При этом вероятности выходов автомата зависят только от его состояния и не зависят от его входа, а вероятности
ПОИСК С САМООБУЧЕНИЕМ
139
переходов автомата из одного состояния в другое зави сят кроме состояния и входа автомата также от его вы
хода на предыдущем |
шаге. |
|
|
|
|
|
|
|
|||||
Введем следующие |
обозначения: |
|
|
|
|
||||||||
Р М . ( с ) ( / ) = В е р |
( W ^ ^ - ^ W J V + I ^ / A X ^ ^ A X ^ . C ) |
(2.1.8) |
|||||||||||
|
|
|
|
|
|
(i'b |
i 2 = |
\,...,т; |
с==0, 1); |
||||
<7 = Вер (AX |
W |
= AX«)/W |
J V |
= W<*)) |
|
|
|
(2.1.9) |
|||||
У |
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
(i' = |
1, . . . , |
m; |
у'=1, |
. . . , v); |
||||
s, = Bep |
(с=1/АХ = АХ0)) |
|
= |
у [ |
1 + Ф |
( ~ ^ ) ] |
(2.1.10) |
||||||
|
|
Z |
|
|
|
|
|
|
(j=\,...,v); |
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
||
Ф(г) |
= |
—— J e~t2dt |
— |
интеграл |
вероятности. |
Здесь |
|||||||
|
|
Уя о-7 |
|
|
|
|
|
|
|
|
|
|
|
Рг,л,м |
(/) |
обозначает |
вероятность |
|
перехода |
автомата из |
|||||||
состояния W ( i i ) |
|
в состояние |
W<»2), если на |
предыдущем |
|||||||||
шаге |
поиска на |
выходе автомата |
появился |
сигнал АХ<-»>, |
|||||||||
а потом на его вход поступил входной сигнал с; цц — ве роятность появления на выходе сигнала ДХ<з) при нахождении автомата в состоянии W'1 ''; s'-*' — вероят
ность штрафа /-го |
действия (выхода) автомата. |
||
П е р е х о д н у ю |
2v |
ф у н к ц и ю |
автомата будем зада |
вать при помощи |
следующих |
стохастических матриц: |
|
для с = 0 |
|
|
|
/>11<°>0') |
- / W 0 ) ( / ) |
|
|
Ао(1) = |
|
|
(2.1.11) |
для с = 1 |
|
|
|
?,><"(/) |
- / W ' > ( / ) |
(2.1.12) |
|
Л , ( / ) = |
|
|
|
В ы х о д н у ю ф у н к ц и ю автомата |
задаем при по- |
мощи прямоугольной матрицы порядка |
mXv |
ГЛАВА II
140
qvi qw (2.1.13)
q-mi ••• q-n
Далее, используя формулы (2.1.8) и (2.1.9), находим
совместную |
вероятность события, состоящего в том, что |
||||||
у автомата |
появился |
выход Д Х ^ и автомат потом пере |
|||||
ходит из состояния |
W ( i i ) |
в состояние W ( i 2 ) |
при |
условии, |
|||
что на его вход поступил сигнал с: |
|
|
|
||||
Вер (Ww«-> - * V W 4 ДХл г = ДХ(Я/с) |
=qi[jPiii2(j). |
||||||
|
|
|
|
|
|
|
(2.1.14) |
Совместная |
вероятность |
следующих трех |
событий: |
||||
WN (».>->W^+i<4 |
ДХ№ = ДХ<Я И с = 1 |
равна |
|
|
|||
В е р ( \ У ^ ) ^ \ У д Г + 1 |
^ , ДХл г = ДХи), |
c = l ) = s j < 7 V p M i n M / ) . |
|||||
|
|
|
|
|
|
|
(2.1.15) |
Аналогично для с = 0 имеем |
|
|
|
||||
Вер (WWW> |
W w + l < 4 ДХ№ = ДХ«), с = 0) = |
|
|||||
= |
( l - s j ) ^ i 1 < , w > ( / ) . |
|
' |
(2.1.16) |
|||
Суммируя эти вероятности, получаем совместную вероят
ность перехода автомата |
из состояния W^1 ' в состояние |
|||
W(*2) при появлении сигнала ДХ( ^ на его выходе: |
||||
Вер ( W w < * - > W w + 1 ( 4 |
AXN |
= AXU))=Pii,.(/) |
= |
|
|
=qU^-si)Pb4w(i) |
+ s j P i ^ 4 j ) l |
|
|
|
|
|
|
(2.1.17) |
Суммируя вероятности |
Pi^U) |
по всем выходам ДХ<-?> |
||
(j = l,..., |
v), находим полную вероятность |
перехода ав |
||
томата |
из состояния W ( ! | ) |
в состояние W'J '2 ': |
|
|
ПОИСК С САМООБУЧЕНИЕМ
141
Рчч- ^ a ( l - S i ) P ; l i 2 < ° > ( / ) +*>Рг^ЧП] |
(2.1.18) |
3=1 |
,т). |
{h,i2=\,... |
Следовательно, полное функционирование автомата в случайной среде (2.1.10) описывается цепью Маркова с переходными вероятностями (2.1.18). Запишем эту цепь Маркова в виде стохастической матрицы порядка тХт
Ри |
••• Pit |
(2.1.19) |
А = |
|
|
Pml ••• рп |
|
|
где рцц |
(I'I, t 2 = l , . . . , m ) определяются |
формулой |
(2.1.18). Предельные вероятности этой цепи Маркова,
если она однородная и эргодическая, находятся |
как ре |
||
шение системы алгебраических |
уравнений |
|
|
Р = |
Л'Р, |
|
(2.1.20) |
где Л |
' — транспонированная |
матрица (2.1.19); |
|
Р |
— вектор предельных |
вероятностей; |
Р=(ри... |
...,рт).
В некоторых случаях для исследования матрицы (2.1.19) удобнее представить ее при помощи более прос тых матриц. Для этого вводим квадратные матрицы
Qi(j) и S(j) порядка т:
ям |
о |
о - |
0 |
0 |
0 |
q2j |
0 •• |
0 |
0 |
Qi(i) = |
|
|
|
(2.1.21) |
|
|
|
|
|
0 |
0 |
0 ••• 0 |
qn |
|
Sj |
0 |
0 ••• 0 |
0 |
|
0 |
S; |
0 ••• 0 |
0 |
|
S(/) = |
|
|
|
(2.1.22) |
0 |
0 |
0 ••• 0 |
s j |
|
ГЛАВА II
142
-При помощи введенных матриц (2.1.21) и (2.1.22) и мат риц (2.1.11), (2.1.12) матрица Л представляется в виде
v |
(2Л-23) |
А= 2[{I-S{j))Qi{i)Ao{j)+S{j)Qi{i)Aim |
где / — единичная матрица порядка т.
Отметим, что при помощи конечных вероятностных ав томатов, переходные функции которых зависят от их вы ходов, представляется любой алгоритм дискретного са мообучения (векторы W и АХ принимают значения из дискретного множества векторов). Рассмотрим некото рые частные случаи автоматов, функционирование кото рых описывается цепью Маркова с матрицей переходных
вероятностей |
(2.1.23). |
|
|
|
||
1. |
Вероятностный автомат, переходная |
функция |
кото |
|||
рого |
не зависит |
от его выходов. |
В этом |
случае все мат |
||
рицы Ac(j) |
при |
фиксированном |
с равны между |
собой, |
||
т. е. |
|
|
|
|
|
|
Л 0 ( / ) = Л 0 ; |
A i ( / ) = A , |
|
|
(2.1.24) |
||
|
|
|
0 = 1, |
|
|
|
Матрица Л равна |
|
|
|
|||
A=(I-S*)A0 |
+ S'AU |
|
|
(2.1.25) |
||
где |
V |
|
|
|
|
|
|
|
|
|
|
|
|
3=1
0 |
0 |
|
|
V |
о |
(2.1.26) |
|
о |
|||
|
V
оо