АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Вероятностные автоматы

Читайте также:
  1. Автоматические выключатели (Автоматы)
  2. Вероятностные методы
  3. Дифференциальные автоматы.
  4. Классификация математических моделей, исходя из особенностей их поведения: детерминированные, вероятностные, игровые модели. Иные классификации моделей.
  5. Случайные события, операции над событиями, вероятность, вероятностные пространства.
  6. Универсальные и установочные автоматы
  7. Частичные автоматы

Детерминированные автоматы S мы задавали совокупностью из пяти объектов: S (A, X, Y, d, l), где A = { a 0, a 1, a 2,..., aM } – множество внутренних состояний автомата, X = { x 1, x 2,…, xF } – множество входных сигналов (входной алфавит), xi – буква входного алфавита, Y = { y 1, y 2,…, yG } – множество выходных сигналов (выходной алфавит), y g – буква выходного алфавита,

d – функция переходов, обеспечивающая однозначный переход автомата в состояние as из состояния аm под действием входного сигнала xf, т.е. as = d [ am, xf ],

l – функция выходов, определяющая однозначное значение выходного сигнала yg в зависимости от состояния автомата аm и входного сигнала xf, т.е. yg = l [ аm, xf ].

В работе Поспелова Д.А. «Вероятностные автоматы» рассмотрена более общая модель автомата, а именно: зная состояние автомата аm и входной сигнал xf, мы не можем с вероятностью равной 1 сказать, в каком состоянии окажется автомат в следующий момент времени, а также какой выходной сигнал он в этом случае вырабатывает. Однако мы можем указать вероятности наступления соответствующего события, а именно: зная состояние аm и входной сигнал xf, мы можем указать вероятности перехода автомата в состояния { а 0, а 1, …, аm, …, аM }, а также вероятности появления выходных сигналов

{ y 1, y 2 ,…,yg, …, yG }, т.е. задаем закон распределения вероятностей. Законы распределения задаются в виде следующих таблиц:

am, xf a 0 a 1 am aM
a 0, x 1 р 010 р 011 р 01 m р 01 M
a 0, x 2 р 020 р 021 р 02 m р 02 M
am, xF р 0 F 0 р 0 F 1 р 0 Fm р 0 FM
a 1, x 1 р 110 р 111 р 11 m р 11 M
am, xf рmf 0 рmf 1 рmfm рmfM
aM, xF рMF 0 рMF 1 рMFm рMFM

 

 

am, xf y 1 y 2 yg yG
a 0, x 1 q 011 q 012 q 01 g q 01G
a 0, x 2 q 021 q 022 q 02 g q 02G
am, xF q 0 F 1 q 0 F 2 q 0 Fg q 0 FG
a 1, x 1 q 111 q 112 q 11 g q 11 G
am, xf qmf 1 qmf 2 qmfg qmfG
aM, xF qMF 1 qMF 2 qMFg qMFG

 

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

,, где,.

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

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

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

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

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

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

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

Рис. 15.1

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

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

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

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

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

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

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

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

Рис. 15.2

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

 

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

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

 

Вопросы к лекции 15:

1.Какие автоматы называются вероятностными?

2. Какие автоматы называют детерминированными вероятностными автоматами?

3. Назовите особенность вероятностного автомата компенсирующего типа?

4. Объяснить принцип «штраф» и «не штраф»?

5. Какие автоматы называются ВА с переменной структурой?

6. Что мы можем указать в вероятностных автоматах зная состояние автомата аm и входной сигнал xf?

7. Возможен ли принцип изменения вероятностей, при котором происходит учет предыстории поведения автомата?

8. Назовите возможность применения ВА компенсирующего типа в реальной жизненной ситуации?

ЛЕКЦИЯ 16 Микропрограммные автоматы

 

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.007 сек.)