Лекция
Привет, Вы узнаете о том , что такое простейший автомат, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое простейший автомат, детерминированный автомат, вероятностный автомат , настоятельно рекомендую прочитать все из категории Теория конечных автоматов.
Предположим, что существует несколько логических переменных u1…ur, и будем рассматривать их как вектор U. Пусть f – логическая функция от этих переменных, образующая некое сложное логическое высказывание
q=f(U)
Будем рассматривать q как выходную величину РКС, реализующую логическую функцию f.
РКС, встречающиеся на практике, как правило, имеют не один выход а несколько, и каждый выход реализует свою логическую функцию.
Будем считать, что РКС осуществляет логические операции мгновенно, т.е. если в момент времени t на вход схемы поступает вектор U, то соответствующее значение q=f(u) получится на выходе в тот же самый момент времени. Для описания работы РКС во времени удобно ввести понятие дискретного времени. Т.е. физическое понятие бесконечно, равномерно, и непрерывно текущего времени мы заменим точечными моментами времени, считая, что все изменения происходят именно в эти моменты, и между ними не происходит никаких изменений. Более того, считаем, что длина этих промежутков настолько мала, что этим значением можно пренебречь. На оси t отметим моменты, в которые входная величина может претерпеть измененияt1, t2, …, tn. Эти величины называютсятактами. Уравнения q[n]=f(u(n)], где n –n-тый такт, описывает работу РКС во времени. РКС является простейшим видом конечных автоматов –конечный автомат без памяти.
Конечные автоматы принято задавать не уравнениями, а таблицами переходов и выходов или графом переходов конечного автомата. В таблице переходов строки соответствуют различным входным сигналам, а столбцы – различным состояниям автомата. На пересечении строки и столбца указывается состояние, в которое переходит автомат.
Другим способом задания конечного автомата, обеспечивающим большую наглядность, является задание автомата с помощью направленного графа. Вершины графа – это возможные состояния автомата. Вершины i,k соединяются дугами тогда и только тогда, когда существует сигнал, переводящий автомат из состояния i в состояние k, при этом дуга помечается значением сигнала U и в скобках указывается значение выходного сигнала q.
Сигнал U мы будем называть влиянием среды. Среда описывается вероятностью выпадания того или иного события. Т.е. среда Е описывается множеством своих состояний D и вероятностью наступления именно этого состояния Р. Будем считать.
Прежде чем начать конструировать и описывать какие-либо автоматы, определим такое фундаментальное понятие теории простейших автоматов, как понятие среды. В отличии от естественных наук, в теории простейших автоматов среде интересует нас только с одной точки зрения: реакции на действие нашего автомата. Значение оценок действий автомата описывается некоторым конечным множеством D= {d1,d2, …dn}. Если наш автомат может сделать наi-том такте одно изmдействий, то среда описывается матрицей вероятностей А(m,n). В которой А(i.j) = вероятности выпаденияj– той реакции среды (dj) наi– тое действие автомата. Если с течением времени значение матрица А остаются неизменными, то среда называется стационарной.
Такую интересную трактовку поведения биологических организмов и описания условий существования этих организмов предложил блестящий советский математик и инженер М.Л. Цетлин. Суть гипотезы простоты Цетлина сводится к тому, что любое достаточно сложное поведение слагается из совокупности простых поведенческих актов. Их совместная реализация и простейшее взаимодействие со средой приводят в результате к весьма сложным поведенческим процессам.
Приведем один из простейших биологических экспериментов, на основе изучения результатов которых Цетлин и создавал свои первые автоматы. В биологии эти опыты известны как опыты Йеркса. В начале опыта дождевой червь помещался на ярко освещенную площадку «Т-образного» лабиринта. Червь начинал движение с целью найти более комфортные условия существования. Там где коридор имел разветвление, червь имел выбор из двух альтернатив. Конечно, червь не мог знать, что по дороге в левом коридоре включено электрическое поле, а заканчивается коридор раздражающей червя солевой ванночкой. В то время как правый коридор приводит червя в затемненную влажную камеру, где он чувствовал себя превосходно.
В процессе эксперимента червь неоднократно проделывал этот путь и «принимал решение» о выборе коридора, постепенно обучаясь выбирать только правый коридор. Другими словами, не имея никакой начальной информации об особенностях среды обитания, червь в процессе взаимодействия с окружающим миром вырабатывал целесообразный способ поведения в нем.
С точки зрения Цетлина общая схема этого опыта выглядит таким образом.
Каким же образом описывается этот автомат и его среда обитания. У нашего автомата есть два возможных действия: {«Направо», «Налево»}, среда также имеет две реакции:{«Наказание», «Поощрение»}. Матрица вероятностей будет выглядеть так:
Немного изменим условия опыта. Эти опыты описаны Торндайком. В такой же, как и в первом опыте, Т-образный лабиринт помещается крыса. В конце и правого, и левого коридора помещена пища. Но по дороге к пище в обоих коридорах крысу ждут неприятные ощущения от раздражения электрическим током. Эти раздражения происходят с фиксированной вероятностью Рпи Рл, которые не меняются в процессе одной серии опытов. Цель эксперимента – определить, сможет ли крыса в процессе обучения научиться выбирать тот коридор, ведущий к пище, в котором вероятность электрического раздражения меньше. При ощутимой разнице между Рпи Рл, после более или менее длительного обучения крысы правильно оценивали эту разницу и принимали целесообразное решение о выборе маршрута. Матрица вероятностей для этого опыта будет выглядеть так:
С точки зрения теории простейших автоматов в обоих случаях рассматривается пример стационарной среды. Но такой мир возможен только в эксперименте. Процессы, протекающие в природе, значительно сложнее и разнообразнее. Как описать их?
С описанием более сложных сред обитания и «жизни» автоматов связано понятиединамической среды. Поскольку законы изменения параметров внешней среды могут быть очень различными мы рассмотрим самый простой способ описания динамической среды. Будем рассматривать динамическую среду как набор конечного числа стационарных сред, описанных уже известным нам способом, Е1, Е2 … Еk. И будем считать, что каждая из этих сред представляет собой моментальную фотографию состояния динамической среды. Эти фотографии, меняясь, как кадры кинофильма, воссоздают нам динамическую среду. Схема взаимодействия автомата с такой средой выглядит так:
Коммутатор как бы подключает автомат к той или иной стационарной среде. Как характеристики этих сред, так и законы работы коммутатора автомату заранее неизвестны. Адаптация состоит не только в оценке вероятностей Рim, где верхний индекс означает среду Еm, а и в определении закономерности смены сред.
+Мы рассмотрим только один, наиболее хорошо изученный, частный случай работы коммутатора. Будем считать, что коммутатор производит переключение сред, руководствуясь некоторой квадратной матрицей. Назовем ее вероятностной матрицей переключения сред Т. Тij– вероятность перехода от Еiк Еjна следующем шаге. По законам теории вероятностей
Такую динамическую среду еще называют переключающейся.
Оценивая поведение автоматов, конструкцию которых мы будем обсуждать позднее, мы будем часто говорить о целесообразности поведения. Сначала обсудим это понятие с точки зрения житейской логики.
Лиса вернулась с богатой добычей. Часть ее насытила лисий выводок, а оставшуюся пищу лиса прячет «на черный день». Тщательно роет яму, кладет в нее мясо и засыпает ее землей. Наблюдая за поведением лисицы, можно прийти к выводу, что цель действий лисицы порождена ее «интеллектом». Столь целесообразно и «разумно» ее поведение.
Но судьба нашей героини оказалась не очень счастливой. Об этом говорит сайт https://intellect.icu . Она попала в западню и стала жительницей зоопарка. Теперь ей уже не приходится тратить силы на добывание пищи. Ее кормят служители. Но что делать лисице, когда пищи избыток? Конечно, прятать! И лиса скребет когтями бетонный пол вольера, а через некоторое время, когда «яма» готова, «прячет» в нее мясо. И после этого перестает замечать остаток трапезы, который, конечно, так и остается лежать на полу вольера. Лиса просто игнорирует его, не видит «зарытое» мясо. То, что в привычной для животного среде выглядело целесообразным, в условиях другой реальности становится лишенным каких-либо черт разумности.
Такие узко специализированные действия, тесно связанные с типовой ситуацией в окружающем мире, принято называть рефлексами. Чем проще организован организм, тем жестче схема рефлекса. Тем нелепее выглядит его поведение в изменившейся среде.
Как же оценивать целесообразность поведения искусственно сконструированных автоматов? Для этого заменим наш автомат устройством равновероятного выбора действий. На каждом шаге своего функционирования этот механизм, никак не учитывая приходящих на его вход сигналов «штраф» - «поощрение», с одинаковой вероятностью, равной 1/n, выбирает одно из доступных ему действий.
П
ри бесконечном повторении опыта с механизмом равновероятного выбора действий, будет накоплен некоторый суммарный штраф. Его величина определяется как математическое ожидание штрафа по формуле, хорошо известной из теории вероятностей:
Значение М*позволяет интерпретировать понятие целесообразного поведения следующим образом. Будем говорить, что автомат ведет себя целесообразно, если накопленный ею суммарный штраф меньше, чем в случае использования механизма равновероятного выбора действий. А нецелесообразным будем считать такое поведение, при котором этот суммарный штраф больше или равен М*.
Пусть, например, в опыте Трондайка Рп= 0,9, а Рл= 0,4. Если бы крыса заранее знала эти вероятности, то она, конечно, всегда бы предпочитала бежать в левый коридор. Если при наших значениях вероятностей штрафов за действия крысу поставить в условия равновероятностного выбора, то суммарное значение штрафа для нее будет равно
М = 0,5*0,9 + 0,5*0,4 = 0,65
А наилучшим поведением будет то, при котором суммарный штраф достигнет своего минимума (при выборе только левого коридора). В этом случае
М = 0*0,9 + 1*0,4 = 0,4
+Опишем структуру технических устройств, обеспечивающих целесообразное поведение в любой априорно неизвестной стационарной среде.
Пример: Рассмотрим ситуацию, встречающуюся в народных сказках. Иванушка-дурачок встречает свадьбу. И начинает громко причитать и плакать. Такое неадекватное поведение вызывает мгновенную реакцию среды. Жестоко побитый Иванушка через некоторое время встречает похороны. Помня свою неудачу, он начинает весело смеяться и петь. И снова жестокая кара постигает нашего простодушного героя. Он снова бит.
Нарисуем граф переходов этого автомата. Состояние 1 – плясать, состояние 2 – плакать. Наша среда так же может вы давать только две ответные реакции: «Бить» или «Не бить». Сплошной чертой мы обозначим реакцию нашего автомата на поощрение (реакция «Не бить»); пунктирной линией – на наказание (реакция «Бить»).
Составим для этого примера таблицу переходов.
Строки – это состояние автомата, в момент времени t
U –это состояние окружающей среды. Обе эти переменные двоичны.
Значения переменной Х – "1" – плакать "2" - петь
Значения переменной U – "0" – похороны "1" - свадьба
Выходом этого автомата будем считать сведения о смене состояния автомата. "0" – если не меняет состояние
"1" – если меняет.
Анализируя нелегкую судьбу Иванушки, сразу возникает идея, что его поведение будет более адекватным, если Иванушка, принимая решение, будет основываться на данных нескольких последних событий, т.е. будет обладать памятью.
Вот как выглядит граф переходов такого автомата. Сплошной стрелкой мы показали переход при наказании, пунктирной – при поощрении. В нашем примере определено по три устойчивых состояния для каждого действия автомата. Будем считать, что состояния 1, 2, 3 – обозначают действие «плакать» нашего Иванушки, а состояния 4, 5, 6 – действие «петь». Это число называется глубиной памятиконечного автомата или степенью егоинерционности. Покажем, что такой автомат достаточно быстро найдет лучшее для статической среды действие, и будет выполнять только его. Поясним эту мысль. Пусть в начале наш автомат находится в состоянии 3. А влияние среды описывается (0,9;0,1) т.е. с вероятностью 0,9 встретится свадьба и с вероятностью 0,1 – похороны. Понаблюдаем за поведением нашего Иванушки. С вероятностью 0,9 встретится свадьба, и Ивана побьют, он перейдет в состояние 4, он станет петь и опять с вероятностью 0,9 на свадьбе. По теории вероятностей, вероятность получения от среды двух свадеб подряд равна 0,81, Двух похорон подряд 0,01, а вероятность одной свадьбы и одних похорон = 0,18. Следовательно, после двух тактов взаимодействия с вероятностью 0,01 автомат окажется в состоянии 1, с Р=0,18 в прежнем положении, и с Р=0.81 в состоянии 5. С ростом числа взаимодействий качественно картина не изменится. Вероятность покинуть группу 6-4 неуклонно падает, а вероятность остаться в ней – растет.
Что произойдет дальше? С Р=0,9 наш автомат получит поощрение и перейдет в состояние 6 и т.д. Вероятность покинуть группу 4-6 все время будет уменьшаться. Этот процесс очень похож на процесс обучения, после которого наш автомат "достаточно адекватно" ведет себя в данной статической среде. "Достаточно адекватно" потому, что существует очень малая, но ненулевая вероятность покинуть группу наиболее благоприятного поведения ( т.е. поведения когда сумма штрафов минимальна).
Если же среда динамическая, то существует зависимость, между вероятностью смены законов среды и глубиной памяти автомата. Это утверждение интуитивно понятно, ведь в динамическом мире смена ситуаций происходит с большой частотой, и инерционность вряд ли может служить хорошим средством для существования в этом мире. Экспериментально показано, что для каждого динамического мира нужна своя наилучшая глубина памяти, выбранная в зависимости от скорости изменения обстановки, а не по принципу «Чем больше, тем лучше». Такая глубина памяти называется оптимальной.
Все сказанное выше, справедливо и для автомата, у которого больше двух действий и больше двух состояний среды. Чем больше глубина памяти такого автомата, тем целесообразнее его поведение. Рассмотренный нами автомат называется автоматом с линейной тактикой.
Подчеркнем еще раз, повышение глубины памяти улучшает показатель целесообразности поведения автомата с линейной тактикой для статических сред. Более того, Цетлин показал, что если minPi<0,5 то при увеличении глубины памятиqавтомата с линейной тактикой мы получим последовательность автоматов с линейной тактикой со все увеличивающейся глубиной памяти, которая является асимптотически оптимальной. Это означает, что приq→∞ М(q, Е) → Мmin– минимальный суммарный штраф. Т.о. конструкция, предложенная Цетлиным, обеспечивает при достаточно больших значенияqповедение, сколь угодно близкое к наилучшему в любых стационарных случайных средах.
Рассмотрим еще пару конструкция автоматов с линейной тактикой.
Эта конструкция предложена В.И. Кринским. Мы будем называть «доверчивым». Вот как выглядит его граф переходов.
При поступлении сигнала штраф, поведение этого автомата аналогично поведению автомата с линейной тактикой Цетлина, но при получении сигнала поощрения, этот автомат, независимо в каком состоянии лепестка он находился в данный момент, переходит в самое глубокое состояние данного лепестка. Этот автомат, как будто, склонен верить в хорошее, и положительный сигнал среды приводит его в состояние «эйфории».
Строго доказано, что автоматы Кринского ведут себя целесообразно в любых стационарных случайных средах.
Может сложиться ощущение, что любые меры по увеличению числа инерционности автомата, улучшает показатель целесообразности поведения автомата.
+Ситуация качественно меняется, если наш линейный автомат имеет дело с динамической средой. Если смена сред происходит достаточно быстро, то инерционность вряд ли может служить хорошим средством для существования в этом мире. Ведь в динамическом мире надо быстро следить за возникающими изменениями среды, и для любого динамического мира необходима своя глубина памяти, выбранная в зависимости от скорости изменения обстановки.
Опишем теперь структуру автомата, поведение которого в той или иной мере будет отвечать требованиям среды. Этот автомат называется вероятностным. Устроен он подобно автомату с линейной тактикой, но его функции переходов и выходов являются случайными функциями. Т.е. задается вероятность переходов из одного состояния в другое, при поступлении на вход определенного сигнала. Такой автомат, как правило, задается системой матриц, в которых на пересеченииi– того столбца иk–той строки указывается Р перехода изi– того состояния вk-тое. В частном случае, когда такие матрицы содержат только "0" и "1", описывается уже знакомый нам детерминированный автомат.
Выписывание таких матриц слишком громоздкая процедура, поэтому покажем вид этих матриц для автомата, показанного на рисунке.
Эти матрицы определяют детерминированную структуру нашего автомата. П+ - матрица переходов при поступлении сигнала поощрения, а П- при поступлении сигнала штрафа.
Матрицы примера описывают вероятностный автомат, еще иногда называемый автоматом Крылова. При поступлении сигнала поощрения этот автомат действует подобно детерминированному автомату, а при поступлении сигнала штрафа он с вероятностью 0,5 останется в прежнем положении, а с вероятностью 0,5 перейдет в другое состояние. Такой автомат, как будто не спешит менять свое действие, а случайным (но не изменяющимся с работой автомата образом) принимает решение о переходе, предварительно «подбросив монетку». Такой автомат еще можно назвать осторожным.
Приведем наглядный пример такого автомата.
Пытаясь формализовать способы спасения ночной бабочки от летучей мыши. Летучая мышь испускает направленный ультразвуковой сигнал и способна улавливать отраженный сигнал, при чем с достаточно высокой точностью различать и идентифицировать сигналы, различая подвижные и неподвижные цели, земные цели и воздушные, маленькие и большие. Кроме того, отраженный сигнал позволяет летучей мыши с весьма большой точностью определять направления и расстояние до потенциальных целей.
Ночные бабочки также способны принять сигнал от летучей мыши и определить его интенсивность. Поведение бабочки различно в зависимости от того, как далеко от нее находится летучая мышь. Будем различать три маневра бабочки.
Бабочка начинала двигаться в сторону, противоположную прежнему движению.
Бабочка меняла направление в вертикальной плоскости, уходя от своего прежнего курса вверх или вниз.
Б абочка начинала хаотическое движение, т.е. переходит на такую траекторию полета, которая максимально затрудняет для нападающего предсказание следующей точки на этой траектории.
На рисунке изображен граф смены состояний вероятностного автомата. Его особенность состоит в том, что для каждой группы состояний (они обведены на рисунке пунктиром) существует ненулевая вероятность перейти в особое состояние, описывающее гибель автомата. Состояние 1 можно интерпретировать следующим образом: 1 – с Р=0,3 летучая мышь обнаруживает бабочку, а с Р=0,7 – пропускает ее. 2 – мышь определяет направление своего движения и с р= 0,8 цель при этом не теряется. 3 – летучая мышь настигает бабочку и уничтожает ее с Р=0,95. Что может противопоставить преследователю бабочка? Для простоты изложения будем рассматривать каждую из групп состояний автомата, как определенную среду, задаваемую стратегией бабочки. Е1 – это прямой полет. Е2 – изменение направления движения в горизонтальной или вертикальной плоскости, а Е3 – хаотическое движение. Действия бабочки сводятся к смене сред, переключению их. При этом автомат может реализовывать действие только в состоянии 2 или 3. На рисунке это показано двойными стрелками переходов.
Составьте сами таблицу состояний этого автомата.
+В приведенном примере действия, позволяющие бабочке максимально увеличить вероятность своего спасения, достаточно просты и прозрачны. Однако в общем случае выбор оптимальной последовательности переключений действий автомата, максимизирующий продолжительность его жизни далеко не тривиален. Наша же цель: показать принципы действия вероятностного автомата достигнута.
Для начала рассмотрим такую ситуацию. Предположим, что вы на своей машине ежедневно добираетесь от дома до работы. В вашем распоряжении есть два возможных маршрута, и вы вольны выбрать любой из них. Т.к. вы всегда выезжаете в одно и то же время, то обстановка по каждому из маршрутов как бы стационарна. И анализируя эту обстановку, вы убедились, что один из маршрутов лучше другого: времени тратиться меньше – движение здесь менее интенсивное, чем по другому маршруту, да и светофоров здесь не так много. Но вот беда: время от времени из-за каких-то ремонтных работ скорость движения здесь резко снижается, образуются пробки, и можно потерять много времени пока они ликвидируются. В этих условиях данный маршрут становится намного хуже другого. Вы бы потеряли куда меньше времени, выбрав в эти неудачные дни другой маршрут. Если нет никакой информации о частоте ремонтных работ на трассе первого маршрута, то выезжая из дома нет никаких шансов угадать, по какому маршруту лучше сегодня ехать. Однако, день за днем, вы накапливаете информацию. Учитесь на своем горьком опыте. Выясняется, что чаще всего пробки образуются в среду и пятницу и вероятность этих пробок достаточно велика. Тогда выбирая в остальные дни недели первый маршрут, вы в среду и пятницу без колебаний выбираете менее хороший маршрут поездки.
Но ни автомат с линейной структурой, ни вероятностный автомат Крылова не могут приспособиться к часто меняющейся динамической среде, поскольку его таблицы переходов не меняются в процессе функционирования. Поэтому рассмотрим модель автомата с переменной структурой. Это уже знакомый нам вероятностный автомат в начале функционирования находящийся в безличном состоянии, с наперед заданными вероятностями переходов.
Если, выполнив какое-то действие, автомат получил сигнал штраф, то в матрице переходов он уменьшает значение вероятности этого перехода на заданную величину Δ , но сумма всех элементов строк должна быть равна 1, поэтому все ненулевые элементы строки необходимо изменить на величину Δ/h, где h – количество ненулевых элементов строки.
П
усть для определенности в начальный момент времени автомат находился в состоянии 1, и совершил действие 1, соответствующее этому состоянию. С помощью равновероятного выбора по матрице П+ перешел в состояние 4. И пусть после этого он получил сигнал штраф. Получение такого сигнала заставляет автомат считать свой переход 1 – 4 ошибкой. Эта информация фиксируется следующим образом. Вероятность П+14 уменьшается на Δ, а все остальные элементы строки увеличиваются на Δ/3. Для удобства положим Δ= 0.03. Тогда после этого шага матрица П- не изменится, а матрица П+ будет выглядеть так:
На очередном шаге автомат делает действие 2, соответствующее состоянию 4, и выбирает очередное состояние на основании матрицы П- (т.к. в текущем акте общения со средой он находится в условиях последнего сигнала от среды – штрафа).
П
усть он выбрал переход 4 – 4 и вновь получил штраф. Теперь меняется матрица П-, а матрица П+ остается неизменной.
Так постепенно происходит перестройка матриц П+ и П- в зависимости от сигналов, формируемых средой. Для автоматов с переменной структурой экспериментально показан следующий фундаментальный результат: с течением времени функционирование автомата с переменной структурой в переключающихся средах, а которых автомат с линейной тактикой ведет себя целесообразно, неограниченно приближается к поведению автомата линейной структурой с оптимальной глубиной памяти. Другими словами, автомат с переменной структурой сам находит оптимальную глубину памяти. Это весьма важно, т.к. значение оптимальной глубины памяти нельзя определить аналитически, оно подбирается в процессе функционирования в среде.
Рассмотрением этой конструкции автомата мы и ограничимся.
Скажем только, что существует очень большое множество классов конечных и бесконечных автоматов, активно используемых в технике. И более подробно об этих объектах вы будете говорить в курсах теории автоматического управления. Я же хочу обобщить сказанное.
С математической точки зрения автомат задается А – входным алфавитом, В – выходным алфавитом, S – алфавитом состояний автомата и двумя функциями φ - функцией переходов и β - функцией выходов.
Напомню, что под алфавитом понимается множество возможных значений. φ и β могут быть и произвольными отношениями и вероятностными функциями.
Следует четко понимать, что функция φ отображает множество SxА в S; а β- отображает множество SxА в В.
Исследование, описанное в статье про простейший автомат, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое простейший автомат, детерминированный автомат, вероятностный автомат и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Теория конечных автоматов
Комментарии
Оставить комментарий
Теория конечных автоматов
Термины: Теория конечных автоматов