ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 228
Скачиваний: 1
ГЛАВА II
235 |
|
|
С в о й с т в о |
3: |
|
Pij, |
если |
i, / e { W } - или i, / e { W } + ; |
Pih |
если |
t'e={W}- и /<={W} + или t'e{W} + |
|
|
и / e { W } - . |
(2.7.6)
Для доказательства равенств (2.7.2) необходимо пред варительно доказать, что [16] сумма предельных вероят ностей pi и рг+s состояний W<*> и W<i + S ) постоянна для
всех i (i = 1, 2, ... , s) и равна ^ п " » т - е -
1
(2.7.7)
2n-i
( t = 1, 2, |
s). |
Для этого запишем систему уравнений, которой удов летворяют предельные вероятности состояний системы
|
2s |
П= ^ |
PaPi |
3=1
( t = l , . . . , s ) ;
(2.7.8)
2s
Phi+sPi-
3=1
Используя 1-е и 2-е свойства вероятностей Pij, систему уравнений (2.7.8) запишем в виде
3=1
(2.7.9)
p i + s = ^ |
Pii{Pj + Pj+s) |
3=1
( t = l , . . . , S) .
ПОИСК С САМООБУЧЕНИЕМ
237
Сложив уравнения системы (2.7.9), соответствующие со стояниям W<»' и W ( ' + s ) , получим
P i + P i + S = ^ |
(Ри+Ра) |
(Pi+Pj+s) |
(2.7.10) |
|
3=1 |
|
( i = l , . . . , s ) . |
|
|
|
Смысл формулы (2.7.7) состоит в том, что система (2.7.10) имеет следующее решение:
1 |
Pi+s |
(2.7.11) |
|
|
2""1
(i=l,...,s).
Действительно, подставив (2.7.11) в систему (2.7.10), по лучим
^(PH + Pn) = l |
(2-7.12) |
3=1
( i = l , . . . , s ) .
Из 1—3-го свойств вероятностей р ц следует
s |
2s |
^(Pii |
+ Pn)= |
2!PU=1 |
(2-7.13) |
|
3=1 |
|
|
3=1 |
|
что и завершает |
доказательство |
формулы (2.7.7). |
||
Выражения |
(2.7.2) получаем, |
подставляя соотноше |
||
ния (2.7.11) в уравнения системы (2.7.9). |
||||
Рассмотрим |
с л у ч а й с п о м е х о й [16]. Предполага |
|||
ется, что на вычисленное значение функции Q(X) накла дывается помеха е(а), представляющая нормально рас пределенную случайную величину с математическим ожи данием, равным нулю, и дисперсией о2 . Тогда поощрение или штрафование автоматов коллектива производится од
новременно в зависимости от знака |
суммы |
AQ' = AQ + Ae, |
(2.7.14) |
где Ае — нормально распределенная случайная величина
ГЛАВА II
238
с математическим ожиданием, равным нулю, и диспер сией 2а2 .
Обозначим
S i = Bep (AQ'«>>0/AQ«><0);
S i = l - s , = Bep (AQ'<*><0/AQW<0).
В силу линейности функции Q(X) и симметричности рас пределения помехи е(б) относительно ее нулевого мате матического ожидания для состояний ie{W}+ (i = = s + 1 , . . . , 2s) вероятности штрафа и нештрафа соответ ственно равны
Вер ( A Q ' W > 0 / A QW > 0) = 5 4 ;
|
|
(2.7.1о) |
Вер |
(AQ , (')<0/AQ<«)>0)=s i l |
|
т. е. |
|
(2.7.17) |
St = |
S j + s ; Sj = Sj+s. |
Докажем, что предельные вероятности Рг и pj+s со
стояний |
W<i> вектора W |
( i = l , . . . , s ) при наличии помех |
|
определяются по формулам [16] |
|||
|
s |
|
|
Р г = |
2^7, |
(SjPit + SjPjt); |
|
|
|
|
(2.7.18) |
Р'-+»= "^ГГЛ ^ |
(SjPn + |
SjPji) |
|
|
3=1 |
|
(t = l , . . . , s ) . |
|
|
|
|
Предварительно покажем, что в случае действия по мех справедливо то же утверждение, что и для случая, когда нет помехи, т. е.
Pi+Pi+s=2^1 |
(2.7Л9) |
|
(i=l,...,s). |
Запишем систему уравнений, которой удовлетворяют стационарные вероятности pt и pi+s состояний W ( i ) и W«+«> (i = l , . . . , s ) :
ПОИСК С САМООБУЧЕНИЕМ
239
2s
Pi= J5j (SjPa + SjPji)pj;
3=12 s (2.7.20)
pi+s= J? (SjPii + SiPji)Pj
3=1
( t = l , . . . , s ) .
Используя свойства вероятностей pji (2.7.6) и Si (2.7.15), (2.7.17), запишем систему (2.7.20) в виде
Pi= |
(SjPn + Sjpji) {Pj + |
Pi+s); |
|
|||
|
'"Х |
|
|
|
|
(2.7.21) |
Pi+s= |
(Sjpji + Sjpji) |
(Pj + |
Pj+s). |
|
||
Складывая уравнения |
системы (2.7.21), |
соответствую |
||||
щие |
состояниям |
W ( i ) и W ( i + s ) |
( i = l , . . . , s ) , |
получим |
||
|
|
s |
|
|
|
|
P i |
+ pi+s= |
Jj? |
(pji + рц) |
(pi + pi+s) |
(2.7.22) |
|
|
|
3=1 |
|
|
( i = l , . . . , s ) . |
|
|
|
|
|
|
||
Подставив (2.7.19) в (2.7.22), докажем высказанное ут верждение:
s |
2s |
(2-7-23) |
2 |
(рп+рп)=2jpi>=i- |
|
3=1 |
3=1 |
|
Формулы (2.7.18) для предельных вероятностей состоя
ний получим, подставив (2.7.19) в |
(2.7.21). |
.... |
|
§ 2.8. С Р А В Н Е Н И Е |
А Л Г О Р И Т М О В |
СА М О О Б У Ч Е Н И Я
Впараграфе 2.6 было показано, что при оп
тимизации в двумерном пространстве алгоритм оптими зации коллективом независимых автоматов в отношении
гллвл II
240
среднего приращения функции Q(X) на одном шаге эк
вивалентен алгоритму покоординатного самообучения |
|
при случайном |
поиске. |
Это означает, |
что к определенным параметрам одного |
алгоритма можно подобрать такие параметры второго алгоритма, при которых результаты действия обоих будут одинаковыми. В этом параграфе рассмотрим другие ас пекты эквивалентности алгоритмов самообучения.
ЭКВИВАЛЕНТНОСТЬ А В Т О М А Т О В П О РАСПРЕДЕЛЕНИЮ
ИХ Н А Ч А Л Ь Н Ы Х СОСТОЯНИЙ [21]
Вработах [21, 26] показано, как определить
вероятность выходного сигнала ДХ'-»', если на вход авто мата был подан входной сигнал с, для случая автомата, вероятности переходов и выходов которого зависят только от его состояния и от его входного сигнала, но не зависят от выходного сигнала на предыдущем такте. Ве роятности переходов, описывающих алгоритм самообу чения при случайном поиске, в общем случае зависят также от выходного сигнала автомата на предыдущем
шаге. |
Распространим |
на этот случай методику и фор |
мулы, изложенные в работах [21, 26]. |
||
По формулам (2.1.8) |
и (2.1.9) имеем |
|
Вер |
(Wjv+i^'/WivW), |
ДХ.уО), с) •Bep(AX,Y (i)/WI V (i i)) = |
|
= <7ыРг,г2<с>. |
(2.8.1) |
Просуммировав это выражение по всем / (/' = 1 , . . . , v), находим вероятность перехода автомата из состояния W<*i) на iV-м шаге в состояние W( ") на (М+1)-м шаге при подаче на его вход сигнала с:
•и |
|
Вер ( \ W = V W W < * > , с) = 2 <7vPv2<c>, |
(2.8.2) |
где v — количество выходных сигналов автомата. Переписывая это выражение в матричной форме,
имеем следующие матрицы перехода Л 0 и А\ для авто мата, переходы которого зависят от его выходов:
ПОИСК С САМООБУЧЕНИЕМ
241
Л0= |
2 |
Qi(i)A0(j); |
|
|
|
j = 1 |
|
|
(2.8.3) |
М= |
^Q<(/M,(/). |
|
||
Далее, |
аналогично |
тому, как это сделано |
в работах |
|
[21, 26], введем матрицу |
|
|||
7(ЛХ<;>/с)=Лс (2;(/), |
(2.8.4) |
|||
где Л с |
— матрица |
(2.8.3); |
|
|
Qi(j) |
— |
матрица |
(2.1.21). |
|
Элемент матрицы (2.8.4) обозначает вероятность пере
хода |
автомата из состояния W<»'> в состояние W'i 2 ) |
и по |
|||
явления на его выходе сигнала AX<J>, если |
на вход |
авто |
|||
мата |
был подан сигнал с, т. е. |
|
|
||
/<„,-,(АХ<я/с)=р(ЛХО->, |
W<*->/W«->, с) = |
|
|
||
|
(2V |
<i,,jphi2 |
(/) ) '//.;• |
(2.8.5) |
|
31=1
Тогда, согласно формуле (0.3.20), переходная матрица
автомата |
при |
входной |
последовательности |
(CjC2 ...cN ) |
|||
и |
выходной |
(AXiAX 2 . .. AXJV) |
определяется |
формулой |
|||
Т (АХ]АХ2 . . . AXWciCa . . . cN) = Т (ДХ,/с,) Т (АХ2/с2) . . . |
|||||||
|
...T(AXN/cN). |
|
|
|
(2.8.6) |
||
Введем |
обозначение |
|
|
|
|||
Ppi( 0 ) (AX,AX2 . . . AXl V /c,c2 . . .CN) |
= Pi^Ti(AXlAX2 |
. . . |
|||||
|
. . . AXN/CiC2. |
.. cN)eit |
|
(2.8.7) |
|||
где |
e,i — вектор, элементы которого равны единице; |
||||||
Рг( 0 ) —• |
начальное |
распределение внутренних состоя |
|||||
|
|
ний автомата |
Ai\ |
|
|
||
r,(AXiAX 2 . . . AXN/c{c2 |
. . . cj V ) — |
|
|||||
переходная матрица входной-выходной последователь ности автомата А*.
16 — 2014