ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 201
Скачиваний: 1
ГЛАВА I
92
Предельные вероятности цепи Маркова равны
Pi=P*=-£\ |
P2=—sr, |
pa= — |
(l-Si); |
(1.7.19)
Рис. 1.7.3. Графы переходов автомата для случая п>2.
ПОИСК БЕЗ САМООБУЧЕНИЯ
93
Средний штраф рабочих шагов
|
|
|
|
|
|
|
|
(1.7.20) |
а среднее приращение показателя качества |
|
|
||||||
M [ A Q ] = | - [ ( l - 2 s 1 ) a , + |
(l-2s4)a2]=—У[ ф(~) |
а , + |
||||||
|
|
|
|
|
|
|
|
(1.7.21) |
При a-Я) имеем |
|
|
|
|
|
|
||
Рср.р->0; |
M |
[ |
A |
Q ] ( |
a |
i + a2 ), |
|
(1.7.22) |
а при а - > о о |
|
|
|
|
|
|
|
|
Р с Р . р - > | - ; |
|
MAQ1 — 0. |
|
|
(1.7.23) |
|||
|
|
|
|
|||||
3. Многомерный |
случай |
( я > 2 ) . |
|
|
||||
Q ( X ) = ^ й Л ; |
|
^ а г |
2 |
= 1 . |
|
(1.7.24) |
||
г=1 |
|
|
г=1 |
|
|
|
|
|
Графы переходов |
автомата |
для этого случая |
показаны |
|||||
на рис. 1.7.3. Матрицы переходов имеют вид |
|
|
||||||
при нештрафе (AQ'<0) |
|
|
|
|
||||
в3 |
вх |
о |
о ••• о |
о |
|
|
||
0 В3ВХ |
о |
••• о |
о |
|
|
|||
Л 0 = |
|
|
|
|
вх |
|
(1.7.25) |
|
о |
о |
о |
о |
••• в 3 |
|
|
||
вх о |
о |
о |
••• о |
въ |
|
|
||
ГЛАВА I
34 |
|
|
|
|
|
|
при штрафе |
(AQ'^O) |
|
|
|||
В2 |
Bi |
О О ••• О О |
|
|||
О В2 Bi О |
О |
о |
|
|||
|
|
|
|
|
|
(1.7.26) |
0 |
0 |
0 |
0 |
В3 |
Bi |
|
в , |
о |
о |
о |
О |
£ 3 |
|
где |
|
|
|
|
|
|
О О О |
|
|
О 1 О |
О 0 1 |
||
1 0 |
0 |
|
В 2 = |
О О О |
В 3 = ,0 О О (1.7.27) |
|
1 О О |
|
|
;0 О О |
О О О |
||
Функционирование автомата в случайной среде, задан ной функцией (1.7.24), описывается цепью Маркова
|
В(s^ |
Bi |
О |
О- |
О |
О |
|
|
|
О |
B(s2) |
Bi |
0 - |
0 |
О |
A{S) |
= |
|
|
|
|
|
(1.7.28) |
|
|
О |
о |
О 0-B(sn-i) |
В{ |
||
|
|
Bi |
о |
О |
0 - |
0 |
B(sn) |
Здесь |
|
|
|
|
|
|
|
|
О |
Si |
l—Si |
|
|
|
|
|
0 |
0 |
О |
|
|
|
(1.7.29) |
|
О О О |
|
|
|
|
||
|
|
|
|
|
|
|
(1.7.30) |
где Ф |
— интеграл |
Лапласа. |
Обозначим через Р* = |
||||
=(Рзг-2, рзг-и Рг%) вектор предельных вероятностей, со
ответствующий i-й переменной функции (1.7.24). Для определения этих векторов по матрице (1.7.28) составим систему векторных уравнений:
|
|
|
ПОИСК БЕЗ САМООБУЧЕНИЯ |
|
||
|
|
95 |
|
|
• |
|
P, = P 1 B ( s , ) + P « B 1 ; |
|
|
|
|||
P2 |
= P1Bi |
+ |
P2B(s2); |
|
|
|
Рз = Р 2 5 , + Р 8 Я ( 5 8 ) ; |
|
|
|
|||
Pi |
= Pi _1 51 |
+ P i 5(s i ); |
|
|
|
|
P n = P„ _ 1 B 1 + P n 5 ( s „ ) . |
|
|
||||
Из i-го векторного уравнения этой системы |
следует |
|||||
|
1 —Si |
— 1+Sj |
|
О О О |
|
|
Pi |
О |
1 |
О |
= Рг-I ! |
1 О О |
(1.7.32) |
|
О |
0 |
1 |
I |
i 1 о о |
|
Отсюда для |
координат |
векторов Р; и Рг -1 получаем со |
||||
отношения |
|
|
|
|
|
|
P3i-2 = Рз(г—1)—1 + Рз(г-1) = Рзг-4 + |
Рзг'-3 = РЗг-5'. |
|
||||
Р з г - 1 = Р з г - 2 5 г ; |
|
|
(1.7.33) |
|||
P 3 i = P 3 i - 2 ( l - S j ) .
Из первого уравнения системы (1.7.31) имеем:
Р1 = Рзп-1 + Рз«;
p2 = s.p.; |
(1.7.34) |
Р з = (1 —Si)/?i- |
|
После нормировки величин pj (/ = 1, 2, . . . , 3 я ) находим
Р з г - 1 = - | ^ |
( i = l , . . . . п); |
(1.7.35) |
ГЛАВА I
96- |
|
|
|
|
Средний штраф рабочих шагов равен |
|
|
||
V f l - s t |
, |
( l - S i ) S i ] |
V |
{l-st)st |
|
|
|
|
(1.7.36) |
а среднее смещение по направлению |
градиента |
|
||
M[AQ]= J£ {pzi-P3i-i)ca= |
^ l - 2 s i |
|
||
—h2 |
»(•%)«• |
с - 7 - 3 7 » |
i |
= l |
|
Для случая отсутствия помех (a=0) имеем |
|
|
|
п |
|
Pcp.p=0; A f [ A Q ] = - - ^ - J ^ a * , |
(1.7.38) |
|
|
г=1 |
|
а при 0->-оо |
|
|
Р с Р . р - ^ | - ; M[AQ]->0. |
(1.7.39) |
|
§1.8. А Л Г О Р И Т М П А Р А Л Л Е Л Ь Н О Г О
ГР А Д И Е Н Т А
Рассмотрим параллельную модификацию метода. Этот алгоритм представляет собой поиск по вер шинам гиперкуба. По всем координатам делаются проб ные шаги и определяется полярное направление гради ента. Это полярное направление соответствует направле нию на вершину гиперкуба, которая наиболее близка к направлению градиента. Схема алгоритма параллель ного градиента показана на рис. 1.8.1. Алгоритм в тер минах теории автоматов представляется в виде двух
автоматов |
— а в т о м а т а |
п р о б н ы х |
ш а г о в |
Л< П ) , |
имеющего |
п + 1 внутренних |
состояний, и |
а в т о м а т а |
|
р а б о ч и х |
ш а г о в Л<Р>, имеющего т+l |
(т = 2п) |
внут |
|
ренних состояний.
Пронумеруем возможные рабочие шаги АХ<'> в сле дующем порядке:
ПОИСК БЕЗ САМООБУЧЕНИЯ
97
Рис. 1.8.1. Схема оптимизации методом параллельного градиента.
ДХО)= (1, . .. , I ) ; А Х ( 2 ) = ( 1 , . . . , 1, - 1 ) ; |
ДХ(з> = |
|
= ( 1 , . . . , 1, - 1 , 1 ) ; Д Х « > = ( 1 , . . . , 1, - 1 , - 1 ) ; . . . |
||
. . , ; д х < ™ / 2 - 1 > = ( 1 , - 1 , . . . , - 1 , 1); |
• • • ; |
ДХ'»/2= |
= ( 1 , - 1 , . . . , - 1 ) ; ДХ<«+*> = -ДХ<*> |
(1.8.1) |
|
( / = 1 , 2 , . . . . f ) .
У автомата пробных являются пробные шаги фиктивное состояние — томата рабочих шагов
шагов внутренними состояниями g^i (их число равно п) и одно автомат рабочих шагов. У ав внутренними состояниями явля-
7 — 2014
ГЛАВА I
98 |
|
ются рабочие шаги A X ( i ) |
(их число равно m = 2n ) и одно |
фиктивное состояние — автомат пробных шагов. |
|
Определим множество |
входов автоматов. Пусть вхо |
дом автомата пробных шагов Л ( П ) является знак при ращения функции качества. Входы автомата рабочих шагов Л ( Р ' определим следующим образом. Пусть в со стояниях от 1 до т автомат принимает на вход только
числа |
с = 0 и с = 1 , а в состоянии т + 1 |
(фиктивное состоя |
ние) |
— только векторы С = (си ..., |
сп), координаты с* |
которых могут иметь значения 0 или 1. При этом i-я ко ордината вектора С равна нулю, если автомат пробных
шагов Л ( П > в 1-м |
состоянии не получил |
штрафа |
(с = 0), и |
||||||
равна единице, если получил штраф |
( с = 1 ) . |
Следова |
|||||||
тельно, вектор С=(си...,сп) |
при |
представляет собой набор |
|||||||
величин |
с, |
полученных |
пробных |
шагах. |
Векторы |
||||
Cj-= (сх^\ |
,.., |
cn(i)), |
количество |
которых |
равно |
2™, про |
|||
нумеруем в том же порядке, как рабочие |
шаги АХ'»', т.е. |
||||||||
d = ( 0 , |
. . . , 0 ) ; С 2 = ( 0 , |
. . . , 0 , |
1); С 3 = ( 0 , . . . , 0 , |
1,0); . . . |
|||||
|
|
Cm /2-i=(0, |
1, 1 , . . . , |
1,0); |
C m / 2 = ( 0 , |
1 , . . . |
|||
|
|
\);...;Ст-,= |
(1, 1 , . . . , 1,0); |
C m = (1, . . . , 1). |
|||||
|
|
|
|
|
|
|
|
|
(1.8.2) |
Нетрудно заметить, что векторы Сг (i= 1 , . . . , 2") об разуются некоторым неоднородным а в т о м а т о м «па м я т и » со следующими, зависящими от номера шага N матрицами переходов:
I ' |
|
0 |
I 2^-1 |
0 |
|
/ |
|
2iv-i |
2n |
|
J.2n_2N-i |
—2N"1 |
|||
|
|
|
(1.8.3) |
0 |
1 |
0 |
|
О О О |
^ 2n —2w-' |
||
2JV-I 2w-i |
|
2n—2N |
|
где / — единичная |
матрица порядка 2^ 1 (Л/ = |
||
= 1 , 2 , . . . , л ) . |
|
|
|