ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 194
Скачиваний: 1
ГЛАВА I
62
По этой матрице можно убедиться, что для любого значения параметра о цепь Маркова является эргоди-
ческой. Поэтому вектор предельных |
вероятностей Р = |
|
= {р\,...,рт) |
пребывания автомата |
в состояниях i |
можно найти, решая систему уравнений |
||
P=;4'(S)P |
|
(1.4.5) |
где A'(S) — транспонированная матрица (1.4.3). Не трудно заметить, что система (1.4.5) сводится к следую щей системе:
flPl+g2p2+ |
|
|
+gm/2 |
Pm/2 = |
0; |
|
|
glPl+f2P2 |
+ |
g3p3+ |
•- |
+gm/2 |
P m / 2 = |
0; |
|
g\P\+g2P2+ |
|
-• |
+ gm/2-l |
pm/2-l+fm/2 |
Pm/2 = 0\ |
||
pm/2+i= |
, |
, |
Pi |
|
1 1 = 1 , . . . , — I , |
||
где |
Km'2+i |
|
|
* |
|
' |
|
|
|
|
|
|
|
|
|
|
|
|
ki |
|
|
|
|
fi = Cli + |
bm/2+i — |
|
1; |
|
|
||
|
|
|
л-m/2+i |
|
|
|
|
gi = ai + am/2+i-T-1—;
Кщ/2+i
ki = ai — bi— 1 = — ( 1 + S j ) .
(1.4.6)
(1-4.7)
Из системы |
(1.4.6) находим: |
f l - g |
l |
0 |
' |
|
2f b |
(1.4.8) |
|
|
|
|
|
Pm'2+i = —r |
|
7 |
Pi |
|
Krn/2+i |
|
|
Ji~gi |
|
0 |
< |
|
:;) |
|
После нормировки p i и подстановки вместо fi и gi выра жений (1.4.4) и (1.4.7) имеем:
|
ПОИСК БЕЗ САМООБУЧЕНИЯ |
63 |
— |
l+Sm /2-H
Pi— — - - о
1 SjSm/2-И
(i=l,...,-%);
рг+т/2z |
l + S i |
n |
|
|
SiSm/2+i |
|
|||
|
1 |
|
||
|
|
( |
< - |
• ? ) • |
где |
m/2 |
|
|
|
|
|
|
|
|
5 = |
/ у 2 + 5, + Sj + C T /2 ) " ' . |
|||
|
' |
1 — SjSj+ T O /2 |
|
|
Средний штраф равен m/2
S i + 25г5, + т о / 2 + S i + m / 2 S = = l _ m S ,
(1.4.9)
(1.4.10)
{ { А П )
j _ J |
1 5i<Si+m/2 |
|
|
Нетрудно |
показать, что имеет |
место неравенство |
|
- | < Р с Р ^ у . |
(1.4.12) |
||
При ЭТОМ При СГ->0 /?ср-*-7з И При 0 - > - О О /?Cp->V2- |
|||
Отсюда |
следует, что вероятностный автомат, соот |
||
ветствующий |
рассмотренному |
алгоритму случайного |
|
поиска, в процессе оптимизации при наличии помех с ог раниченной дисперсией обладает целесообразным поведе
нием в |
смысле |
определения, данного М. Л . Цетли- |
||
ным [28]. |
|
|
|
|
Далее |
пронумеруем |
направления |
смещения ДХ<«> в |
|
пространстве X (состояния автомата) |
в следующем по |
|||
рядке: |
|
|
|
|
Д Х < " = ( + 1 , . . . , |
+ 1 ) , |
ДХ<2> = ( + 1 . . . ., + 1 , - 1 ) ; ДХ<з) = |
||
= |
( + 1 , . . . , + 1 , - 1 , - 1 ) ; ДХ№ = |
= |
( + 1 , . . . , + 1 , - 1 , - 1 ) ; . . . ; Д Х ( ™ / 2 - п = |
ГЛАВА I
|
64 |
|
|
|
= |
( + i , - i |
- |
l , + 1 ) ; лх ™/2= |
|
= |
( + 1 , - 1 , . . . , |
- 1 ) ; AXC»/2+') = - A X W |
(1-4.13) |
|
|
|
|
. |
|
2
Тогда средний вектор смещения в пространстве {X} равен
М[АХ}=[(
+
1—S\S i+m/2 |
|
1—S2S2+W./2 |
|
||||||
Sm — Sm/2 |
|
\ „ / S 1 + m / 2 — S i |
|
||||||
1 — S m S m / 2 ' |
M — S i S j + m / 2 |
|
|||||||
+ 1 —Sm /4ST n /4+m/r 2 |
1 — S m / 4 - H S m / 4 - H - ) - m / 2 |
||||||||
Sm — S m / 2 \ |
c |
|
/ S i + m / 2 — Si |
|
|||||
1 — |
S m / 2 |
S m ' |
h |
|
M(Л |
|
|
||
|
|
|
|
—SiSi4_m /2 |
|
||||
S2 +m/2— s2 |
|
+ |
S34-m/2 — S3 |
S4+m /2 — S4 |
h |
||||
1—S2S2+M /2 |
~ |
|
|
~ |
|||||
|
|
1—S3S3+M /2 |
1— S4S44W2 |
||||||
|
sm |
|
Sm/2 |
\ g |
I |
|
|
||
l - s m s m / 2 |
|
J' |
|
(1.4.14) |
|||||
где S определяется формулой (1.4.10). Среднее смеще ние в направлении градиента grad Q(X) = (ось а 2 , . . . , ап) равно
Af[AQ] = sf |
"1+m/2~S[ |
( a i |
+ a 2 + - +ап) |
+ |
|
||
|
|
'SlSl+m/2 |
|
|
|
|
|
L 1 — S i S1 |
4-m /2 |
|
|
|
|
||
S2+m/2~S2 |
(at + a 2 + ••• + a n - i —an ) |
+ |
|||||
|
|
|
|||||
1 — S2S2 +m/2 |
|
|
|
|
|||
S3+m/2 — S3 ( a i + |
••• + a n - 2 — a n - i + a n ) + |
||||||
1 ~ |
$ 3 5 3 + т / 2 |
|
|
|
|
||
|
|
|
( a i + |
••• +0C1-2 — a.n-1 — |
|
||
1 — S4S4+m /2 |
|
|
|
|
|||
\ |
1 |
1 |
Sm-l |
— Sm/2—I 1 |
|
, \ , |
|
-a„) + |
••• + - |
|
(ai— |
a n - i + a n ) •+ |
|||
Sm |
Sm/2 |
1 |
Sm—lsm/2—1 |
|
|
||
•(ai — a2— ••• —an) ] • |
(1.4.15) |
||||||
1 |
|
SmSm/2 |
|
|
|
|
|
ПОИСК БЕЗ САМООБУЧЕНИЯ
65-
Теперь предположим, что направление вектора гради ента функции Q (X) удовлетворяет условиям
ai><%2 > ••• > a n > 0 ; |
(1.4.16) |
|
a i > a 2 + ••• +an. |
||
|
||
Тогда имеют место следующие неравенства: |
|
|
A Q ( " > 0 ; . . . ; AQWV>0; AQ("V2+i)<0; . . . ; AQ(™><0, |
||
|
(1.4.17) |
|
где AQb') — приращения функции Q(X) по направлению A X ( i ) . Поэтому при предельном переходе о-э-0 имеем
lim S j =
сг-*0
1 при
. m
О при * = - y
2. .
—при < = ! , . .
m
(1.4.18)
m ;
m
lim Pi |
|
4 |
|
. m |
, . |
|
|
(1.4.19) |
СГ-+0 |
|
|
|
m; |
|
|||
- — |
при 1 = - т г + 1 , . . . . |
|
||||||
|
3m |
|
2 |
|
|
|
|
|
l i m p c p = 4; |
|
H m M [ A X ] = ( |
- 1 |
0 , . . . , o ) ; |
(1.4.20) |
|||
cr->-0 |
<J |
|
a-*0 |
|
4 |
|
|
|
lim A I [ A Q ] = - — |
a b |
|
|
|
(1.4.21) |
|||
a->-0 |
|
|
<J |
|
|
|
|
|
Нетрудно |
убедиться, |
что |
при |
предельном |
переходе |
|||
а->-оо получаем |
|
|
|
|
|
|
||
lim s»= - jr ; |
H m p i = — |
( i = l |
m); |
|
||||
(У->-оо |
^ |
a->-oo |
W |
|
|
|
|
|
H m p c p = 4 - ; |
HmAf[AX]=(0 |
|
0); |
(1.4.22) |
||||
0->-oo |
^- |
|
CT->oo |
|
|
|
|
|
lim M[AQ]=0.
a->co
5 — 2014
ГЛАВА I
66
Далее рассмотрим д в у м е р н ы й с л у ч а й (я = 2; т =
= 4). |
|
|
|
|
|
|
Принимаем следующую |
нумерацию векторов ДХ<*>: |
|||||
ДХ<1>=(1,1); |
ДХ < 2 >=( - 1, 1); |
|||||
Д Х ( 3 ) = ( - 1 , - 1 ) ; |
ДХ(*>= (1, — 1). |
|||||
Пусть функция Q(X) является линейной, т. е. |
||||||
grad Q(X) = (а,, а2) =const; oci2 +oc22 = 1. |
||||||
Тогда из формулы |
(1.2.17) |
следует: |
||||
|
|
|
|
|
2а |
|
«3 |
|
a i + а г |
|
|
||
|
|
|
|
|
||
|
|
|
|
|
(1.4.23) |
|
где Ф(г)=—L |
Г е ~ г 2 Л |
|
||||
Матрица (1.4.3) |
равна |
|
|
|||
|
а\ |
cii |
bx |
a,i |
|
|
A(S) = |
а2 |
а2 |
а2 |
Ь2 |
(1.4.24) |
|
Ъг |
аг |
а3 |
а3 |
|||
|
|
|||||
где |
Й4 |
Ьц |
Й4 |
Й4 |
|
|
|
|
|
|
|
||
1
fli=—(1-sj); bi=—(l+3s<). (1.4.25) 1
Имеем следующий вектор предельных вероятностей:
( 1 + S 3 ) ( 1 - S 2 S 4 ) |
P2-- |
( 1 + S 4 ) ( 1 — SiS 3 ) |
||
3 ( 2 - S 1 S 3 - S 2 S 4 ) |
3(2 — S ! S 3 |
—s2s4) |
||
|
||||