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

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

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

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

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

Добавлен: 19.06.2024

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

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

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

ПОИСК БЕЗ САМООБУЧЕНИЯ

 

133

 

 

 

 

 

 

Рассмотрим

случай

о г р а н и ч е н и й ,

с о з д а в а е ­

м ы х о б л а с т ь ю т и п а I I . '

 

 

Окрестность

минимума

состоит

теперь из трех точек:

(1, 1), ( — 1, 1),

( — 1, —1)- Однородными

множествами

будут:

 

 

 

 

 

 

 

1)

множества At

(i =

2,3,т);

 

Ai={0:

(£, 1),

( - 1 , 0 1 ;

 

 

2)

множества

В0:

 

 

 

Во={0:

( - 1 , 0 ,

( - » , 1)(» = 2,3

оо)};

 

3)

множества

Bi

(i — 1, 2, 3,...,

т);

 

5 i = { 0 :

(i,k),

(-k, - i ) ( * = 2 , 3 , . . . , o o ) } ;

 

4)

множества

С4

( i = 1, 2, 3,...,

т);

 

Ci={0:

(i, -k),

{k, -i)

(k = m+l,m + 2,

oo)};

5)

множества

Эц.

 

 

 

Множества Dtj в совокупности образуют множество точек, координаты которых удовлетворяют следующим

неравенствам:

 

 

 

 

2^.Xi^.m;

— tn^.x2^.

— 2; Xi — x2^m

+ 2.

Пусть

2 ^ г ' ^ т

и — z ^ j ^ t n

для

т нечетного и

m/2=sC/^.т для четного т. Тогда

 

D i j

= { 0 :

(i, - / ) , (/, - t ) } ;

 

 

6)

множество Е:

 

 

 

Е={0:

(k,l),

( - 1 , - А ) ( Л =

от+1,т

+ 2 , . . . ' , о о ) } ;

7)

множество F:

 

 

 

F = { 0 :

( i , * ) ( t = - 2 , - 3 ,

- о о ; £ = 2 , 3 , . . . , оо)};

8)

множество G:

 

 

 

G={0:

(i,k),

(-k,

-i) (i = m + l , m + 2, . . . , oo; k = 2,

 

3 , . . . , o o ) } ;

 

 

 

ГЛАВА I

 

134-

•

•

9) множество Я:

 

Я = { 0 : 0", -k)

(i = m+\,m + 2,.. .,оо- k = m+\,m

+

+2 , . . . , о о ) } .

Впредположении, что Р0(Н) — 1, получим следующую систему уравнений для искомых величин:

Г3P(Ai)-P(Bi)-P(Ai-l)=Q;

W

I

-Р(А{)+ЗР(В^-Р(В^)=0

 

 

 

 

(i = 2,3,...,

m;

/ > ( Л , ) = 0 ) ;

 

m

 

 

 

 

3P(B0)-

^P(Bi)-P(G)=0;

 

 

 

 

i = i

 

 

 

 

3P(Bl)-P(B0)-2P(F)=0;

 

 

 

 

2P(C1)-P(E)-P(G)=0;

 

 

 

 

 

3P(Ci)-P(Ci-l)-P(DUm)=0

 

 

 

 

 

 

{1 = 2, 3, . . . ,

m);

 

 

4P(DU)-P(Di-Ui)-P(Diti-<)

 

= 0

 

 

 

( I > / + 1 ;

i + / > m

+ 2);

 

4P(DU)

- 2P(D^hj)-P(D^X)

 

 

= 0

 

 

 

( t ' = / + l ;

i + / > m

+ 2);

/ач

J 4 Р ( О ;

, , ) - Р ( ^ _ 1 > ; ) = 0

 

 

 

 

 

J

(t' = /;

i+j>m

+ 2);

 

 

m

 

 

m

 

 

2P(Di,i)-

] ? (\+bik)P(DUk)-

 

 

^ P ( D k t i ) -

 

 

k=j+\

 

 

h=i+\

 

 

 

-P(Ci)-P(Cj)=Q

 

 

 

 

 

 

(i+i = m + 2;

6

« -

{ J ;

; ; * ) ;

 

m

 

 

 

 

 

3P(E)-

^P(Ci)-2P(H)-P(Am)=2;

 

2P(F)-P(BQ)=0;

 

 

 

 

 

2P(G)-P(Bm)-P(E)=0;

 

 

 

 

2P(H)-P(Cm)=2.

 

 

 

 

(1.11.19)

ПОИСК БЕЗ САМООБУЧЕНИЯ

135

Из подсистем (а) и (р) найдем:

 

Al-h

_L Oi-fe

Al-h _

Ol-k

 

P(Ah)

=

1

/> (Л,)

P

(Bt);

P (Bh)

=

-

P (Л0 +

3 —

/> (50 ;

 

2'-'

+ 1

 

 

 

т ) = ^ п г т Р ( Л г ) ;

 

 

P(Dh,m)=2^P(Cm);

P(Ch)=2^P(Cm).

(1Л 1.20)

После подстановки соотношений (1.11.20) в оставшиеся уравнения системы (1.11.19) и решения полученной сис­ темы найдем:

 

2 т - ' - 1

 

12

 

,

1 7 - 2 т - 2 + 1

п / _ . ч

=

34 - 4^-4-3 - 2 m - i — 1

Р(Ст)=

л п лт_0

; Р(Е)

5 j . 4m - 2

'

 

17 .4"г-2

> v '

 

P(77) =

J L ; p(G) = —

 

— .

(1.11.21)

Находя с помощью соотношений (1.11.20) и (1.11.21) все необходимые величины и подставляя их в (1.11.7), по­ лучим

^ = 1 0 + m

+

1 ^ j .

 

 

 

 

 

(1Л1.22)

Для

случаев,

когда

начальное

состояние

расположено

в множествах

G и F, тем же методом соответственно по­

лучим:

 

 

 

 

 

 

 

 

 

 

N e = l

0 + m +

£

+ L ;

^

 

8 +

^

± 2

f .

(1.11.23)

 

 

 

1 7 - 2

ш

—

1

7

• 2 m

 

Определим теперь время, необходимое системе для первого попадания в окрестность минимума. Назовем такт правильным, если система в конце данного такта не удалилась от точки минимума, т. е. приблизилась к ней или осталась на том же расстоянии, на котором она на­ ходилась в начале такта. В противном случае будем на­ зывать такт неправильным.

ГЛАВА I

136

Пусть до того, как система попала в окрестность мини­ мума, прошло п тактов и пусть правильных было k. Число неправильных тактов равно тогда n — k. При дан­ ном методе поиска потеря времени на каждый непра­

вильный такт равна 2 сек. В самом деле,

1 сек уходит на

то,

чтобы совершить

этот

неправильный

такт, и 1 сек

на

то, чтобы потом

снова

сделать шаг в правильном

направлении, так как после п тактов система должна оказаться в окрестности минимума.

Из k правильных тактов 2 необходимы (при сделан­ ных предположениях) для попадания в указанную ок­ рестность. Время, требующееся для осуществления этих тактов, обозначим t'. Остается k — 2 тактов, которые сис­ тема затрачивает на «колебания» около осей хх и.хг, яв­ ляющихся (при предположениях, сделанных относи­ тельно показателя качества) линиями остановки, и на «отражение» от границ запрещенных множеств. В обоих случаях на каждый такой такт затрачивается 2 сек и, следовательно, всего 2 (k — 2) сек.

Таким образом, время, соответствующее первому попа­ данию в окрестность минимума за п тактов, равно

t = t' + 2(k-2)+2(n-k).

(1.11.24)

Усредняя это выражение по возможным

реализациям,

получим

 

T = f + 2(N-2).

(1.11.25)

Подставляя вместо ./V его значения, соответствующие случаям (1.11.17), (1.11.18), (1.11.22), (1.11.23), получим зависимость времени поиска от формы и размеров за­ прещенных областей и от расположения начальной точки на плоскости.

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

время

как

формулы (1.11.17),

(1.11.18),

(1.11.22),

(1.11.23)

и

(1.11.25)

показывают,

что при

применении

случайного

поиска

цель может

быть достигнута за

вполне приемлемое

время.

 

 

Г Л А В А I I

ПОИСК С САМООБУЧЕНИЕМ

§ 2.1. А Л Г О Р И Т М Ы С А М О О Б У Ч Е Н И Я

П Р И С Л У Ч А Й Н О М П О И С К Е К А К В Е Р О Я Т Н О С Т Н Ы Е А В Т О М А Т Ы

В предыдущей главе были исследованы ал­ горитмы случайного и детерминированного поисков как вероятностные автоматы в случайных средах. В настоя­ щей главе исследуем с использованием такой интерпре­ тации различные алгоритмы самообучения.

Под с а м о о б у ч е н и е м при поиске понимается из­ менение вероятностных характеристик процесса поиска. Пусть вероятность выбора шага АХ в пространстве пере­

менных

Х = (хи ... ,хп)

зависит

от векторного параметра

W, который

назовем

в е к т о р о м

« п а м я т и »

и число

координат

которого

равно

числу

координат

вектора

АХ, т. е.

 

 

 

 

 

 

 

 

 

W = ( a > b . . . , a > „ ) .

 

 

 

 

 

(2.1.1)

Вероятность выбора

yV-ro шага поиска

A X W задается

как

условная вероятность

 

 

 

 

 

 

pN(AX)=p(AXN/WN),

 

 

 

 

 

(2.1.2)

где WN

— значение

вектора

памяти W

на JV-M

шаге

по­

 

иска.

 

VJN

 

N-м

 

 

 

Значение

вектора памяти

на

шаге поиска

оп­

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

ния

вектора

памяти

Wjv_i на (JV — 1)-М шаге,

от сделан­

ного

шага

AXJV-I

и от

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

качества

A Q ' J V _ I , полученного на

(N— 1)-м шаге:

 

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