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

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

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

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

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

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

Добавлен: 19.06.2024

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

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

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

ГЛАВА III

302

шагов в направлении неудачного шага с вероятностью, равной единице.

Выше были построены оптимальные алгоритмы поиска в классе алгоритмов, определяемом матрицами (3.2.1). Теперь найдем оптимальные алгоритм'ы в некоторых бо лее узких классах алгоритмов.

1. Класс алгоритмов поиска, задаваемый матрицами

т1			т1	т
1			1_	т	Yo	Yi	Y2	Yi
А0 = т			т	т	Yi	Yo	Yi	Y2
А0 = т			1	_1_	Y2	Yi	Yo	Yi
т			т1	т	Yi	Y2	Yi	Yo
т1_			т					(3.2.111)
								(3.2.111)
По формулам			(3.2.110)		находим:
P = Pi + p	2	=	2	Y = Yi + Y2-				(3.2.112)
P = Pi + p		=	2	Y = Yi + Y2-

Подставляя эти величины в формулы (3.2.108) и (3.2.112), имеем:

Рср = Si2 +		s22+4\SiS2			(3.2.113)
		1+2у
M[AQ]=		( 2 у - 1 )		(sl-s2)	(3.2.114)
		2 у + 1

Для	этого	класса	алгоритмов		M[AQ] принимает мини
мальное значение			— 1/3(si — s2)		при у= 1, т. е. при уо=0
и Y i + Y 2 = l - Следовательно,					в оптимальном алгоритме
исключается повторение неудачного шага.
2.	Класс	алгоритмов		поиска,	задаваемый матрицами

ОПТИМАЛЬНЫЕ АЛГОРИТМЫ

зоз

ро	pi	Р2	Pi	т1	т
				т1	т
Pi	Ро	Pi	Рг
Р2	Pi	Ро Pi		1	1
				т
Pi	Рг	Pi	Ро		т

				т1	т1

Для этого класса имеем: p=Pi + p2 ; у=\12. лам (3.2.108) и (3.2.109) находим:

2p(s1 2+s2 2)+2s,s2

	Р с р =	2 р + 1
		2 р + 1
	M[AQ]=-	( l - 2 p ) ( S l - s 2 )
	M[AQ]=-	1+2р
		1+2р

4	т
1	1
т_1_	т
т1	т
т	т
	_1_

(3.2.115)

По форму

(3.2.116)

(3.2.117)

Для этого класса	алгоритмов	M[AQ] принимает мини
мальное значение,	равное — (si — s2 ), при р = 0,		т. е. при
Ро=1; Pi = p2 = 0. Следовательно,		оптимальным	является
алгоритм случайного спуска.
3. Класс алгоритмов поиска, задаваемый матрицами
(алгоритмы поиска с возвратом при неудаче)

	Ро	Pi	Рг Pi		0	0			1 0
А0--	Pi	Ро	Pi р2		0		0	0	1	(3.2.118)
А0--	Рг	Pi	Ро Pi		1 0			0	0	(3.2.118)
	Рг	Pi	Ро Pi		1 0			0	0
	PI	Рг	Pi Ро		0		1 0		0
Для этого класса p = Pi + p2 ; у=1.					Для среднего штрафа
и среднего		приращения		функции	качества				имеем:
	_ P(S,2 + S a 2 ) + 5 l S 2			-

Pep

—

(3.2.119)

ГЛАВА III

	304
M[AQ]=	( 1 - p )	(Sl-s2)	(3.2.120)
M[AQ]=	-		(3.2.120)
	1+p
JW[AQ] принимает минимальное			значение, равное — (s\ —

— s2), при 0 = 0, т. е. при Ро=1; 01 = 02 = 0. Оптимальным является алгоритм, в соответствии с которым при удач ном шаге продолжается спуск, а при неудачном проис ходит возврат в предыдущее состояние.

4. Класс алгоритмов поиска, задаваемый матрицами

^'алгоритмы спуска)
0	о	Yo	Y i	Y2	Y i
1	о	Y i	Yo	Y i	Y2	(3.2.121)
0	1	Y2	Y i	Yo	Y i	(3.2.121)
0	1	Y2	Y i	Yo	Y i
о	о	Y i	Y2	Y i	Yo

В этом случае 0 = 0; Y = YI + Y2-		Отсюда следует:
p c p = 2sl S 2 ;	M [ A Q ] = - ( s , - s 2 ) .	(3.2.122)
Полученные	выражения для рср	и M[AQ] имеют место,

если уФО. Поэтому оптимальным является алгоритм, ко

торый исключает	повторение	неудачных шагов поиска.
§ 3.3.	С И Н Т Е З	О П Т И М А Л Ь Н О Й

СТ Р У К Т У Р Ы А Л Г О Р И Т М О В

СА М О О Б У Ч Е Н И Я

В§ 3.1 и 3.2 был рассмотрен синтез опти

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

Найдем оптимальные алгоритмы в классе алгоритмов,


которые задаются автоматами со случайной						переходной
функцией 4/ = 4 F ( W A T _ I , AQ'N-I),				не зависящей от выхода
автомата		AXJV - I , и	со случайной выходной			функцией
pN(AX)	=	p(AXN/XVN).	Пусть	переходы	автоматов, рас
положенных на координатах				Wi ( / = 1 , . . . , п ) вектора W,
из одного		состояния	в другое	w^^f-wi^	задаются мат-

ОПТИМАЛЬНЫЕ АЛГОРИТМЫ

305

рицами переходных вероятностей, одинаковых для всех координат W/. Пусть это будут следующие матрицы:

при нештрафе (ДС?'<0)

R(l)=Ro=				0 . . . 0		0	0 0 0 . . . 0					0		0
	гг 0 0
Г\ 0 г2			0	0	.. . 0	0	0		0	0	.. . 0 0 0
0	Г\ 0 г% 0				.. . 0	0		0	0	0	. . . 0		0	0
0	0	0	0	0	.. • г{	0		Н 0		0	. . . 0		0	0
0	0	0	0	0	.. . 0			0 Г\		0 .. . 0		0		0
0	0	0 0		0 . . 0		0		0 0		0	. • г2		0	Г\
0 0		0 0		0 . . 0 0				0 0 0 . . 0					Гг

(3.3.1)

при штрафе (AQ'jjsO)

г2	Г\	0 0 0			. . 0 0 0 0 0 . . 0 0 0
Гг 0 Г\			0	0	. . . 0		0 0			0	0 . . . 0		0 0
0 г2		0	Г\	0 .. .		0	0		0 0		0	.. . 0		0 0
0	0	0	0 0 .. •			г2		0 Г\ 0			0	.. . 0		0	0
0	0	0 0 0			.. .	0		Г\	0 гг 0			. . . 0		0	0
0	0	0	0	0	. . 0			0	0	0 0		.. • гх		0	г2
0	0 0 0 0				. . 0			0 0 0 0 . . 0 Г\							гг

(3.3.2)

где

г, + г 2 = 1 .

(3.3.3)

20 — 2014

ГЛАВА III

306

Выходную функцию автомата также задаем покоорди натно в виде одинаковых выходных функций Fi для всех координат wt (/= 1 , . . . , п):

	1				при	w{>q;
Fi = F(wi, q) =	2	\	1 +	J *	) при	\| а у \| ^ о ;
	2	\		q	) при	\| а у \| ^ о ;
	0				при	Wi<C—q,

где

Fi = F(wi, q) = В е р (Дх; = l/w = Wi);

1 — 7^ = Вер (Дх;= — 1/ш = &>,).

На изменение Wi накладываем ограничение

(3.3.4)

(3.3.5)

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

A=(I-S*)A0 + S*AX, (3.3.6)

где матрицы А0 и Ах являются матрицами (2.1.107) и (2.1.108), а матрица S* — матрицей (2.1.26). Элементы диагональной матрицы S* равны

2	(г =	1, .. .,	т),		(3.3.7)

j=i
где Sj — вероятность штрафа действия ДХ<Л;
qtj — вероятность		появления выхода		ДХ<л	при на
хождении автомата			в состоянии	wW;	цц опре

деляется формулой (3.3.4).

Задача синтеза оптимального алгоритма поиска за ключается в нахождении таких значений переходных вероятностей гх и г2 матриц (3.3.1) и (3.3.2) и такого зна чения параметра q в формуле (3.3.4), при которых сред нее приращение M[AQ] функции качества максимально. Предположим, что функция качества Q(X) линейна и

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

Ребрик Б.М. Вибрационное бурение скважин.pdf

Родин И.И. Проектирование одноковшовых строительных экскаваторов учеб. пособие.pdf

Розов В.М. Измерения и контроль в однополосном радиооборудовании.pdf

Романов В.Г. Обратные задачи для дифференциальных уравнений спецкурс для студентов НГУ.pdf

Руководство по проектированию золоотвалов тепловых электрических станций П 20-74 ВНИИГ..pdf

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

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

Информация

Списки файлов

Дополнительно