Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов.

Исследование поведения автоматов в стационарной случайной среде. Целесообразные автоматы.

Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов.

Конечный автомат – объект, имеющий конечное число внутренних состояний (состояний памяти) Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru ( Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru ), конечное число входных сигналов Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru ( Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru ) и конечное число выходных сигналов Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru ( Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru ). Предполагается, что автоматы функционируют в дискретном времени, т.е. время принимает целочисленные значения.

Автомат зададим каноническими уравнениями:

Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru , (1)
Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru , (2)

где уравнение (1) определяет смену внутренних состояний под воздействием входной величины, а уравнение (2) – зависимость выходного сигнала от внутреннего состояния автомата.

Функция перехода автомата может быть задана либо системой матриц Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru , которые определяют смену состояний автомата ( Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru ) ( Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru ) под воздействием сигнала Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru ( Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru ), либо ориентированными графами состояний.

Автоматы могут быть детерминированными или стохастическими. Для детерминированных автоматов матрицы Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru являются простыми, т.е. каждая их строка содержит только один элемент равный единице, а остальные элементы строки равны нулю. Для стохастических автоматов матрицы Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru - стохастические ( Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru , Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru ). Каждый элемент Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru матрицы определяет вероятность перехода автомата из состояния Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru в состояние Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru под воздействием входного сигнала Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru .

Рассмотрим поведение автомата во внешней среде С. Это означает, что выходные сигналы автомата Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru ( Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru ) являются входными сигналами для некоторого устройства C, которое реагирует на них сигналами являющимися входными для автомата. Выходные сигналы Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru называют действиями, а входные сигналы Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru - реакцией среды С. Будем считать, что реакции среды С, воспринимаемые автоматом, делятся на два класса: класс благоприятных реакций Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru = +1 (выигрыш, поощрение, вознаграждение) и класс неблагоприятных реакций Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru = -1 (проигрыш, штраф).

Рассмотрим простейшую задачу о поведении автомата в стационарной случайной среде С( Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru ), где Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru постоянны и не зависят от времени. Автомат A функционирует в случайной среде С ( Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru ), если действие автомата Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru ( Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru ), произведенное автоматом в момент времени t, влечёт за собой в момент времени t+1 значение Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru = -1 (штраф) с вероятностью Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru и значение Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru = +1 (поощрение) с вероятностью Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru .

Поведение системы “автомат – случайная стационарная среда” описывается дискретной цепью Маркова. В том случае, когда конструкция автомата (набор матриц Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru и Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru ) такова, что цепь Маркова эргодична, существуют финальные вероятности состояний, не зависящие от начального состояния.

Обозначим через Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru финальную вероятность состояния Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru автомата в среде C и через Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru ( Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru ) финальную вероятность действия Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru . Математическое ожидание выигрыша Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru автомата А в среде С определяется формулой

Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru .

Очевидно, что

Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru .

Если автомат выбирает свои действия независимо от реакций среды и равновероятно, то математическое ожидание его выигрыша

Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru .

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

Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru .

Задача построения автомата, обладающего целесообразным поведением в данной среде С, тривиальна, т.к. её решением является автомат с одним внутренним состоянием, в котором он выполняет то действие, за которое в данной среде полается минимальный штраф. Такой автомат обладает “априорной целесообразностью”, т.е. целесообразность его поведения основывается на априорном знании параметров случайной среды.

В дальнейшем нас будут интересовать автоматы, которые “априорной целесообразностью” не обладают, т.е. симметрические автоматы случайных сред, получаемых из сред С ( Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru ), всеми возможными перестановками параметров Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru . В этом случае, функция Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru является симметрической функцией параметров Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru .

Нас будут интересовать конструкции автоматов, для которых Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru приближается к Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru . Введём следующее определение:

Последовательность автоматов Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru называется асимптотически - оптимальной, если

Понятие о конечном автомате. Целесообразные автоматы. Асимптотически-оптимальная последовательность автоматов. - student2.ru .

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

Наши рекомендации