Analysis of expedient behavior of various types of automata

Full Text

Введение

Организация сложного поведения децентрализованных систем, построенных на базе простых элементов, находит свое отражение в таком разделе машинного обучения, как «Коллективное поведение автоматов» [1]. При этом связь между нейросетевым и автоматным подходами бывает очень тесной [2].

Анализ поведения автоматов будет проводиться при помощи аппарата теории игр. Такой выбор определяется тем, что теория игр позволяет легко создавать формализуемые системы правил и стратегий поведения, определяющие характер взаимодействия отдельного автомата (или совокупности автоматов) и окружающей среды [3].

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

Первые интересные модели такого типа были созданы М. Л. Цетлиным (1924–1966) [4]. Он выступил создателем целого направления исследований, получившего название «коллективное поведение автоматов» [5–7]. Им были сформулированы основные принципы, лежащие в основе подобных моделей, и способы их реализации.

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

Основные положения этого подхода состоят в следующем:

• принцип суперпозиции;
• принцип соизмеримости;
• принцип универсальности структуры автомата.

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

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

Левая граница – это значение математического ожидания количества штрафов и поощрений, полученных системой, реализующей стратегию случайного выбора доступных в данной среде действий из множества D=d₁,..., d_m, m ≥2.

Правая граница – это величина математического ожидания штрафов и поощрений, полученных системой, которая в любой момент времени t, t>>1 всегда реализует заведомо оптимальное в данной среде действие d_i= d*, i=1, …, m.

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

Принцип универсальности. Конструкция анализируемой системы не должна содержать эмпирических данных об оптимальных (или неоптимальных) действиях в данной среде, т. е. такие действия система выявляет в процессе своего функционирования в течение некоторого заданного времени t. Первая автоматная реализация таких систем была предложена М. Л. Цетлиным.

Автоматная реализация

Приведем формальное описание автомата:

X = x₁, …, x_k – множество входных сигналов, поступающих от окружающей среды на вход автомата (входной алфавит).

D = d₁, …, d_m – конечное множество доступных автомату действий (выходной алфавит).

S = s₁,…,s_n, 2 <= m <= n – конечное множество внутренних состояний автомата (внутренний алфавит).

Правила функционирования автомата в дискретные моменты времени t однозначным образом задаются двумя функциями:

функцией переходов внутренних состояний s_t+1 = F(s_t, x_t) и начальным внутренним состоянием в нулевой момент времени t = t₀: s₀ = S(t₀);

функцией зависимости выходных сигналов (действий) от внутренних состояний dt = G(s_t).

Общая постановка задачи

Пусть задана некоторая среда E, в которой будут функционировать типы исследуемых автоматов.

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

Требуется:

• определить степень влияния глубины памяти q каждого из рассматриваемых типов автоматов на изменение степени целесообразности поведения в указанной среде E;
• на основе полученных результатов определить тип конструкции автомата, достигающей заданного уровня целесообразности с минимально возможной глубиной памяти q = q*;
• в случае наличия нескольких эквивалентных конструкций указать наиболее простую в реализации конструкцию.

Биологические предпосылки

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

Подопытное животное помещалось в основание Т-образного лабиринта с возможностью выбора одного из двух действий:

«Повернуть влево»;

«Повернуть вправо».

По условиям эксперимента в конце каждого из двух ответвлений реализовывались неизвестные подопытному животному благоприятные (или неблагоприятные) условия с независимыми вероятностями для каждого из ответвлений.

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

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

Стационарная окружающая среда

Стационарная окружающая среда E является математическим описанием условий Т-образного лабиринта.

В Т-образном лабиринте было всего два доступных для выполнения действия: «повернуть влево» и «повернуть вправо». В каждом из выбранных ответвлений ожидалась своя вероятность поощрения Pl и Pr.

Обобщением этой ситуации является стационарная среда с m исходами (действиями).

Для каждого из m действий задается совокупность значений вероятностей: либо поощрения p_i, либо штрафа 1 – p_i, i=1, …, m.

Выбор оптимального действия в такой среде сводится к определению действия с максимальной вероятностью поощрения (минимальной вероятностью штрафа).

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

Типы конструкций автоматов

Первой конструкцией автомата, способного вести себя целесообразно в описанной выше стационарной среде E, является автомат с линейной тактикой, предложенный М. Л. Цетлиным.

Автомат L1 (с глубиной памяти q=1) состоит из m состояний S=s₁,.., s_m.

За каждым из m состояний s_i закреплено действие d_i, i=1, …, m.

Автомат L1 функционирует следующим образом:

В некоторый момент времени t=t*, находясь в состоянии s_i, автомат L1 выполняет выходное действие d_i, i=1, …, m.

В ответ на это действие окружающая среда и формирует сигнал, принимающий значение «поощрение» в соответствии с вероятностью p_i и «штраф» с вероятностью 1 – p_i.

Этот сигнал подается на вход автомата l1.

Если автомат L1 на входе получает сигнал «штраф», то он переходит в состояние s_i+1 и, следовательно, переключает внешнее действие с d_i на d_i+1.

При получении сигнала «поощрение» автомат L1 остается в исходном состоянии s_i, при этом смена действия не происходит.

Таким образом, в следующий момент времени t*+1 автомат L1 выполнит действие в соответствии со своим внутренним состоянием, и процесс взаимодействия автомата со средой повторится описанным выше образом.

Закрепляя за каждым из m действий di q последовательных состояний, мы получим последовательность линейных автоматов с монотонно возрастающей глубиной памяти q.

М. Л. Цетлину удалось показать, что последовательность таких автоматов L1, L2, …, Lq, функционирующих в стационарной среде E, является асимптотически оптимальной, т.е. чем больше глубина памяти линейного автомата Lq, тем дольше такой автомат выполняет самое оптимальное действие (с максимальной вероятностью поощрения) и почти никогда не покидает связанные с ним состояния.

Усложнением автомата с линейной тактикой является автомат Кринского.

Он характеризуется тем, что при получении поощрения этот автомат всегда переходит в самое глубокое состояние, соответствующее текущему (выполненному им) действию.

При получении штрафа от окружающей среды этот автомат реагирует точно так же, как и автомат с линейной тактикой, понижая на единицу номер состояния текущего (выполненного) действия.

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

Следующим по степени усиления свойства инерционности является автомат Роббинса.

Он отличается от автомата Кринского тем, что в отличие от него при смене действия автомат Роббинса сразу переходит в самое глубокое состояние, соответствующее новому действию.

В остальном он ничем не отличается от автомата Кринского.

Для него также верна теорема об асимптотической оптимальности в стационарных средах.

Заметим, что у трех автоматов – автомата с линейной тактикой, автомата Кринского и автомата Роббинса – при глубине памяти q = 1 алгоритмы функционирования полностью совпадают, утрачивая отличия между ними.

Несколько другой подход к усилению инерционности применен в конструкции автомата Крылова.

Он сочетает в себе элементы поведения как детерминированного, так и стохастического автомата.

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

При получении штрафа автомат Крылова «подбрасывает монетку».

При выпадении «орла» автомат не меняет своего состояния, а при выпадении «решки» уменьшает номер состояния за действие, за которое от среды получен штраф.

Этот автомат также является асимптотически оптимальным в условиях стационарных сред.

Динамические среды

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

Действия автомата из множества D взаимно однозначно соотносятся со стратегиями, доступными игроку в соответствующей (заданной) игре с конечным числом стратегий.

Например, действия автомата в уже рассмотренной выше стационарной среде E на языке теории игр формулируется как игра с природой:

• задана одностолбцовая платежная матрица с m неотрицательными значениями;
• элементы матрицы игры нормируются относительно максимального значения платежа и рассматриваются как вероятности поощрений от стационарной среды E;
• значение поощрения равно единице, значение штрафа равно нулю;
• действиям автомата (игрок 1) соответствуют номера строк заданной матрицы;
• природа (игрок 2) выбрала свою стратегию (столбец) и не меняет ее в течение всех партий игры;
• целью игры является максимизация выигрыша автомата.

Игрок 1 (автомат) в каждый момент времени t разыгрывает партию игры с природой и в зависимости от выбранного действия d*=d_i и соответствующей этому действию вероятности p*=p_i получает сигнал поощрения (или штрафа) от окружающей среды I, i=1, …, m.

Поскольку оптимальная стратегия игры с природой известна и соответствует выбору игроком действия с максимальной ценой p_i=p_max, то создается возможность сравнить эффективность действия осведомленного игрока, которому известна вся платежная матрица, с действиями автомата, которому не известно содержимое этой матрицы.

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

Игры двух автоматов

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

В этом случае действиям первого автомата сопоставляются номера строк, а действиям второго автомата – номера столбцов платежной матрицы.

Если первый автомат с вероятностью p получает поощрение, то второй автомат получает штраф, и наоборот, реализуя принцип антагонистической игры с нулевой суммой.

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

Если игра допускает решение в чистых стратегиях, то автоматы реализуют друг для друга стационарную среду, для которой повышение целесообразности связано с ростом глубины памяти q.

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

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

Игра в размещения

Примером того, как коллектив автоматов формирует динамическую среду для отдельного автомата, является игра в размещения.

Биологической предпосылкой для игры в размещения служит следующая задача:

• имеется конечное число участков с различной степенью производительности пищи. На этих участках некоторым образом размещаются животные;
• если два и более животных в текущий момент времени оказываются на одном участке, то производительность пищи участка делится поровну между этими животными.

Задача животного состоит в максимизации количества добываемой им пищи.

Описание игры в размещения легко формулируется на языке теории игр следующим образом:

• пусть задано m стратегий d = d₁, …, d_m. Значение каждой стратегии равно математическому ожиданию события «поощрение / штраф» в случае ее выбора;
• в рамках заданных стратегий функционируют n автоматов: n < m. Выигрыш от стратегии d_i, i=1, …, m, в любой момент времени t поровну делится между всеми выбравшими эту стратегию автоматами;
• требуется найти условия, обеспечивающие максимальный выигрыш для всей совокупности автоматов.

Эти условия делятся на три основные группы:

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

Мы будем анализировать рассмотренные выше типы автоматов: автомат с линейной тактикой, автомат Кринского, автомат Роббинса и автомат Крылова.

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

Взаимодействие автоматов варьируется от полной изолированности автоматов друг от друга до введения внешней по отношению к структуре автоматов процедуры общей кассы.

Оценка скорости переключения

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

Требуется определить необходимый интервал времени функционирования автомата для сбора достоверной статистики.

Утверждение 1. Средняя скорость переключения между действиями одного из изолированных автоматов в игре в размещения не ниже значения этой скорости автомата, функционирующего в соответствующей стационарной среде.

Действительно, если у автомата при выборе текущего действия d* = d_i, i = 1, …, m в текущей партии отсутствуют соседи, то его новое состояние будет обусловлено только значением отклика окружающей среды на выбор данного действия в соответствии с вероятностью получения поощрения p* = p_i. В этом случае его скорость смены действий будет совпадать со скоростью автомата в соответствующей стационарной среде E.

Если при выборе данной стратегии d* = d_i у рассматриваемого автомата имеются соседи (один или более одного) на i-й площадке, то текущая ситуация распадается на два случая.

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

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

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

Теперь рассмотрим фактор влияния процедуры общей кассы.

Утверждение 2. Средняя скорость переключения n автоматов в наилучшем размещении не ниже скорости переключения между действиями одним автоматом, выполняющим наилучшее действие в соответствующей стационарной среде E.

Действительно, наличие процедуры общей кассы приводит к тому, что вся совокупность полученных от окружающей среды поощрений в любой партии делится в равных долях между всеми n автоматами.

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

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

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

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

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

Поочередно вычеркивая из списка наилучшую площадку, мы можем провести данное доказательство для всех m площадок.

Проведение вычислительного эксперимента

Для проведения игры в размещения задано 10 площадок. В качестве доступных для автоматов действий.

Величина поощрения равна (+1), величина штрафа (–1).

Эти величины определяют следующие значения вероятностей получения поощрений:

 

Таблица 1. Платежная матрица

Table 1. Payoff matrix

Цена	0,0	0,1	0,2	0,3	0,4	0,5	0,6	0,7	0,8	0,9
Поощрения	0,50	0,55	0,60	0,65	0,70	0,75	0,80	0,85	0,90	0,95

 

Для каждого типа автомата была проведена серия из 10 независимых экспериментов, после чего полученные данные усреднялись.

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

Обозначим типы автоматов следующим образом:

автомат с линейной тактикой – АЛТ;

автомат Кринского – АКРН;

автомат Роббинса – АРББ;

автомат Крылова – АКРЛ.

 

Таблица 2. Математические ожидания поощрений и штрафов

Table 2. Mathematical expectations of rewards and penalties

Автомат	Память 1	Память 2	Память 3	Память 4	Память 5	Память 6	Память 7	Память 8
АЛТ	0,63679	0,76809	0,80862	0,87499	0,88372	0,88475	0,79856	0,88803
АКРН	0,63679	0,76809	0,80474	0,87788	0,87707	0,88170	0,88255	0,87800
АРББ	0,63679	0,75081	0,80495	0,87277	0,87602	0,89240	0,89255	0,89688
АКРЛ	0,630618	0,760276	0,848816	0,884885	0,886225	0,89742	0,89549	–

 

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

При этом общая тенденция увеличения эффективности функционирования автомата с ростом глубины памяти q сохраняется.

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

 

Таблица 3. Среднее время работы автомата

Table 3. Average machine operating time

Автомат	Память 1	Память 2	Память 3	Память 4	Память 5	Память 6	Память 7	Память 8
АЛТ	74	695	3761	251394	3648854	19393688	927170104	22414244336
АКРН	74	695	4527	264297	3795658	–	48562927	927170104
АРББ	74	759	5179	264297	3795658	53461387	1029193271	26407904074
АКРЛ	116	2152	50814	2426164	89700530	3627473535	126294097025	–

 

Таким образом, мы видим две автоматные стратегии оптимизации поведения:

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

Заключение

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

About the authors

D. P. Dimitrichenko

Kabardino-Balkarian Scientific Center of the Russian Academy of Sciences

Author for correspondence.
Email: dimdp@rambler.ru
ORCID iD: 0000-0003-2399-3538
SPIN-code: 3272-3520

Institute of Applied Mathematics and Automation

Russian Federation, 360000, Nalchik, 89 A Shortanov street

References

Supplementary files