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

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

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

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

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

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

Добавлен: 19.06.2024

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

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

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

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

321

метода покоординатного спуска, S3 — стратегия случай ного поиска с парными пробами и т. д.).

Синтез такого алгоритма сводится к выбору его со ставляющих из множества алгоритмов (3.4.3) и опреде лению вектора их весов (3.4.2). Очевидно, что при задан ном объекте и выбранном критерии эффективности ал горитма вектор (3.4.2) вырождается в единичный. Это означает, что наилучшей смешанной комбинацией алго ритмов является отсутствие комбинации, что и сводится к выбору одного наилучшего алгоритма.

Это обстоятельство заставляет обратиться к другим


способам		построения	смешанного алгоритма.
Пусть		в качестве	исходных чистых действий su s2 ,...
...,Sh	выступают не		стратегии поиска, а лишь отдель

ные операторы. Такими операторами могут быть, напри мер, оператор определения градиента показателя ка чества, оператор движения в том же направлении, что и ранее (стратегия «Так же»), оператор движения в обрат ном направлении (стратегия «Иначе») и т. д. Так, извест ный алгоритм наискорейшего спуска образуется комби нацией трех операторов: градиента, шага в антигради ентном направлении и оператора «Так же». Граф этого

алгоритма показан на рис. 3.4.1		(знаком « + » обозначен
оператор «Так же»).
Пусть имеется к исходных операторов			(а	не страте
гий)	Si,...,5 f t . Это означает, что	ни одно	из	S{ не явля
ется	алгоритмом поиска. Поиск образуется		определенной

комбинацией этих операторов. Переход от одного опера тора к другому имеет вероятностный характер и опреде ляется двумя стохастическими матрицами: матрицей не штрафа при AQ<0

А>=Нр«( 0 ) И,

.(3-4.4)

Рис. 3.4.1. Граф алгоритма наискорейшего спуска.

21 — 2014

ГЛАВА III

	322
где Pijw	— элемент матрицы kxk,	определяющий веро
ятность перехода от г'-го оператора		к /-му при удачном
шаге поиска (рассматривается, как		обычно, случай ми
нимизации), и матрицей штрафа при A Q ^ O
Л, =	\|\|р,-/Ч1,	(3.4.5)

которая характеризует вероятности перехода от одного оператора к другому при неудачном шаге поиска, т. е. приА<25гО.

Введя параметр штрафа на N-u шаге поиска

=	Г 0	(нештраф)	при A Q J V - I < 0 ;	(3 4 6)
C n	X 1	(штраф)	при Д<Эя-,5>0,	1 ' ' '

можно матрицу переходных вероятностей, образующую алгоритм поиска, записать в виде

A"=(\-cN)A0 + cNAl. (3.4.7)

Таким образом, смешанный алгоритм поиска представ ляется вероятностным автоматом, входом которого яв ляется параметр штрафа с, а выходом — номер / опера тора (/ = 1 , . . . , k ) .

Для анализа работы смешанных алгоритмов необхо димо замкнуть обратную связь, т. е. иметь модель объ екта и уметь оценивать эффективность работы алго ритма, т. е. располагать критерием качества алгоритма поиска.

Для моделирования объекта выберем стохастическую модель, предложенную в [1]. Эта модель обычно харак теризуется двумя вероятностями — вероятностью удач

ного случайного	шага
р = Вер ( A Q 6 < 0 )		(3.4.8)
и вероятностью	двух непосредственно	следующих друг

за другом удачных шагов в одном и том же	направлении
о = Вер ( A Q . v < 0 / A Q w _ 1 < 0 ) .	(3.4.9)

Однако в общем случае объект следует задавать веро ятностью штрафа при использовании t'-ro оператора

/г = Вер {c=l/s = S i ) .

(3.4.10)

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

323
Таким образом,вектор
L = ( / b	,lh)	(3.4.11)
полностью характеризует объект, где
h = h{p,q).		.(3.4Л2)

В качестве критерия оценки эффективности алгоритма естественно выбрать средний штраф, который хорошо характеризует целесообразность автомата поиска (3.4.7):

		N
с= Пт±	N	£ d -	( З - 4 - 1 3 )
N-юо	N

Это означает, что наилучшим алгоритмом поиска счи тается тот, средний штраф которого имеет минималь ное значение. Средний штраф определенным образом за

висит от матриц Л 0 и Ах и свойств объекта	(p,q):
c = f(A0,Ax,p,q).	(3.4.14)

Задача оптимального синтеза заключается в определе нии такого алгоритма, т. е. таких стохастических мат риц Л 0 и Ль которые минимизировали бы средний штраф для заданного объекта (р, q):

/(Л0 , Л,,р, q) -»-min.

(3.4.15)

Для решения этой задачи сначала нужно выяснить вид зависимости, т. е. определить средний штраф в функции матриц Ло и Л ь Определим предельные вероятности:

P = ( P i , . . . , p f t ) ,

(3-4.16)

где р~г — предельная вероятность пребывания автомата

	h
поиска в состоянии st (	р; = 1 ) . Для этого необхо-

димо иметь матрицу автомата поиск—объект. Эта мат рица имеет вид

В = \\Ьц\\	(3.4.17)
( i , / = l ,	...,k),

21"

ГЛАВА III

324

где

Ьц=(1-и)Рц«»+1гРцЫ.

(3.4.18)

Это означает, что переход из t'-ro состояния в /-е проис

ходит с	вероятностью нештрафа	1 — Ц по матрице А0 и
с вероятностью штрафа U — по матрице А\.
Теперь	легко определить вектор предельных вероят
ностей. Он является решением линейного уравнения
В Т Р =	Р,	(3.4.19)

где Т — знак транспонирования. Средний штраф при

этом равен скалярному	произведению
с = [Р, Ц.	(3.4.20)

Получив это выражение в аналитическом виде, нетрудно решить задачу оптимального синтеза, минимизирующего средний штраф.

Заметим, что средний штраф поиска имеет четкий фи зический смысл. Это — относительное число неудачных шагов поиска. Естественно, что чем меньше средний штраф, тем эффективнее алгоритм. Поэтому минимиза ция среднего штрафа дает возможность синтезировать оптимальные алгоритмы поиска. Конкретизируем выше изложенное на одном классе алгоритмов случайного поиска.


Большое		число алгоритмов случайного поиска образу
ется	путем	комбинации трех операторов		(k = 3):
1)	случайный шаг (оператор		sx);	s2);
2)	шаг в том же направлении		(оператор
3)	шаг в обратном направлении (оператор S3) .

а)

Рис. 3.4.2. Графы	методов случайного поиска с линейной (а)
и нелинейной (б)	тактикой.

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

325-
На рис. 3.4.2 показаны графы известных	алгоритмов
случайного поиска этого класса с линейной	(а)	и нели
нейной (б) тактикой для двух случаев удачного		(AQ<0)
и неудачного (AQl^O) шагов.

Рассмотрим следующий смешанный алгоритм с мат

рицами,	где оставлены			лишь	наиболее	существенные и
логичные переходы			(рис. 3.4.3):
	l-Pi	Pi О			\-р2	0 р2
А0 =	0	1	о	А,=	1	О	о	(3.4.21)
	1	о	о		1	о	о
Здесь для простоты введено обозначение
Р\=Р\2т;	P2 = Pi3 ( 1 ) -							(3.4.22)
Вектор	вероятностей штрафов				L=(li,l2,/3)		в этом слу
чае естественно задать в виде
L = ( l - p , \ - q , 0),								(3.4.23)