Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов.
Исследование поведения автоматов в стационарной случайной среде. Целесообразные автоматы.
Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов.
Конечный автомат – объект, имеющий конечное число внутренних состояний (состояний памяти) (
), конечное число входных сигналов
(
) и конечное число выходных сигналов
(
). Предполагается, что автоматы функционируют в дискретном времени, т.е. время принимает целочисленные значения.
Автомат зададим каноническими уравнениями:
![]() | (1) |
![]() | (2) |
где уравнение (1) определяет смену внутренних состояний под воздействием входной величины, а уравнение (2) – зависимость выходного сигнала от внутреннего состояния автомата.
Функция перехода автомата может быть задана либо системой матриц , которые определяют смену состояний автомата (
) (
) под воздействием сигнала
(
), либо ориентированными графами состояний.
Автоматы могут быть детерминированными или стохастическими. Для детерминированных автоматов матрицы являются простыми, т.е. каждая их строка содержит только один элемент равный единице, а остальные элементы строки равны нулю. Для стохастических автоматов матрицы
- стохастические (
,
). Каждый элемент
матрицы определяет вероятность перехода автомата из состояния
в состояние
под воздействием входного сигнала
.
Рассмотрим поведение автомата во внешней среде С. Это означает, что выходные сигналы автомата (
) являются входными сигналами для некоторого устройства C, которое реагирует на них сигналами являющимися входными для автомата. Выходные сигналы
называют действиями, а входные сигналы
- реакцией среды С. Будем считать, что реакции среды С, воспринимаемые автоматом, делятся на два класса: класс благоприятных реакций
= +1 (выигрыш, поощрение, вознаграждение) и класс неблагоприятных реакций
= -1 (проигрыш, штраф).
Рассмотрим простейшую задачу о поведении автомата в стационарной случайной среде С( ), где
постоянны и не зависят от времени. Автомат A функционирует в случайной среде С (
), если действие автомата
(
), произведенное автоматом в момент времени t, влечёт за собой в момент времени t+1 значение
= -1 (штраф) с вероятностью
и значение
= +1 (поощрение) с вероятностью
.
Поведение системы “автомат – случайная стационарная среда” описывается дискретной цепью Маркова. В том случае, когда конструкция автомата (набор матриц и
) такова, что цепь Маркова эргодична, существуют финальные вероятности состояний, не зависящие от начального состояния.
Обозначим через финальную вероятность состояния
автомата в среде C и через
(
) финальную вероятность действия
. Математическое ожидание выигрыша
автомата А в среде С определяется формулой
.
Очевидно, что
.
Если автомат выбирает свои действия независимо от реакций среды и равновероятно, то математическое ожидание его выигрыша
.
Говорят, что автомат А обладает целесообразным поведением в стационарной случайной среде С, если
.
Задача построения автомата, обладающего целесообразным поведением в данной среде С, тривиальна, т.к. её решением является автомат с одним внутренним состоянием, в котором он выполняет то действие, за которое в данной среде полается минимальный штраф. Такой автомат обладает “априорной целесообразностью”, т.е. целесообразность его поведения основывается на априорном знании параметров случайной среды.
В дальнейшем нас будут интересовать автоматы, которые “априорной целесообразностью” не обладают, т.е. симметрические автоматы случайных сред, получаемых из сред С ( ), всеми возможными перестановками параметров
. В этом случае, функция
является симметрической функцией параметров
.
Нас будут интересовать конструкции автоматов, для которых приближается к
. Введём следующее определение:
Последовательность автоматов называется асимптотически - оптимальной, если
.
Автомат, принадлежащий асимптотически-оптимальной последовательности, при достаточной величине номера m производит почти всегда то действие, при котором вероятность выигрыша максимальна. В качестве номера автомата в последовательности мы будем использовать число состояний памяти, называя его емкостью (глубиной) памяти.