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

282

ГЛАВА III

•

« i o = PoS2

+ YoSi;

G2o =

PoSi + YoS2;

a n

= P i S 2

+ Y i s

b

«2 i =

P i S i + Y i S 2 ;

(3 . 2 . 25)

£ l 2 = P2 S2 + Y 2 S i ; « 2 2 = P 2 S l + Y 2 S 2 -

Подставляя

в

формулы

(3 . 2 . 23)

выражения

( 3 . 2 . 2 4 ) ,

имеем:

_ 1_

a 2 0 + fl21 + ( ^ 2 2 - ^ 2 0 ) 6 2 2

.

'

4

a 2

0

+

a 2

i + ( a 2 2 - a 2 o ) 6 2 2 +

aio + a i i + ( ^ 1 2 - 0 1 0 ) 6 1 1

p2

1

•

a1 0

+ a n + ( a 1

2 —аю)бп

.

——

+ a 2 1 +

( a 2 2

•

622 + a 1 0

4

a 2 0

- a 2 0 )

+ a n + ( « 1 2 - 0 1 0 ) 611

(3 . 2 . 26)

Средний штраф автомата поиска равен

8

Р с р =

^ T p i S i = 4 ( p 1 S i + p 2

s 2 ) = s 2 +

^ ~ * а ,

(3 . 2 . 27)

г = 1

1

M[AQ] = 4(Pl-p2)

=

a2o + a 2 i + ( a 2 2 - a 2 o ) 6 2 2 - ( о ю + « п ) - ( « i 2 - « i o ) 6 n

o2 o + a 2 i + ( a 2 2 - a 2 o ) 6 2 2 + (al0

+ a n ) + ( a 1 2 - a , o ) 6 n

G - l

(3 . 2 . 28)

G + l

где

G

aio + a n + ( « 1 2 - 0 1 0 ) 6 1 1

a2o + a2i

+

(«22 — a 2 o ) 6 2 2

= [ l - 2 ( p s 2 + y S | ) ] [ l - ( p 2 s 2 + v 2 S i ) } ( l - 6 ) + p s 2 + y s i

[ l - 2 ( p S l

+ Y S 2 ) ] [ l - (p2Si + Y 2 s 2 ) ] ( l - 6 ) + p s 1 + Y S 2 '

(3 . 2 . 29 )

причем

P = Pi + p2 ;

Y = Y i + Y 2 ;

(3 . 2 . 30 )

0 ^ p i < 0 , 5 ; 0 s C p 2 < l ;

0 < Y i < 0 , 5 ; 0 ^ Y 2 < 1 .

( 3 ' 2 ' 3 1 )

283

Из формулы (3.2.28)

следует

l i m A f [ A Q ] = - l ,

(3.2.32)

G-eoo

а из (3.2.27) —

lim/?C p = S2-

(3.2.33)

G-+00

Из

формул (3.2.32) и (3.2.33) вид­

Рис. 3.2.1. Область

опре­

но,

что для построения оптималь­

деления функции f (хи х2).

ных

алгоритмов

поиска необхо­

димо найти значения

параметров

Рь 02 и у и Y2.П Р И

которых выражение G принимает

мак­

ражения G для случая, когда отсутствует

помеха,

т. е.

когда

о = 0 и st = 1, s2 = 0. Тогда

G =

[1 —2(Y i+Y2)](l—Y2> (1 - 6 ) +Y1+Y2 =

/(Yi.Ya)

[1—2(p, + p 2 ) ] ( l —p2) (1 — 6) +P1 + P2

/(Pi.Pa)

'

(3.2.34)

f (хи х2)

= 1 - 6 + (26 - 1)*!+ (36 - 2)x 2

+ 2 ( l - 6 ) x ! X 2 +

+ 2 ( 1 - 6 ) х 2 2

(3.2.35)

показана

на рис. 3.2.1. Стандартными

методами матема­

чения функции f(xuXi)

находятся на границе области ее

определения. Дифференцируя f(x\,x2),

находим:

f'xl(Xi,x2)

= 26-l +

2(l-6)x2;

(3.2.36)

/'*,(*!, х2)

= 36 - 2 + 2(1 - 6 ) ^ + 4(1

-Ь)х2.

1 —26

б

1-26

/ О < л о - , ч

Х =

; Х =

; Х 2 =

.

(3.2.37)

'

2(1 - 6 )

2(1 - 6 )

2 ( 1 - 6 )

V

ния функции f(xu

х2); при 6 = 0,5 она помещается на гра­

нице

этой

области

и имеет координаты Х\=0,5;

х2 = 0;

при

6 = 0

— также

на

границе, с координатами Х ]=0 ;

х 2 = 0,5.

При 0 , 5 < 6 ^ 1

стационарная

точка выходит из

области

определения функции

/ ( х ь х 2 ) .

Вторые производные функции

равны

*> = f"xx

(хих2)=0;

С = \"

( х ь х 2 )

= 4 ( 1 - 6 ) ;

Х\Л2

Л2Х2

(3.2.38)

5 =

(xi.**)-?'^

( х ь х 2 ) = 2 ( 1 - 6 ) .

Поэтому

В 2 —DC = 4(1 — 6 ) 2 ^ 0 .

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

точка,

определяемая

формулами

(3.2.37), не является

точкой

экстремума.

функцию / ( х ь х2)

Исследуем

на границах ее опреде­

ления.

f(xux2)

1. На границе

* i = 0; 0 ^ х 2

^ 1

функция

имеет

вид

/ (0, х2) = 1 -

6 + (36 - 2) х2

+ 2 (1 -

6) х2

2 ,

(3.2.39)

а экстремальной

является точка

2 - 36

2 - 6

Хг= *H=Wl

7(Г=5Г

( 3 ' 2 " 0 )

В этой

точке

функция

f(0, х2) принимает

минимальное

значение,

равное

f/о

2 ~ 3 6

) =

4 - 4 6 - 6 2

(3.2.41)

' V

'

4(1 - 6 )

/ ~

8(1 - 6 )

На концах отрезка

0 ^ х 2 ^ 1

функция

принимает

значе­

ния

/(0,0) = 1-6; /(0, 1) = 1.

(3.2.42)