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

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

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

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

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

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

Добавлен: 19.06.2024

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

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

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

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

195
Рассмотрим	случай, когда	выполняется	условие
0 < d < l . Тогда	из (2.3.11) при	предельном	переходе
N-+oo получаем
Р г = у Ф г			(2.3.12)

( t = l , . . . , 4 ) .

В этом случае цепь Маркова является эргодической, т.е. предельное распределение вектора W не зависит от его начального распределения. Оно зависит от величины по мехи а. Из выражения (2.3.12), учитывая (2.3.7), нахо дим

im pi = —			при £ = 1 , . . . , 4;
0->оо	4	j		(2.3.13)
lim pi=	I	—•	при i =	1, 2;
lim pi=	I	2		л
C-»-0	I	n	о	л
		О	при 1 = 3, 4.

Из формул (2.3.13) видно, что при о->-оо вектор W

равномерно	распределяется по	всем состояниям i (i =
= 1,...,4),	а при а-*-0 вектор W с одинаковой			вероят
ностью 1/2	принимает состояния	1 и 2 и с	вероятностью
О -— состояния 3 и 4.			Q(X\,	х 2 ) на
Среднее	приращение функции	качества	Q(X\,	х 2 ) на
N-ы шаге поиска равно
	4
MN[AQ]=	£ PiWM[AQ/V/i],		(2.3.14)
где
Af[AQ/Wi] = dAQ(*).			(2.3.15)

Подставляя выражения (2.3.11) и (2.3.15) в соотноше

ние (2.3.14), получаем
MN[AQ]	= - J -	d { Ф	) [ 1 + d™ (р,(0) + р4<о) _
	2у2	х	2а '
			/ДО(2) \
_ р 2 ( 0 ) _ р 3 ( 0 ) ) ] ( а 1 + а 2 ) + ф ^ _ bL _
-	^ (р, (0) + рА(0)		_ р 2 ( 0 ) _ р з ( 0 ) ) ] ( а 1 _ а г ) \| ,

(2.3.16)

13*

(

ГЛАВА II

196
где cci и а2 являются	направляющими				косинусами		гради
ентного вектора, причем a,i2		+	а22=1.		из (2.3.16)		полу
В предельном случае, когда N-voo,					из (2.3.16)		полу
чаем
M[AQ]=limAijv[AQ]= —l —d\ Ф (£9!!					) (ai +	a2)	+
w^oo	2У2	"-	v	2а	1		+
+ Ф ( ^ ) (	а 1 _ а	2 ) ] .				(2.3.17)
Отсюда имеем:
1						(2.3.18)
lim M[AQ]= —= dau						(2.3.18)
lim M[AQ] = 0.						(2.3.19)
На рис. 2.3.1 представлено		поведение среднего				прираще

ния функции качества в зависимости от уровня помехи о для случаев, когда направление градиента совпадает с

осью Х\	(tzi = l ;	а 2 = 0)	и когда	направление	градиента
совпадает	с биссектрисой		ДХ(1> (ai = о.2 = 1/У2). Очевидно,
что при малых помехах			(ст^1)	система лучше оптими
зируется	тогда,	когда направление градиента			совпадает
с осью х\, хуже, — когда			направление градиента совпа

дает с биссектрисой ДХ<!>. Для помех <т>1,5 среднее уве личение функции качества практически не зависит от на правления градиента оптимизируемой системы.

WMIAO)

Р и с . 2.3.1. Характеристика изменения среднего при ращения функции качества на одном шаге поиска для я = 2 и 65=2<i при N-+°° в зависимости от уровня помехи о.

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

197

Далее рассмотрим частный случай, когда d=\. Под ставляя в матрицах (2.3.9) и (3.3.10) d=\, получаем

	Ф, 0		0 Ф 4
А*=А =	0	Ф 2	Ф 3	0
	0	Ф2	Ф 3	0

	Ф,	0	0 Ф 4

В этом случае вероятности пере хода вектора W из одного состоя ния в другое не зависят от номера шага N. Эти переходы показаны на рис. 2.3.2. Видно, что состояния цепи Маркова образуют два зам кнутых множества [50]. В одно мно жество входят состояния 1 и 4, во второе — состояния 2 и 3.

Подставляя в формулу (2.3.11) d=l, получаем:

р1 ОУ) = ф 1 ( р 1 ( 0 ) + р 4 ( 0 ) )

p2W = <S>2(p2M+Pal0))

р3 ( Ю = ф 3 ( р 2 ( 0 ) + Р з ( 0 ) )

р4 ( Ю = Ф 4 ( Р 1 ( 0 ) + Р 4 ( 0 ) ) .

(2.3.20)

Рис. 2.3.2. Граф пе реходов вектора W при d = 1.

(2.3.21)

Следовательно, распределение вектора W по состоя ниям i также не зависит от номера шага поиска N. Это распределение зависит лишь от начальных вероятностей

Pi '

В пределе при N-*-oo из (2.3.21) получаем:

*- { ^( P l ( 0	) + P 4 ( 0 ) )	(t= 1, 4);	(2.3.22)
( Р 2 ( 0	) + / ? 3 ( 0 ) )	{1 = 2, 3).
Подставляя в выражение		(2.3.16) d=\,	имеем
Af[AQ] = M w [ A Q ] = - 4 f		Ф ( ^ ^ ) ( P i ( 0 )	+ P 4 ( 0 > ) ( a 1 +
	у 2	' п2о

+ а2 ) + Ф ( ~ ^ ) ( Р 2 т + Р ъ т ) (ai - a 2 ) ] . (2.3.23)

ГЛАВА II

	198
Из этой формулы		находим:
lim M[AQ] = ~		a. + ~	(Plm	+ р 4 ( 0 ) - р 2		< 0 ) -Рз<0 ) ) «2 ;
ст->о	У2	У2					(2.3.24)
							(2.3.24)
limAf[AQ] = 0.						(2.3.25)
СГ-юо
2. Многомерный		случай (п>2;			8^2d).	Пусть	направ
ляющие	косинусы	градиентного		вектора		oti	(i=l,...,п)
удовлетворяют условию
« i > « * > - > « » > 0 ;						(2.3.26)
a i > a 2	+ ••• + an -
Тогда	при нумерации		состояний		вектора W		(2.2.52)
предыдущего параграфа			имеем:
AQ( 1 ) , A Q ( 2 ) , . . . > A Q < 2 " - I ) > 0 ;							g ^
A Q ( 2 " - 1 + i ) ; . . . ;		A Q < 2 " ) < o .

Проделав те же самые выкладки, что и для п = 2, по лучаем предельное распределение вектора W по состоя ниям:

Р<= ^ = Т ф *

( 2 3 - 2 8 >

(t = l , . . . , 2 » ) .

Среднее	приращение	функции	качества Q ( х ь . . . , хп) на
один шаг	поиска в предельном		случае N-+oo равно
	2 "		i
M[AQ] = d • 2' - "		ФгД<2<1> = d • 2 1 - "

z=i

х{[Ф(^1)+ ...+Ф{^1)]в|+

+ [ ф ( ^ ) + . . . + ф ( ^ _ )

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

199

СС2+ •"

- Ф / AQ( 4 ) \ . / AQ<2 " ') \ 1

Ф	AQ (2 п - 1	) ] • " }	(2.3.29)
	2а

В предельном случае из этой формулы следует:

lim M[AQ] = — - ссь	(2.3.30)
limM[AQ] = 0.	(2.3.31)

§ 2.4. СВОЙСТВА ПОКООРДИНАТНОГО САМООБУЧЕНИЯ С МАЛОЙ ИНТЕНСИВНОСТЬЮ ПРИ СТАТИСТИЧЕСКОЙ

ОПТИМИЗАЦИИ С ПОМЕХАМИ

В предыдущем параграфе был рассмотрен случай покоординатного самообучения, когда вектор па мяти W может принимать одно из 2П = 4 возможных зна

чений, т. е. когда количество состояний автомата					совпа
дает с количеством			его выходов (т = 2п).	В этом	пара
графе рассмотрим случай, когда т= (2k+l)n,				т. е. когда
т>2п.	Пусть функция Q(X) обладает теми же свойст
вами,	которые	были	заданы формулами (2.3.1) — (2.3.8).
Тогда	работа	алгоритма как вероятностного автомата,
функционирующего			в случайной среде,	описывается

ГЛАВА II

200

Ри

Р\2

0 •••

Р21

О Р2г

О -

л =

Р32

О Р3 4

О -

О ••• Р2ft—i,2ft-:

О •••

цепью Маркова с блочной матрицей

переходных

вероят

ностей [51], т. е. матрицей

(2АЛ).

В этой матрице нулями обозначены блоки, элементы

которых равны нулю, а Рц — матрицы типа

Якоби

(2k+\)-го

порядка,

определяемые

формулами (2Л.73) и

(2.1.74)

(например,

матрица

(2.4.2),

где рц —

вероят

ность

перехода

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

в состояние / ) .

Рп =

рп

Pi2 0

0 •••

P2i

р 2 3

о •••

О рз2 0 p3i

о •••

0 ••• p2k-l,2k-2

P2k-\,2k

0 •••

p2h,2h-\

p2ft,2ft+i

0 •••

p2k+\,2k p2h+i,2h+i

(2.4.2)

Элементы

ptj

(/= 1 , . . . ,

(2k +1)2;

/ = 1 , . . . , 4 )

определя

ются

формулой

(2.1.59)

при учете

формул

(2.3.6) и

(2.3.7), т. е.

Ри=

(Яа +

Яи5-з)®ь

(2.4.3)

где

<7«

1 + ауг<*) sign

Axilft).

(2.4.4)

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

(2.4.1)

ОP2k-U2k О

^2ft,2ft-l 0 P2h,2h+\

ОP2k+l,2k P2h+\,2h+\

Элемент получен из формулы (2.1.41) с использова нием конкретного вида функции F(qi, wi), заданной фор


мулой	(2.2.1). Нумерация	состояний и переходы			вектора
W из одного состояния в другое для этой цепи					Маркова
показаны на рис. 2.4.1. Учитывая матрицу				(2.4.1), полу
чаем	систему векторных	уравнений	для	нахождения
предельных вероятностей		pi (i— 1 , . . . ,	(k+1)2):

i=i

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

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

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

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

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

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

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

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

Информация

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

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