Вероятностные автоматы. 
Разработка недетерминированных программных систем на основе вероятных автоматов

Детерминированные автоматы S мы задавали совокупностью из 5 объектов: S (А, Х, Y, ,), где А={а₀, а₁, а₂,…, а_M}- множество внутренних состояний автомата, Х={х₁, х₂,…, х_F} - множество входных сигналов (входной алфавит), х_i — буква входного алфавита, Y={y₁, y₂,…, y_G} - множество выходных сигналов (выходной алфавит),.

— функция переходов, обеспечивающая однозначный переход автомата в положение а_s из состояния а_m под действием входного сигнала х_f, то есть а_s= [а_m, х_f],.

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

В работе Поспелова Д. А. «Вероятностные автоматы» рассмотрена наиболее общую модель автомата, а конкретно: зная состояние автомата а_m и входной сигнал х_f, мы не можем с вероятностью, равной 1 сказать, в каком состоянии окажется автомат в последующий момент времени, а также какой выходной сигнал он в этом случае вырабатывает. [2].

Законы распределения задаются в виде следующих таблиц (таблица 26, 27).

Таблица 26. Матрица переходов состояний.

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

Разумеется, так как автомат непременно перейдет в одно из состояний, то.

(6).

(7).

где, .

Таблица 27.

Матрица появления выходных сигналов.

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

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

Рассмотрим некие частные случаи вероятностных автоматов. Имеет возможность существовать, что выходные сигналы автомата ориентируются детерминировано, а переходы автомата — случайно. Эти автоматы именуются Y — детерминированными вероятностными автоматами. Ежели состояния определяются детерминировано, то владеем, А — детерминированный вероятностный автомат.

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

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

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

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

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

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

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

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

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

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

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

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

Рисунок 12. Схема перекрестка Матрица переходов выглядит следующим образом (таблица 28).

Таблица 28. Матрица переходов.

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

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

Таблица 29. Матрица переходов.