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

нице, при

0 < 6 < 1

она

принимает

на

правом

конце от­

резка х2=1,

а для 6 = 0 — также

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

х2 = 0.

Точка

минимума

(3.2.40)

находится

внутри

отрезка

0 ^ * 2 = ^ 1 П Р И

0 < б < 2 / 3 .

При

2 / 3 ^ 6 ^ 1

точкой

мини­

мума является

левый

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

х2 = 0,

а

минималь­

ное значение

равно

/(0,0) = 1-6.

(3.2.43)

2. На границе х2

= 0; 0 ^ x ^ 0 , 5

функция

/ ( х ь

х 2 ) яв­

ляется

линейной:

f ( x b 0 )

= 1 - 6 +

( 2 8 - 1 ) х ь

(3.2.44)

Наибольшее

и

наименьшее значения она принимает на

концах

отрезка

0 ^ x ^ 0 , 5 :

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

(3.2.45)

3. На

границе

2х! + х 2 = 1 ;

0 ^ x ^ 0 , 5 ;

0 ^ х 2 ^ 1

функ­

ция имеет вид

f(±^L,

х2)=±

+ (б-±)ха+(\-6)х2*

. (3.2.46)

Экстремальной является точка с координатами

х 2 =

1-26

•;

х , =

3 - 26

,

, п п л „

4(1 - 6 )

8(1 - 6 )

(3.2.47)

2

V

;

в которой

функция принимает

минимальное

значение:

f(

3

~ 2

6

1-26

\

_

5 + 4 6 -

1262

(3.2.48)

' 8(Т^бГ ' "4(1-6) /

16(1-6)

На концах границы функция / |•-

, х2

j равна

f (0,5; 0) =0,5;

f(0, 1) =

1.

(3.2.49)

Формулы (3.2.47) дают

точку

минимума функции

(3.2.46)

для 0<6<0,5. При 0 , 5 ^ 6 < 1

точкой

минимума

функции

(3.2.46)

является

точка

Xi = 0 , 5 ;

х 2

= 0, а

минимальное

значение функции

равно

/(0,5; 0 ) = 0,5.

(3.2.50)

(3.2.48)

и (3.2.49),

видим,

что

максимальное

значение,

равное

единице,

функция

f(xux2)

для случая

0 < 6 < 1

принимает

в

точке

хх = 0;

х 2 = 1 . Следовательно, опти­

мальные значения

вероятностей уо, Уь Y2 равны

Yo = Yi = 0;

Y 2

= i ,

(3.2.51)

является

оптимальным

действием.

Далее

следует,

что

для 2 / 3 ^ 6 < 1

минимальное

зна­

чение,

равное 1 — 6, функция f(xux2)

принимает в

точке

Х\—х2

= 0, т. е. оптимальными

значениями параметров

Ро, Рь Рг являются

Ро=1;

Pi = p2 = 0.

(3.2.52)

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

для

2 / 3 ^ 6 < 1

оптимальным является

алгоритм поиска

со следующими элементами переходных

матриц

(3.2.1):

Ро=1;

Pi = p2 = 0; Yo = Yi = 0; Y 2

= l .

(3.2.53)

формуле (3.2.28), для этого алгоритма

равно

M , [ A Q H - - A - ,

(3.2.54)

l — о

а средний штраф, подсчитанный по

формуле (3.2.27),

287

нение

выражений

(3.2.41) и

(3.2.48). Из

неравен­

ства

^ 4 - 4 6 ^

5 + 4 6 - 1262

к

'

следует

неравенство

1062 -126 + 3 ^ 0 .

(3.2.57)

Решая это неравенство, получаем

точки

e i = 6

± £ ; e a = 6

z £ ,

(3.2.58)

10

10

2 - 6

;

п

п

2 - 3 6

Ро= , „

с ч

Pi = 0;

'

P V

4(1 - 6 ) '

4(1 - 6 )

'

^

v z

1 ( 1 - 6 ) ' 1

4(1 - 6 ) '

M2[AQ] =

;

.

(3.2.61)

L

J

12—126 —б2

К

'

4_45_g2

рс р (2) =

,

(3.2.62)

И р

12—126 —б2

V

;

а для второго алгоритма —•

M f r q —

" - * • » + « №

(3.2.63)

1

J

21 - 126 - 126 2

V

;

288

5+46-126*

^ P

21 — 126— 1262

'

Изложенный

выше

анализ

показывает, что для раз­

личных

интервалов

изменения

параметра

объекта 6

имеются

различные оптимальные

алгоритмы.

1) Для интервала

2 / 3 ^ 6 < 1 оптимальным

является

алгоритм со значениями переходных вероятностей

Ро=1;

Pi = p2 = 0; Yo = Yi = 0;

Y2=l-

(3-2.65)

Среднее значение функции качества для этого

алгоритма

равно

M , [ A Q } = - 1 1 - ,

(3.2.66)

а средний штраф —

Р с р ( ' > = - ^ - .

(3.2.67)

2) Для интервала

(6 —У6)/10<6<2/3

имеем следую­

щий оптимальный алгоритм:

о

2 - 6

_

2 - 36 .

Yo = Yi = °; Y2=l-

(3.2.68)

Среднее приращение функции качества

и средний штраф

равны

4 _ 46 + б2

M i ^ = ~

1 2 - 1 2 . - е . '

^

4 _ 4 § _ g 2

=

12-126-6*

•

( 3 - 2 - 7 ° )

M J a Q l —

" - 2 0

6 +

1 2 6 1 ;

(3.2.72)

3 1

V J

2 1 - 1 2

6 -

1262

Л

;

...

5 +

4 6 - 1 2 6 2

Р ^

=

- 2 1 - 1 2 6 - 1 2 6 2 •

( 3 - 2

J 3 )

приращения

функции

качества

на

одном

шаге поиска

для

алгоритмов

случайного спуска

M C N [ A Q ]

и для алго­

ритмов случайного поиска с возвратом M B [ A Q ] . Для слу­

чая,

когда отсутствует

помеха,

по формулам (3.2.34) и

(3.2.28) имеем:

f~2l8

A W A Q ] = -

;

.

(3.2.74)

MB[AQ ] = ~

у

•

(3.2.75)

MCAQ]