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

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

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

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

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

Добавлен: 19.06.2024

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

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

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

ГЛАВА III

316

Рис. 3.3.3. Состояния и переходы автомата для от=4 (и=2) и нуме­ рация выходов AXj автомата.

где

 

Vi= (l-sW)r12+sWr22=ri2-s(V(rl2-r22),

(3.3.48)

b = rxr2.

(3.3.49)

Пронумеруем выходы ДХ^> автомата так, как это пока­ зано на рис. 3.3.3,6. Тогда приращения по направ­ лениям ДХ( з' равны

AQ(i) = a i + a2 ;

AQ(2> = a, - a 2

;

 

 

(3.0.5U)

AQ(3) = _ ( a i + a 2 ) ;

A Q ( 4 ) = _ _ ( a i _ a 2 ) ;

где a, ( i = l , 2 ) — направляющие косинусы вектора градиента функции Q(X).

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

317 :

Вероятности Sj штрафов действий ДХ( ^ автомата опре­ деляются по формуле

Sj = Bep ( A Q > 0 / A X = AXO>) = ± [ i + o ( _ ^ L ) ] ,

(3.3.51)

где Ф(г) — интеграл вероятности. Учитывая формулы (3.3.50), находим:

„ 4 [ 1 + Ф ( ^ ) ] ; 5 2 4 [ , + ф ( ^ ) ] ;

(3.3.52)

1

* з = у

Определим вероятности штрафов s(') ( i = l , . . . , 4 ) по отношению к состояниям W( ') автомата. Для этого сна­ чала определим вероятности выходов цц\

<7ii = Bep (Axx = \/wx = wxW) •Bep(Ax 2 =l / ^2 = ^ 2 ( i ) ) =

qu=(l-FxW)F2^,

 

 

 

где Fi(i> заданы формулой (3.3.4)

при Wi = wi^.

Предположим,

что

состояния

W<») автомата располо­

жены симметрично относительно начала координат:

W('l = - W f f l ;

W<4> = -W<2 >.

(3.3.54)

Тогда имеют место следующие равенства:

f 1 n . - f , « ' - f , » - W « - l ' . ;

 

Fxw = F2w = FxM =

F2w=:F2.

 

При этом можно показать, что

 

F2=

 

 

(3.3.56)

ГЛАВА III

3 1 8 -

По формуле (3.3.7), учитывая выражения (3.3.55) и (3.3.56), находим:

s<2)= s 4 + ( s 2 - s 4 ) F i ;

 

(3.3.57)

s<3) = s i -

(s I - s 3 )F 1 ;

 

 

 

S ( 4 ) = s 2 _

(s 2 - s 4 )Fi ,

 

 

где

 

 

 

1,

если

Ш 1 О > 0 ;

 

 

еСЛИ

| Ш 1 < 1 ' | ^ о ;

(3.3.58)

o,

если

ff< — Ш ^ ' ) ;

 

Sj (/=1, ... ,4 )

 

определяются формулами (3.3.52).

Из формул

(3.3.57) видно, что выполняются

равенства

S ( D + S ( 3 ) = 1 ;

 

S ( 2 ) + S ( 4 ) =

l_

(3.3.59)

Учитывая эти равенства,

находим:

 

1 ) 3 = 1 - 0 ] ;

 

vi=l-v2.

 

(3.3.60)

Следовательно,

матрица

(3.3.47) имеет вид

 

 

Ь 1 - и,

b

 

А =

v2

Ъ

\-v2

(3.3.61)

b

\-vx

b

 

 

Ь

v2

b

\ — v2

 

Предельные вероятности этой цепи Маркова находятся как решение следующей системы уравнений:

P\ = vx(px+pz) + Ь(р2

+ р4);

P2 = b(pl+p2)

+v2(p2

+ p4);

 

 

(3.3.62)

Рз = (l-vi)

(Pi+Рз)

+b(p2 + p4);

Pi = b(p{ + p3) + (\-v2) (p2 + P i ) .

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

 

319

 

 

 

 

 

Решая эту систему

уравнений

и нормируя

вероятности

pi, находим:

 

 

 

 

 

p 1 = l [ l + ( r 1 - r 2 ) ( l - 2 S ( ' ) ) ] ;

 

 

 

P2=\[l

+

{rl-r2){\-2sW)];

 

 

 

 

 

 

 

 

 

(3.3.63)

Р З = 1 [ 1 + ( Г , - Г 2 ) ( 1 - 2 5 < 3 ) ) ] ;

 

 

 

p 4 = l [ l + ( r 1 - / - 2 ) ( l - 2 s H ) ) ] .

 

 

 

Можно

показать,

что

среднее

приращение функции

Q(X) при фиксированном

W ( i )

( i = l , . . . , 4 )

равно

M[AQ/WW] = (F^

+ F2w-l)AQW+

(F1 w - F2w) AQ<2)).

 

 

 

 

 

 

(3.3.64)

По этой формуле с учетом равенств (3.3.55) находим:

Af[AQ/W<D]=(2i7 i-l)AQ(1 );

М[А Q/W<2>1 = (2Fi -

1) AQ <2>;

 

(3.3.65)

 

 

 

 

Af[AQ/W<3>]=

( l - 2 / 7

1 ) A Q < 1 > ;

 

 

 

M[AQ/W<4>] = (1-2F,)AQ<2 >.

 

 

 

С учетом этих выражений и формул

(3.3.50) приращение

функции Q(X), осредненное по всем

состояниям

W ( i ) ,

равно

 

 

 

 

 

M[AQ] = [(Pl-p3)

(а{

+ а2) + (Р2~Р4)

( a i - a 2 ) ] ( 2 F 1 -

1) =

= - l [ ( s i - s 3 ) (ai + a2 ) + (s2-Si)

(oci - a 2 )]X

X ( r 1 - r 2 ) ( 2 f 1 - l ) .

 

(3.3.66)

Очевидно, что M[AQ] достигнет своего минимального зна­ чения тогда, когда выражение

(r1-r2)(2Fl-l)

(3.3.67)

ГЛАВА III

320

примет свое максимальное значение. Это будет иметь место при

г , =

1; r2 = 0; F, =

l .

(3.3.68)

Fi = l

тогда, когда

в формуле (3.3.58) Wi^^q.

По­

скольку oj] ( 1 ) = ffi>2(1\ алгоритм поиска будет оптимальным при следующих значениях его параметров:

г, = 1; r2 = 0; wxW = w2W^q.

(3.3.69)

Этот результат согласуется с результатом, полученным для одномерного случая ( я = 1 ) .

§3.4. С М Е Ш А Н Н Ы Е А Л Г О Р И Т М Ы

СЛ У Ч А Й Н О Г О П О И С К А

Будем называть смешанным алгоритмом (по аналогии со смешанной стратегией в теории игр) такой алгоритм, в котором некоторые переходы от одного опе­ ратора к другому осуществляются вероятностным обра­ зом. Простейшим смешанным алгоритмом поиска явля­ ется алгоритм, стратегия которого образуется вероят­ ностным взвешиванием чистых стратегий:

к

 

 

s= 2 PiSi = [P S],

.

(3.4.1)

где

 

P=(pu...,pk)

(3.4.2)

— вектор вероятностей бесов выбранных стратегий;

h

 

г = 1

 

S = ( s „ ...,sh)

(3.4.3)

— вектор имеющихся чистых стратегий поиска (напри­ мер, Si — стратегия метода градиента, s2 — стратегия

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