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

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

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

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

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

Добавлен: 19.06.2024

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

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

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

ГЛАВА III

326

Система

уравнений

для предельных

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

р\,

р2

и р 3 имеет вид

 

 

 

 

 

[p{l-pi)

+

{\-p2)]pi+

{l-q)P2

+ pa = Pi;

 

 

+

 

 

 

(

3 4 2

5 )

(l-p)P2pl=P3\

Р\ + Р2+РЗ=

1-

Заметим, что первые три уравнения линейно зависимы, что заставляет расширить систему четвертым уравне­ нием. Решая эту систему, получаем:

1 - о

Pi-

[1 + ( 1 - р ) р 2 ] ( 1 - < 7 ) + р р

 

 

 

^ Щ [ = р ) ^ - Я ) + Р Р Г '

( З А 2 6 )

 

(l-p)(\-q)p2

 

 

L l + ( l - p ) p 2 ] ( l - o ) + p p 1

 

Следовательно, средний штраф равен

(3.4.27)

[1 + ( 1 - р ) р 2 ] ( 1 - о ) + р р 1 '

Проанализируем полученные выражения с точки зре­ ния сопоставления алгоритмов поиска. Начнем с ана­ лиза известных алгоритмов, которые получаются при нулевых или единичных переходных вероятностях р\ и р2 .

1-

/?i = /?2 = 0

(алгоритм

случайного

блуждания).

В этом случае средний штраф равен

 

с, = 1 - р .

 

 

(3.4.28)

2.

Pi = 0; р 2 = 1

(алгоритм

нелинейного

поиска «с воз­

вратом») ; тогда

 

 

 

С 2 = ^ ~ ~ .

 

 

(3.4.29)

 

2-р

 

 

 

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

327

3. pi = l ; Рг = 0 (алгоритм поиска с линейной такти­ кой) ; тогда

£ ' - т ^ 7 '

 

(3•4•30,

4- Pi = Р2 = 1

(линейная тактика с возвратом при не­

удачном случайном

шаге); тогда

с 4 =

—

.

(3.4.31)

 

(2-p)(l-q)+p

 

параметров объекта (р, q)

Определим

на плоскости

зону преимущества

каждого

алгоритма.

Несложный

анализ показывает, что

c^Ci

 

 

 

(3.4.32)

(i = 2, 3,4),

т. е. случайное блуждание никогда не лучше других рас­ сматриваемых алгоритмов. Это естественно, так как при Pi=P2 = 0 нет целенаправленности, имеет место случай­ ный перебор.

Далее,

с 4 < с з ,

(3.4.33)

т. е. линейный алгоритм с возвратом всегда лучше, чем без возврата, что также естественно. Сопоставляя 2-й и 3-й из указанных выше алгоритмов, получаем

с2<с3,

если ? < р 2 - р + 1,

(3.4.34)

и наоборот (см. рис. 3.4.4, а, где зона преимущества не­ линейного алгоритма поиска заштрихована).

Сопоставление 2-го и 4-го алгоритмов приводит к сле­ дующему результату:

c2<Ci, если q< — — ,

(3.4.35)

2-р

 

и наоборот (см. рис. 3.4.4,6, где зона целесообразного применения 2-го алгоритма заштрихована).

Эти результаты определяют оптимальные в данной ситуации алгоритмы и дают возможность построить

ГЛАВА III

Рис.

3.4.4. Плоскость параметров

объекта с зонами

целесообраз­

ного

применения

алгоритмов.

 

 

алгоритм

случайного

поиска

с адаптивной

структурой

при р 2 = 1:

если

qN{2-pN)

< 1 ;

 

Pi ( J V - I )

Г 0,

(3.4.36)

:

если

4JV(2 — pjv) > 1,

 

 

1 1,

 

где pjv И <7JV — текущие оценки параметров р и о объекта на Л/-м шаге поиска, которые можно производить по сле­ дующим формулам:

после случайного шага

(sj):

 

 

 

N

[pjv_,(A/-l)

+

l],

если

A Q A - - i < 0 ;

PN

=

 

 

 

 

 

(3.4.37)

 

 

 

 

 

 

если A Q J V - Ь ^ О ;

<?JV =

I?JV-I

;

 

 

 

 

после спускового шага

(s2 ):

 

pN

=

pN-U

 

 

 

 

 

 

 

1

[ < ? J V - I ( J V - 1 )

+

1],

если

A Q J V - I < 0 ;

 

 

—

OjV

=

 

 

 

 

 

(3.4.38)

N q j v - i ( i V - l ) ,

если A Q N - I > 0 ;

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

329

после возврата (S3):

P n = P n ~ 1 '

(3.4.39)

Предложенные формулы гарантируют асимптотичес­ кую сходимость к истинным значениям параметров р и q объекта, т. е.

lim pN = p;

N-+00

(3.4.40)

lim qN = q,

N-f-oo

если p и <7 = const. Однако для реальных объектов это предположение слишком грубо, и следует считать, что значения р и q изменяются в зависимости от состояния объекта. В соответствии с этим формулы (3.4.37) — (3.4.39) следует записать, например, в следующем виде:

после S\.

(

p j v - i ( l - f a i ) - а ь

если

A Q < 0 ;

/о и/in

I

p j v - i ( l - a 2 ) ,

если

A Q > 0 ;

 

<7ЛГ = <7JV-I;

после s2:

PN = PN-\ ;

 

4JV_I(1 +

P I ) - P

I ,

если

A Q < 0 ;

 

(3.4.42)

 

 

(1 — p2 ),

если AQjsO;

 

 

 

 

 

после s3 используем (3.4.39).

 

 

должны

Параметры

a%, Pi (t = 1, 2) в этих формулах

быть назначены исходя из конкретных

соображений.

Проведем

а н а л и з

с м е ш а н н ы х

а л г о р и т м о в .

При pi,

Р2ФО; 1 получаем

смешанные алгоритмы слу­

чайного

поиска.

Решаем

для

этого

случая

задачу

(3.4.15), а именно

 

 

 

 

 

 

< ( Р ь Р 2 ) =

U-DV-P

 

+ PPi)

_

min .

 

С ( Р и Р 2

)

[l-(l-pW{\-q)+PPi

т

Ш ]

 

 

 

 

 

 

 

 

(3.4.43)

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