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

Скачать файл (8,31Мб)

Заказать решение

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

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

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

Добавлен: 19.06.2024

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

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

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

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

159

flfi(l)	ft (2)	0	0	0 -	0	0		0
q2{\)	0 q2(2)		0	0 •••	О	О		О
О	&(1)	0	q3(2)	0 - 0		О		О
0	0	0	0	0 -q2k(l)		0		<?2,(2)
О	О	0	0	0 -	0	q2h+i(\)	cJ2k+i{2)
								(2.1.74)
найти из матриц Ри,и-\			и Рц путем			замены	в	последних
элемента	q(u-l){2h+l)+i	(1) элементом			q ( l i - m k + l ) + i			(3) и эле
мента q(n-\)(2h+i)+i		(2)	— элементом			9 ( u _ I ) ( 2 M - I) - H (4) (£ =
— 1	2ЛЕ-Ы).

Далее рассмотрим тот вид самообучения, когда в фор

муле	(2.1.3) п е р е х о д н а я					ф у н к ц и я			Чг =	Ч / ( \ ¥ № - ь
AQN-U	AXn-I)	не	з а в и с и т			от в ы х о д а			автомата,
т. е. когда
V = V ( W w _ b A Q V - i )										(2.1.75)
и 4r (WJ V _i,		AQ'JV - I )	— д е т е р м и н и р о в а н н а я							ф у н к
ц и я .	Такой алгоритм самообучения наиболее удобно за
дать при помощи формулы
	Wjv - j - 8		sign A Q ' J V - I I , если				\| W J V \|		s£d"yn;
						если		\WN\>dyn,
		\| W j v \|							(2.1.76)
где I	— л-мерный вектор				с координатами			— 1 , 0 или + 1 ,
	соответствующий				некоторому		фиксированному
1 =	направлению			шага;
	( t i , . . . , in).									(2.1.77)
В формуле		(2.1.76)		последующие			значения			вектора
памяти W зависят не от сделанного шага, а от получен
ного приращения AQ'JV - I оптимизируемой функции. Да
лее будет показана			работоспособность				алгоритма при ре

шении задач оптимизации. Такой алгоритм самообучения представляет собой вероятностный автомат с детермини рованными переходами и случайными выходами. Полное

ГЛАВА II

160

функционирование такого автомата описывается цепью Маркова с матрицей переходных вероятностей (2.1.25), которую можно построить, если известны матрицы пере ходных вероятностей автомата при нештрафе А0 и при штрафе А{ и матрица вероятностей штрафов S* автомата по отношению к его состояниям.

Построим матрицы переходных вероятностей Ло и А\ для этого автомата. Напишем формулу (2.1.76) отдельно для случаев

sign AQ'A -_i = ± 1,	(2.1.78)
т. е. при AQ'<0
W.v-j + ei*0 ',	если iW . vl^rfj'n;

(2.1.79)

•, если [ Шл - j >d~\'n,

|WJV|

а при AQ'^ O

	\V2v_i-6K1 »,	если	\| W w \| < r f y n ;
				(2.1.80)
	W A - = ^ ^ ,	если	\VJN\>dfn.
Здесь	и I * 1 ' — n-мерные векторы, координаты			которых
равны	± 1 , т. е. они направлены вдоль биссектрис			прост

ранственных углов, образованных координатными квад рантами.


Пусть
КО =(;,(<»,,..,;„«»);						(2.1.81)
Ю) =	(i,0) . . .			inm).		(2.1.82)
Рассмотрим			случай, когда
КО = id) = ( S			g n	а»,, ... , sgn а>„).		(2.1.83)
Функция		sgn		определена выше (2.1.47). По			фор
муле	(2.1.79)			получаем	переходы	автомата	при
нештрафе		(с = 0), а по формуле (2.1.80)				— переходы при
штрафе	( с = 1 ) . Эти переходы				представлены на рис, 2.1.7.

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

161 •

Матрицы А0 и А\, характеризующие реакцию автомата соответственно при нештрафе и штрафе, имеют вид

		1 0		0 0		0	0	0 1
Л 0	=	0	1 0		0	0	0		1 0	(2.1.84)
		0	0		1 0	0	1 0		0

		0	0	0 1		1 0		0 0

Для случая т>2п переходы автомата, определяемые формулами (2.1.79) и (2.1.80), при учете формулы (2.1.83), показаны на рис. 2.1.8. Переходная матрица Л 0 имеет блочный вид

/>„«>>	о	о	о
(0)	о	о	о
	Р32<°>	о	о	(2.1.85)
				(2.1.85)
0	о	о	- P2h-\,2k (0)
0	о	о •••

где нулями ооозначены матрицы, элементы которых равны нулю; i 3 , / 0 ) — матрицы порядка (2k)X(2k), рав ные между собой:

	С=0			с~1
Рис.	2.1.7. Граф	переходов	автомата,	переходы которого
не	зависят от	выходной	функции,	для случая т—2п

(п=2).

11 — 2014

ГЛАВА 11

162

pii(0)=p{0)==	2k	(2.1.86)

Переходная матрица А\ равна следующей блочной мат рице:

о л 2 ( 1 )		о о		О	0	0
о	о	/ V " о		0	0	0
о	о	о	о	Рок-
				2fe—1,2ft—2(1)
о	.0	о	о	о	2ft,2ft-l (i) о

(2.1.87)

где — матрицы порядка (2/г)Х(2/г), равные между собой:

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

163-

/>1;.(1) = />(!) =

0	1 0 0-	о о о ••• о о
0	0 1 0 -	о о о ••• о о
0 0 0 0-		•О 1 0 - 0 0		(2.1.88)
0	0 0 0-	• 1 о о ••• о о		(2.1.88)
0	0 0 0-	• 1 о о ••• о о
0	0 0 0-	• 0 0 0 ••• 1	о
0	0 0 0-	• 0 0 0 ••• 1	о

( t = l , . . . , 2*; / = l , . . . , 2 f e ) .

Функционирование автомата в случайной среде описы вается цепью Маркова с матрицей переходных вероят ностей вида

Рп	Pl2	0	0	0 ••	0	0	0
	0	Р2з	о	0 ••	0	0	0
0	Рз2	0	P3i	0 ••	0	0	0
А-.
0	0	0	0	0 ••" Ргк-1,2к--2		0	Р2h-\,2k
0	0	0	0	0 ••	0	P2k,2k-\ P2k,2h
							(2.1.89)
Здесь Рц равны		матрицам
Pu=(I~S*l)A0;					PiA-1=(I-S*i)A0-
							(2.1.90)