Основные понятия. Раздел 6. Лекция 15. Вероятностные автоматы

Раздел 6. Лекция 15. Вероятностные автоматы

Детерминированные автоматы S мы задавали совокупностью из пяти объектов: S(A, X, Y, d, l), где A = { a ₀, a ₁, a ₂,..., a _M}– множество внутренних состояний автомата, X = { x ₁, x ₂,…, x_F } – множество входных сигналов (входной алфавит), x _i– буква входного алфавита, Y = {y₁, y₂,…, y_G} – множество выходных сигналов (выходной алфавит),

d - функция переходов, обеспечивающая однозначный переход автомата в состояние a_s из состояния а_m под действием входного сигнала x_f, то есть a_s = d [ a_m, x_f ],

l - функция выходов, определяющая однозначное значение выходного сигнала y_g в зависимости от состояния автомата а_m и входного сигнала x_f, т.е. y_g = l [ а_m, x_f ].

В работе Поспелова Д.А. «Вероятностные автоматы» рассмотрена более общую модель автомата, а именно: зная состояние автомата а_m и входной сигнал x_f, мы не можем с вероятностью, равной 1 сказать, в каком состоянии окажется автомат в следующий момент времени, а также какой выходной сигнал он в этом случае вырабатывает. Однако мы можем указать вероятности наступления соответствующего события, а именно: зная состояние а_m и входной сигнал x_f, мы можем указать вероятности перехода автомата в состояния { а₀, а₁, …, а_m, …, а_M }, а также вероятности появления выходных сигналов {y₁, y₂,…,y_g, …, y_G}, т.е. задаем закон распределения вероятностей. Законы распределения задаются в виде следующих таблиц:

a_m,x_f	a₀	a₁	…	a_m	…	a_M
a₀,x₁	P₀₁₀	P₀₁₁	…	P_01m	…	P_01M
a₀,x₂	P₀₂₀	P₀₂₁	…	P_02m	…	P_02M
…	…	…	…	…	…	…
a_m,x_F	P_0F0	P_0F1	…	P_0Fm	…	P_0FM
a₁,x₁	P₁₁₀	P₁₁₁	…	P_11m	…	P_11M
…	…	…	…	…	…	…
a_m,x_f	P_mf0	P_mf1	…	P_mfm	…	P_mfM
…	…	…	…	…	…	…
a_M,x_F	P_MF0	P_MF1	…	P_MFm	…	P_MFM

a_m,x_f	y₁	y₂	…	y_y	…	a_M
a₀,x₁	q₀₁₁	q₀₁₂	…	q_01y	…	q_01G
a₀,x₂	q₀₂₁	q₀₂₂	…	q_02y	…	q_02G
…	…	…	…	…	…	…
a_m,x_F	q_0F1	q_0F2	…	q_0Fy	…	q_0FG
a₁,x₁	q₁₁₁	q₁₁₂	…	q_11y	…	q_11G
…	…	…	…	…	…	…
a_m,x_f	q_mf1	q_mf2	…	q_mfy	…	q_mfG
…	…	…	…	…	…	…
a_M,x_F	q_MF1	q_MF2	…	q_MFy	…	q_MFG

Т.е. в каждом случае имеем закон распределения, заданный в виде гистограмм.

Очевидно, т.к. автомат обязательно перейдет в одно из состояний, то

, ,

где , .

Автоматы, в которых зная состояние автомата а_m и входной сигнал x_f, мы можем указать лишь вероятности перехода в новое состояние и вероятности появления выходных сигналов, т.е. законы распределения, называются вероятностными автоматами (ВА).

По аналогии с детерминированными автоматами, Можно определить ВА Мили и Мура. ВА, у которых вероятности появления выходных сигналов (закон распределения) зависят лишь от состояний автомата, но не зависят от входных сигналов, называются ВА Мура. Если же вероятности появления выходных сигналов (закон распределения) зависят как от состояний автомата, так и от входных сигналов, имеем автомат Мили.

Рассмотрим некоторые частные случаи вероятностных автоматов. Может быть, что выходные сигналы автомата определяются детерминировано, а переходы автомата – случайно. Такие автоматы называются Y – детерминированными вероятностными автоматами. Если состояния определяются детерминировано, то имеем А- детерминированный вероятностный автомат.

Если в процессе функционирования автомата законы распределения вероятностей появления выходных сигналов и вероятности перехода автомата в новые состояния не меняются во времени, то такие ВА называются ВА с постоянной структурой.

Очевидно, можно рассмотреть общий случай, когда эти законы распределения зависят от времени. Такие автоматы называются ВА с переменной структурой.

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

Часто при построении ВА изменение вероятностей производят по некоторому закону, причем закон зависит от истории функционирования автомата (т.е. зависит от входных сигналов, поданных на него и от выходных сигналов, т.е. реакции автомата). Такие ВА с переменной структурой называются автоматами компенсирующего типа. Их разработке и уделяется основное внимание.

В этом случае можно сказать, что ВА работает в некоторой среде, в которую он выдает выходные сигналы и из которой он получает входные.

Входные сигналы условно можно разделить на поощрения («нештрафы») и наказания («штрафы»). При этом в зависимости от выходного сигнала на вход подается поощрение или штраф. Если в зависимости от этих сигналов менять вероятности перехода автомата из одного состояния в другое, то оказывается, что с течением времени автомат перестраивается таким образом, что он начинает с большой вероятностью получать сигналы поощрения, т.е. он в некотором смысле приспосабливается к той среде, в которой он находится.

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

Рассмотрим У-детерминированный вероятностный автомат. Пусть автомат в некоторый момент времени t находится в состоянии а_m, выдал соответствующий этому состоянию выходной сигнал y_g и получилна вход сигнал поощрения. Тогда вероятность р _mm перехода из состоянии а_m в состояние а_m увеличиваются на некоторую величину , а все остальные вероятности в строке уменьшаются на /М. Если же автомат получает сигнал штрафа, то вероятность р _mm перехода из состоянии а_m в состояние а_m уменьшаются на некоторую величину , а все остальные вероятности в строке на увеличиваются на/М, чтобы сумма вероятностей осталась равной 1.

Возможен и другой принцип изменения вероятностей, при котором происходит учет предыстории поведения автомата. Если автомат в момент времени t перешел из состояния а_m в состояние а_к и в момент времени t +1 получил сигнал «штраф», то вероятность р _m_к заменяется на р _m_к, где коэффициентбольше 0 и меньше 1, а все остальные вероятности в строке изменяются на величину . Если же получил сигнал «нештраф», то вероятность р _m_к величину , а все остальные уменьшаются на величину .

Можно менять вероятности в матрице перехода не только по строкам, но и по столбцам. Например, возможен следующий алгоритм. Если в момент времени t под влиянием входного сигнала x_f автомат перешел в состояние а_m и в момент времени t +1 получил сигнал «штраф», то независимо от того, из какого состояния он перешел, все элементы m-го столбца в матрице переходов заменяются на (р _mm – ) или р _mm, а все остальные вероятности изменяются аналогично тому, как это происходило при изменении вероятностей по строкам.

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

Рассмотрим пример, который приводит Д.А. Поспелов – регулирование движения через автомобильный перекресток. Обычно (мы с вами всегда сталкиваемся именно с таким светофором) задают жесткий режим переключения светофоров, при котором длительность включенных сигналов (красного и зеленого) – постоянны. Однако, как показывает практика работы таких светофоров, решение задачи получается мало эффективным, поскольку предполагается, что потоки машин постоянные, стационарные.

Можно установить датчики на перекрестке, которые бы подсчитывали число машин (очередь), возникающее в данном направлении при красном свете светофора. Пусть на перекрестке стоит ВА компенсирующего типа, который имеет 2 состояния: включен красный свет вдоль главного направления и включен зеленый свет. Каждому состоянию однозначно соответствует выходной сигнал, т.е. автомат У-детерминированный. С датчиков поступают сигналы штрафа и нештрафа.

Матрица переходов выглядит следующим образом: .

Пусть в начале все эти вероятности равны 0,5 и на главном направлении скопилось П₁ машин, а на другом – П₂. На вход автомата поступает сигнал = П₁ – П₂. Пусть > 0, т.е. на главном направлении больше машин. Тогда если автомат в момент времени t находился в состоянии зеленом, перешел в состояние зеленый и получил сигнал нештраф, то вероятность р_зз(t +1) увеличивается, а вероятность р_зк(t +1) уменьшается: р_зк(t +1) = р_зк(t),

а вероятность р_зз(t +1) = 1– р_зк(t +1).

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

Проектирование – это многоплановый процесс, начинающийся с общего замысла о предмете проектирования и заканчивающийся подробным его описанием. Чем полнее и понятнее выполнено описание, тем быстрее и качественней реализация предмета проектирования. Известно два приема при описании предмета проектирования:

· Оформление чертежей, схем и диаграмм;

· Составление спецификаций в виде пояснительной записки.

Предметная область – сегмент реального мира, выделенный и описанный в соответствии с поставленными целями и задачами проектируемой ИС (системотехника как научное направление, охватывающее проектирование, создание и эксплуатацию сложных систем).

Методы обследования – системный анализ, структурный или объектный анализ и другие общенаучные методы.

Предмет проектирования – система, предназначенная для хранения и обработки информации или ИС.

Методология проектирования – метод и технология проектирования, основанная на стандартах.

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

Проектирование ИС предполагает: