Файл: Растригин Л.А. Автоматная теория случайного поиска.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 19.06.2024

Просмотров: 172

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

ОПТИМАЛЬНЫЕ АЛГОРИТМЫ

307

что на ее значения накладывается помеха в виде нор­ мально распределенной случайной величины е(о) с ма­ тематическим ожиданием, равным нулю, и диспер-

Q ' ( X ) = Q ( X ) + e ( a ) .

.(3.3.8)

Тогда цепь Маркова (3.3.6) является однородной и за­ дача сводится к нахождению ее предельных вероятнос­ тей. С использованием найденных предельных вероят­ ностей составляется выражение для среднего приращения 7W[AQ] функции качества по направлению ее анти­

градиента.

Это

выражение

содержит

вероятности

ги

г2

и параметр

q.

 

 

 

 

 

 

 

 

 

 

 

Построение оптимального

алгоритма

поиска

сводится

к нахождению

таких

значений

г ь

r2,

q,

при

которых

M[AQ] принимает минимальное значение. Построены оп­

тимальные

алгоритмы

для

одномерного

( я = 1 )

и дву­

мерного (п = 2)

случаев.

 

 

 

 

 

 

 

 

 

1. Одномерный

случай

( л = 1 ) . В этом случае

матрицы

переходных

вероятностей

AQ я

А {

равны

матрицам

Ro

(3.3.1) и Ri

(3.3.2), т. е.

 

 

 

 

 

 

 

 

 

 

Л 0 = Я0 ;

Al =

Ru

 

 

 

 

 

 

 

(3.3.9)

 

Для составления матрицы S*, входящей в формулу (3.3.6), необходимо определить вероятности Sj штрафов действий ДХ№ автомата и вероятности qa выходов ДХЬ'> автомата при его нахождении в состоянии w^. Опреде­ лим эти вероятности.

Пусть автомат имеет 2k состояний, которые располо­ жены на прямой и пронумерованы в следующем по­

рядке:

 

 

 

Wi = d; w2=(k-2)8+~;

о>*_1

= 6 + — ;

^h=—\

б

/ „ б

\

 

^fe+i = - y ;

Wk+2=-\8+—

) ;

w 2 h - i =

= -(k-2)6--j:

®2k=-d,

 

(3.3.10)

20*

ГЛАВА III

308

где

2ft - 1

Для одномерного случая автомат имеет два выхода, которые представляют собой следующие числа:

ДХ ( 1 )=Дх=1; ДХ(2) = _ Д х = - 1 ,

(3.3.11)

вероятности появления которых согласно формуле (3.3.4) равны

qil

= Bep(Ax=l/w=wW)=Fi=F(w<i\

 

q);

(3.3.12)

qi2

= Bep(Ax

= — \/w = wW) = l~Fi

=

 

 

 

 

0,

если

w^>q;

 

 

 

y ( l

—),

если

|ш№|===я;

(3.3.13)

 

 

 

1,

если

wM< — q

 

 

 

 

 

( i = l , . . . , 2ft).

 

Ввиду линейности функция Q(X) обладает свойством

AQ<'> = a ;

AQ<2> = - a ,

 

 

(3.3.14)

где AQ(i > — приращение функции Q(X) по направлению

AX{i)

( t = l , 2).

Тогда вероятности штрафов Sj действия

АХ^

автоматов

равны

 

s, = B e p ( A Q > 0 / A x > 0 ) = - i [ l + O ( • — ) ] ;

 

 

 

 

(3.3.15)

s2 = B e p ( A Q > 0 / A x < 0 ) = l [ l - ( l > ( - ^ - ) ] .

 

По формуле (3.3.7) находим

 

sw

= FiSl + (1 -

-Ft) s2 = s2+Fi (s, - 5 2 )

(3.3.16)

 

 

( i = l , . . . , 2 f t ) .

 

Следовательно, имеем диагональную матрицу вероят­ ностей штрафов (3.3.17).

s2 + Fi{si-s2)

0

0 .

0

0 . . .

0

0

s2+F2{sl-s2)

0 .

0

0 . . .

0

s*=

 

0...sa

+ Fi(sl-s2)

0 . . .

(3.3.17)

 

CO

 

 

 

 

 

 

 

о

 

 

0 . .

 

0 . . . s2 +

F2k(si-s2)

 

l - o ,

 

0

0

0 . .

0

0

0

0

0 . .

0

0

0

 

\ — v2

0

 

0

0 . .

0

0

0 0

0 . .

0

0

0

 

0

l - v 3

0

v3

0 . .

0

0

0

0

0 . .

0

0

0

A =

0

0

0

0 0 . . .

l - v k

0

Vh

0

0 . .

0

0

0

0

 

0

0

0

0

0 . .

0

1 - v h

0

Vh

0 . .

0

0

 

0

0

0

0 0 . .

0

0

0

0

0 . . .

l - l >2

0

v2

 

0

0

0

0 0 . .

0

0

0

0

0 . .

0

1 - 0 ,

V\

(3.3.19)

ГЛАВА III

310

Поскольку состояния автомата, определяемые форму­ лами (3.3.10), симметричны относительно нулевой точки, то, используя формулы (3.3.4) и (3.3.13), мы можем за­ писать

Fi=l-F2h-i+l

(3.3.18)

(i=l,...,2k).

 

Учитывая свойство (3.3.18) и используя

матрицы

(3.3.1), (3.3.2) и (3.3.17), по формуле (3.3.6)

находим

матрицу (3.3.19) переходных вероятностей цепи Маркова,

описывающей

переходы

автомата

из одного

состояния

в другое, где

 

 

 

 

 

 

 

_ Гs « > r i + ( l - s < * > ) r 2

( i = l , 2 , . . . , £ ) ;

 

 

° < - 1 5 ( « г а + ( 1 - 5 ( « ) г ,

(i =

k+l,...,2k);

 

s(»' определяются формулой (3.3.16).

 

k=\.

Сначала

рассмотрим простейший

случай,

когда

В этом

случае, как

нетрудно заметить, цепь Маркова

(3.3.6) имеет

матрицу

переходных

вероятностей

 

А-

 

1 - O i

V\

 

 

 

(3.3.21)

 

 

 

 

 

 

 

где,

в соответствии с формулой (3.3.20),

 

 

U l =

s ( i ) r 1 +

( l - s ( ' ) ) r 2 = r 2

+ s ( i ) ( / - ! - r 2

) .

(3.3.22)

Предельные

вероятности

этой цепи Маркова

равны

 

Pi = l - u i ;

p2 = wi

 

 

 

(3.3.23)

Подставляя

вместо vx

выражение (3.3.22), получаем:

„_„_,...<„_„>;

 

 

 

<

з з 2 4 )

P2 = r2

+

 

sW(rl-r2).

 

 

 

 

 

Определим среднее смещение на одном шаге по пря­ мой х. При нахождении автомата в состоянии оно вычисляется по формуле

Смотрите также файлы