ПОВЕДЕНИЕ АВТОМАТОВ В СЛУЧАЙНЫХ СРЕДАХ.

Исследование поведения конечных и стохастических автоматов в случайных средах как самостоятельный раздел теоретической кибернетики получило широкое развитие лишь в начале 60-х гг. 20 ст., начиная с работ сов. математика М. Л. Цетлина (1924—66). Он ввел осн. понятия, сформулировал и решил ряд задач для случая стационарных и составных (состоящих из стационарных) сред при дискретном времени. В качестве иллюстрации был предложен автомат с линейной тактикой, обладающий при определенных условиях асимптотически оптим. поведением в стационарной среде и оптим. емкостью памяти в составной.

Впоследствии другие исследователи предложили конструкции асимптотически оптим. автоматов и изучали различные их свойства. В начальный период развития этого направления появились работы, посвященные исследованию поведения в случайных средах автоматов с переменной структурой и обучению автоматов. Имеются работы и для случая непрерывного времени. Значительное к-во результатов дал подход, использующий аппарат теории восстановления и теории полумарковских случайных процессов. Были исследованы автоматы со случайным временем реакции. Применение новых теоретико-вероятностных результатов оказалось плодотворным и для случая составных сред. В подавляющем большинстве работ рассматриваются двухвходовые автоматы. Имеются результаты исследования оптим. поведения в стационарных случайных средах автоматов со многими входами.

Особенно интенсивно исследуется коллективное П. а. в с. с. Стохастический автомат А определяют как систему, имеющую конечное число входов и конечное число внутр. состояний Число считают емкостью (объемом) памяти автомата. Для каждого значения входной переменной s задана своя матрица переходов состояний автомата

Следует заметить, что автомат с линейной тактикой и его обобщение на случай К действий к, обладает асимптотически оптим. поведением лишь в тех средах, где , т. е. имеется возможность получить неотрицательный средний выигрыш хотя бы за одно какое-либо действие. Были предложены и исследованы также стохастические автоматы, не имеющие этого свойства. Кроме того, А имеет выходную переменную, которая может принимать значений , однозначно определяемых состоянием. Обозначив через соответственно состояние автомата, значение его входной в выходной переменных в момент можно полностью определить функционирование стохастического автомата соотношениями

Считают, что входная переменная s может принимать лишь два зцачения: которые рассматривают соответственно как нештраф и штраф.

Под функционированием А в случайной среде понимают следующее: если в момент t автомат находится в состоянии которому соответствует действие то в момент на вход автомата поступит штраф с вероятностью и нештраф с вероятностью Среда именуется стационарной, если ее

вероятностные характеристики не меняются во времени.

Нетрудно показать, что функционирование стохастического автомата в стационарной случайной среде описывается конечной однородной Маркова цепью. Естественно предположить у этой цепи наличие предельных вероятностей состояний: Для вычисления математического ожидания штрафа автомата А в среде С используют где таково

Графы состояний автомата

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

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

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

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

При исследовании П. а. в с. с. непрерывность во времени можно рассматривать по-разному. Назовем автоматом со случайным временем реакции такой стохастический автомат, для которого время пребывания в состоянии является некоторой положительной случайной величиной с произвольной ф-цией распределения Функционирование такого автомата в случайной среде описывается некоторым полумарковским процессом. Можно рассматривать автоматы, у которых время реакции зависит только от входного сигнала или от предыдущего состояния и т. д. Используя наличие у Полумарковских процессов стационарного распределения и применяя метод стохастических уравнений, можно успешно решать задачи о среднем штрафе, выплачиваемом за время t, о времени пребывания автомата в некотором подмножестве его состояний и другие. Наличие у таких автоматов новых параметров средних времен реакции — открывает новые возможности для решения задач оптимизации.

Отдельно рассмотрим задачу о поведении стохастических автоматов в составных случайных средах при дискретном времени. Составной наз. среда , состоящая из нескольких стационарных случайных сред переключение которых осуществляется цепью Маркова Д с v состояниями. В простейшем случае где Автомат А функционирует в простейшей составной среде К, если в каждый дискретный момент времени он функционирует в среде или том смысле, как говорилось выше). При этом, если в момент t автомат находится в среде то в момент он будет с вероятностью функционировать в той же среде в с вероятностью в другой. В этом случае

Здесь — предельные вероятности марковской цепи, описывающей поведение автомата в стационарной среде вероятностные параметры среды . Аналогично для среды . В простейшем случае (среды и симметричные) для автомата дсказано. что величина достигает своего

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

Лит.: Цетлин М. Л. Исследования по теории автоматов и моделированию биологических систем. М., 1969 [библиогр. с. 306—316]. В. Я. Валах.