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

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

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

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

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

Добавлен: 19.06.2024

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

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

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

ГЛАВА II

174

Изучение динамики такого самообучения возможно и целесообразно с привлечением теории марковских цепей, которые хорошо описывают процессы подобного рода. В процессе обучения вектор памяти W переходит из од­ ного состояния в другое в соответствии с алгоритмом обучения (2.2.4) и ограничениями (2.2.5). Пусть общее число возможных состояний этого вектора конечно и равно т. Пусть также вероятность перехода из 1-го со­ стояния в /-е определяется числом рц. Тогда изменение вектора W в процессе самообучения

- > W J Y _ , - > W ^ W J W ^ ,

как это будет показано далее, образует простую цепь Маркова. Будет также показано, что в линейном поле эта цепь будет однородной. (В нелинейном случае пере­ ходные вероятности зависят от положения системы, т. е. от времени, что вносит неоднородность.)

Таким образом, матрица тХт переходных вероятнос­ тей pij определяет процесс самообучения, и задача за­ ключается в определении этих вероятностей с последую­ щим привлечением общей теории марковских цепей.

1. Случай n = 2; 6^2d. Исследуем сначала простейшую схему обучения в двумерном пространстве. В этом слу­ чае вектор W = ( ш ь w2) может находиться в одном из

Рис. 2.2.1. Пространства {W} и {X} для п—2.

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

175

четырех состояний, которые занумеруем в следующем порядке:

W^id.d);

W 2 = ( d , -d);

 

W 3 = ( - d , d ) ; W 4 = ( - d , -d).

{ - }

Эти состояния вектора W показаны на плоскости обуче­ ния на рис. 2.2.1, а.

На рис. 2.2.1,6 показаны возможные направления дви­ жения оптимизируемой системы в двумерном простран­ стве параметров. Таких направлений также четыре. Выбор направления движения определяется двумя сов­ местными событиями, а именно движением по обеим ко­ ординатам. Поэтому вероятности выбора указанных направлений движения следующие:

Р ( Д Х < П ) = №

 

 

/>(ДХ<2>)=/М1-р2 );

 

 

Р(ДХ(з)) = ( 1 - р , ) р 2 ;

 

 

P(AXW)

=

(\-pl)(l-p2),

 

 

где pi ( i = l , 2)

определяются

формулой (2.2.1).

Вероятности

р\ и р% зависят от

состояния вектора W,

что и создает марковость процесса

обучения.

Пусть

вектор

W находится

в состоянии Wi, т. е. W =

= [d, d).

Тогда

по формулам

(2.2.7) и при учете ограни­

чений (2.2.5) получаем следующие условные вероят­ ности:

P(AX0>/W,)=1

(l+d)(l+d)=qu;

 

P(AX«2)/Wi) =

j - ( l + d ) ( l - d ) = 9 i 2 ;

 

/>(AX<3)/W,) =

~(l~d)(l+d)=ql3;

(2 2 8)

 

P(AX«)/W,) =

1 ( 1 - ^ ( 1 - ^ ) = ^ ,

 

где P(AXW/V/i)

обозначает

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

ления ДХ«) при W = W,.

 

 

Аналогично

подсчитываем условные

вероятности

ГЛАВА II

176

P(AK^yWi) для других состояний вектора W. Получен­ ные значения показаны в табл. 2.2.1.

АХ(з')

ДХ(1)

AX(2)

» |

 

JL (1+<*)*•

1 (1-d2 )

 

4

4

 

 

w 2

4

A (i+d)2

 

4

 

 

w3

| JL (i - d 2 )

i - ( l - d ) *

 

[ 4

4

 

 

W4

\ - J - ( l - d ) 2

1

 

4

4

 

 

Т а б л и ц а 2.2.1

 

ДХО)

 

ДХ(4)

4

i - (1-d2 )

 

i - ( l - d ) 2

 

 

4

1

( i - d ) 2

j J- (i - d 2 )

| 4

1 4

 

 

• i ( i + d ) »

j

1 ( i - d 2 )

 

4

4

1 4- J - (1 - rf 2 ) 4

- J - d + d ) *

Теперь обратимся к алгоритму самообучения. Пусть для определенности градиентное направление располо­ жено между направлениями ДХО и ДХ<2> плоскости пара­ метров (см. рис. 2.2.1,6). Тогда

AQ(i) = [g rad Q, ДХ<Я]

(2.2.9)

0 = 1 , . . . , 4);

 

AQ<1 >>0; Д(3<2 >>0; Д<Э<3><0; AQ<4 ><0.

(2.2.10)

Переходим к автоматному представлению этого алго­ ритма самообучения, т. е. рассмотрим вектор W как со­ стояние автомата, а ДХ — как его выход. Тогда таблица 2.2.1 представляет матрицу вероятностей выходов авто­ мата Qij. Случайная среда, с которой взаимодействует автомат, задается модифицированной формулой (2.1.10) предыдущего параграфа:

S j = Bep ( A Q < 0 / A X = AX«)) = i-[

)],

(2.2.11)

где приращения функции AQO') определяются формулой (2.2.9).

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

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

177

автомата учитывается то, что происходит поиск макси­ мума Q(X). Предположим, что функция Q(X) является линейной, т. е. приращения AQ<->> ( / = 1 , 2, 3, 4) не меня­ ются в процессе поиска. В этом параграфе будем исхо­ дить из предположения, что на функцию Q(X) не накла­ дывается помеха (а = 0). Тогда по формуле (2.2.11) с учетом формул (2.2.10) имеем:

s, = s2 = 0; s3 = s 4 = l .

(2.2.12)

•Функционирование автомата в стационарной случайной среде (2.2.12) описывается цепью Маркова с матрицей переходных вероятностей (2.1.60). Подставляя в эту матрицу значения из таблицы 2.2.1 и значения из формулы (2.2.12), получаем матрицу переходных вероят­ ностей для вектора W:

 

J_ (1+0-2)

 

У

 

J_ (1-flf2 )

A (W/Wi)

2

J_

 

 

У (1-<*2 )

 

J_

 

У (1+d2 )

1

у (l-d*)

1 У (1+0-2)

1

У (l+d*) У1 ( l - d 2 )

Возможные переходы вектора W из одного состояния в другое пока­

заны на рис. 2.2.2.

 

 

 

 

 

Из

матрицы

видно, что переходы

вектора W из одного состояния в

другое

образуют

простую,

однород­

ную цепь Маркова. Состояния

3 и

4 являются несущественными;

зна­

чение имеют только состояния

1 и 2,

т. е. такие, первая

координата

кото­

рых

положительна.

Это

вызвано

тем,

что в состояниях

1 и 2 прира­

щение

функции

качества

 

макси­

мально

(напомним, что рассматри­

вается

случай

максимизации

пока­

зателя

качества

объекта).

 

 

 

0 0

0 0

(2.2.13)

0 0

0 0

Рис. 2.2.2. Граф веро­ ятностей перехода для вектора памяти (на­ правление градиента расположено между биссектрисами перво­ го и четвертого квад­ рантов).

12 — 2014

ГЛАВА II

178

 

 

 

 

 

Из матрицы

 

(2.2.13), используя формулу

Перрона [48]

и учитывая таблицу 2.2.1, получаем матрицу

 

переходных

вероятностей за N шагов для вектора памяти W:

 

 

l ( l + d 2 N )

1 ( 1 -d™)

0

0

 

 

_1_

1 ( 1 + d™)

о

0

 

 

т

A ^ ( W / W i )

=

 

 

 

_1_

1 ( 1 + ^ )

о

 

 

 

0

 

 

~2~

 

 

 

 

 

 

 

~(l+d™)

-(l-d™)

о

0

 

 

 

 

 

(2.2.14)

Пусть p i ( 0 ) обозначает вероятность того, что в начале поиска вектор W находится в состоянии i, P i i N ) — веро­ ятность того, что на iV-м шаге поиска вектор W нахо­ дится в состоянии i, я Pi — вероятность того, что в пре­ деле при Л/->-оо вектор W будет принимать значение Тогда по матрице (2.2.14) получаем:

P i w

= l + l d 2 i V ( p 1 ( 0 ) + P 4 ( 0 ) )

1 ^ ( р 2 ( 0 ) + р 3 ( 0 ) ) ;

Р2(Ю: 1

-

1

d™ (Pi О) + P i

<°>) +

у d™ (p2(0) + Рз(0)) ;

Рз

= p 4

( i V )

= 0.

 

 

(2.2.15)

 

 

 

 

 

 

 

Рассмотрим

 

случай, когда

выполняется

условие

0<d<l.

Тогда

из (2.2.15)

при

предельном

переходе

N—>-оо получаем:

 

 

 

Pi =

lim p i ^ ' =

*

 

 

 

 

 

 

 

2

 

 

(2.2.16)

 

 

 

 

_1_

 

 

р2=

lim р2(Ю

=

•

 

 

 

2

 

 

 

Из выражения (2.2.16) следует, что в этом случае цепь Маркова является эргодической, т. е. предельное рас-

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

179

лределение вектора памяти W не зависит от его началь­

ного распределения. Из этого же выражения

видно, что

в пределе при N-^oo вектор W равновероятно

пребывает

в существенных состояниях 1 и 2.

 

Изложенный прием определения предельных вероят­ ностей р\, р2 требует вычисления корней характеристи­ ческого уравнения и миноров матрицы переходных веро­ ятностей Л (Wj/Wj), что весьма сложно для матриц боль­ ших размерностей. Эти же предельные вероятности можно получить стандартным образом, решая систему

линейных

уравнений

 

 

Р = Л ' Р ,

 

 

 

(2.2.17)

где А'

—

транспонированная матрица (2.2.13);

Р — вектор предельных вероятностей.

 

Определим

теперь

среднее приращение

функции

Q(x\, х2)

на N-м шаге

поиска:

 

 

 

4

 

 

 

MN[AQ]=

У

p4 <*W[AQ/WJ,

(2.2.18)

 

 

Iff

 

 

 

где M[AQ/V^i] — среднее приращение функции качества при W = W , ; суммирование ведется по всем состояниям i. Среднее приращение M[AQ/W,] вычисляется по формуле

4

 

Af[AQ/W; ]= ^P(AXMIV/i)\Qii),

(2.2.19)

где P(AX'i'/Wi) определяется таблицей 2.2.1, AQb'J — формулой (2.2.9). Суммирование ведется по всем воз­ можным направлениям движения оптимизируемой сис­ темы в плоскости параметров. Из формул (2.2.9) и (2.2.10) и таблицы 2.2.1 следует, что

M[AQ/Wi]

= dAQ<iK

(2.2.20)

Поэтому

 

 

 

MN[AQ]=

-LdaУ2 x

+

 

+

J _ d 2 ^ + i a 2 ( p 1 ( 0 ) + p 4 ( 0 ) _ p 2 ( 0 ) _ p 3 ( 0 ) ) >

(2.2.21)

 

Г

 

 

12*

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