Адаптивные системы управления

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Введение

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

Адаптивная система называется самоорганизующейся, если изменяется структура алгоритма. Адаптивные системы управления используются, когда с помощью обычных систем не удаётся справиться с поставленной задачей. А это обычно происходит, когда начальной (априорной) информации об объекте недостаточно или характеристика объекта в процессе функционирования системы изменяется непредвиденным образом в широких пределах. [1]

Методы технологии мобильных агентов

Для получения полной картины о состоянии безопасности в сетях организации некоторые СОВ используют распределенный сбор данных от контролируемых хостов, но функции анализа и принятия решения возлагаются при этом на единственный механизм. Этот подход имеет ряд недостатков: сложность с конфигурированием, ограниченная расширяемость. Поэтому в последние годы разрабатываются варианты распределенного сбора данных (сенсоров) и распределенного анализа данных (принятия решения). Одной из технологий, которая может быть использована для построения распределенных СОВ, является технология агентов. В качестве примера рассмотрим архитектуру системы AAFID (Autonomous Agents for Intrusion Detection) [1].

Система AAFID разработана в университете Purdue, , West Lafayette, IN, USA (http://www.cs.purdue.edu/coast/projects/autonomous-agents.html).

AAFID - это одновременно название распределенной архитектуры систем обнаружения атак и собственно системы обнаружения атак. Основой системы являются автономные агенты обнаружения. Наиболее интересна в системе именно ее архитектура. Данная система базируется на работах Crosbie и Spafford, которые предложили использование автономных агентов, работающих на основе генетических алгоритмов и адаптирующихся к поведению пользователей.

Основными компонентами системы являются: агенты, фильтры, трансиверы, мониторы.

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

То есть функционирование агента не зависит от других компонентов системы обнаружения атак. Агенты могут использовать фильтры для сбора информации о поведении объектов в архитектурно-независимом представлении. Все агенты на одном узле передают собранную информацию одному трансиверу. Трансивер - компонент системы обнаружения, который управляет запуском и остановкой агентов на данном узле. Каждый узел, на котором есть агенты, имеет один трансивер. Кроме того, трансиверы могут осуществлять некоторую редукцию получаемой от агентов информации в более обобщенное представление. Трансиверы передают полученную информацию одному или нескольким мониторам. Каждый монитор наблюдает и взаимодействует с несколькими трансиверами. Мониторы функционируют на уровне защищаемой системы в целом, поэтому они могут анализировать получаемую информацию с учетом корреляции событий в разных областях защищаемой системы. Мониторы могут располагаться в иерархическом порядке. Монитор также является связующим компонентом между системой обнаружения и пользовательским интерфейсом - он получает управляющие команды и отдает полученную и проанализированную информацию. На рис. 5.1 представлена архитектура системы обнаружения, а на рис. 5.2 - иерархия компонентов системы обнаружения.

Рис. 5.1. Архитектура системы AAFID, основные компоненты системы

Рис. 5.2. Иерархия компонентов системы AAFID

Остановимся более подробно на описании компонентов системы AAFID.

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

Фильтры предназначены для сбора однотипной информации из различных источников (различных системных журналов или от наблюдателей). Так же фильтры выполняют функции уровня представления модели OSI (Open System Interconnect): преобразовывают форматы данных, собираемых из аналогичных источников, но на разных архитектурах, к единому виду.

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

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

Мониторы - наивысшие в иерархии компоненты системы AAFID. Функционально они похожи на трансиверы с тем отличием, что сбор и анализ информации происходит не на одном узле, а на части сети или на всей сети. Мониторы могут управлять трансиверами и другими мониторами. Мониторы имеют механизмы взаимодействия с пользовательским интерфейсом и являются точками доступа к системе обнаружения атак. [0]

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

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

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

Глава 1. Введение в автоматное программирование

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

1.1 Области применения автоматного подхода

В соответствии с классификацией, введенной Д. Харелом [2], любую программную систему можно отнести к одному из следующих классов.

· Трансформирующие системы осуществляют некоторое преобразование входных данных, и после этого завершают свою работу. В таких системах, как правило, входные данные полностью известны и доступны на момент запуска системы, а выходные - только после завершения ее работы. К трансформирующим системам относятся, например, архиваторы и компиляторы.

· Интерактивные системы взаимодействуют с окружающей средой в режиме диалога (например, текстовый редактор). Характерной особенностью таких систем является то, что они могут контролировать скорость взаимодействия с окружающей средой - заставлять среду «ждать».

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

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

Другая традиционная область использования автоматов - задачи логического управления [4] - является подклассом реактивных систем. Здесь автомат - это, на первый взгляд, совсем другое устройство. У него несколько параллельных входов (чаще всего двоичных), на которые в режиме реального времени поступают сигналы от окружающей среды. Обрабатывая эти сигналы, автомат формирует значения нескольких параллельных выходов.

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

Критерий применимости автоматного подхода лучше всего выражается через понятие «сложное поведение». Неформально можно сказать, что сущность (объект, подсистема) обладает сложным поведением, если в качестве реакции на некоторое входное воздействие она может осуществить одно из нескольких выходных воздействий. При этом существенно, что выбор конкретного выходного воздействия может зависеть не только от входного воздействия, но и от текущего состояния сущности и от предыстории. Для сущностей с простым поведением реакция на любое входное воздействие зависит только от этого воздействия Сложное поведение также называют поведением, зависящим от состояния (в англоязычной литературе используется термин state-dependent behavior). Соответственно, простое поведение можно назвать поведением, не зависящим от состояния. Смысл этих терминов станет более ясным в разд. 1.3, когда будет рассмотрено понятие управляющих состояний. (рис. 1.1).

Рис. 1.1. Сущность с простым поведением (слева) и со сложным поведением (справа)

1.2 Основные понятия

Базовым понятием автоматного программирования является «состояние». Понятие состояния в том смысле, как оно используется в данной парадигме, было введено А. Тьюрингом. Это понятие с успехом применяется во многих развитых областях науки, например, в теории управления и теории формальных языков. Основное свойство состояния системы в момент времени t₀ заключается в «отделении» будущего (t > t₀) от прошлого (t < t₀) в том смысле, что текущее состояние несет в себе всю информацию о прошлом системы, необходимую для определения ее реакции на любое входное воздействие, формируемое в момент t₀.

В разд. 1.1 при описании понятия «сложное поведение» упоминалось, что реакция сущности со сложным поведением на входное воздействие может зависеть, в том числе, и от предыстории. При использовании понятия «состояние» знание предыстории более не требуется. Состояние можно рассматривать как особую величину, которая в неявной форме объединяет все входные воздействия прошлого, влияющие на реакцию сущности в настоящий момент времени. Реакция зависит теперь только от входного воздействия и текущего состояния. Понятие входного воздействия также является одним из базовых для автоматного программирования. Чаще всего, входное воздействие - это вектор. Его компоненты подразделяются на события и входные переменные в зависимости от смысла и механизма формирования. Совокупность конечного множества состояний и конечного множества входных воздействий образует (конечный) автомат без выходов. Такой автомат реагирует на входные воздействия, определенным образом изменяя текущее состояние. Правила, по которым происходит смена состояний, называют функцией переходов автомата.

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

Рис. 1.4. Конечный автомат

1.3 Парадигма автоматного программирования

Для того чтобы лучше разобраться в основных концепциях автоматного программирования, рассмотрим сначала один из абстрактных вычислителей, широко применяемых в теории формальных языков - машину Тьюринга [5, 6]. Эта абстрактная машина была предложена А. М. Тьюрингом в 1936 г. в качестве формального определения понятия «алгоритм». Тезис Черча-Тьюринга [6] гласит, что все, что можно «вычислить», «запрограммировать» или «распознать» в любом смысле (из формально определенных в настоящее время) можно вычислить, запрограммировать или распознать с помощью подходящей машины Тьюринга. Машина Тьюринга состоит из двух частей: устройства управления и запоминающего устройства - ленты (рис. 1.5). Лента состоит из бесконечного числа ячеек, в которых могут быть записаны символы некоторого конечного алфавита. В каждый момент времени на одной из ячеек ленты установлена головка чтения-записи, позволяющая устройству управления считывать или записывать символ в этой ячейке.

Рис. 1.5. Машина Тьюринга

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

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

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

1. Двигаться вправо, пока не встретиться пустой символ.

2. Сдвинуться на одну ячейку влево.

3. Пока в текущей ячейке находится '1', заменять его на '0' и двигаться влево.

4. Если в текущей ячейке находится '0' или 'blank', записать в ячейку '1' и завершить работу.

Этот алгоритм необходимо «ввести» («закодировать») в устройство управления машины Тьюринга. Другими словами, необходимо задать состояния, а также функции переходов и выходов ее управляющего автомата. Удобный и наглядный способ сделать это предоставляют графы переходов автоматов, иначе называемые диаграммами переходов. Подробнее язык графов переходов будет обсуждаться в разд. 2.2, а пока достаточно знать, что вершины в этом графе соответствуют состояниям автомата, а дуги - переходам между состояниями. Каждая дуга помечается условием перехода (значениями входных воздействий, которые инициируют этот переход) и действием на переходе (значениями выходных воздействий).

На рис. 1.6 представлен граф переходов управляющего автомата машины Тьюринга, реализующей функцию инкремент. Здесь символ `b' - сокращение от blank, символ `*' на месте записываемого символа означает «записать тот же самый символ, который был считан». Команды головке обозначаются стрелками (стрелка вниз означает «остаться на месте»).

Рис. 1.6. Увеличение числа на единицу с помощью машины Тьюринга

Отметим, что в графе переходов обозначены имена состояний управляющего автомата. Эти имена отражают смысл состояния и являются кратким описанием поведения машины в этом состоянии. Итак, управляющий автомат машины Тьюринга, реализующей функцию инкремент, имеет три состояния. Сколько же состояний у этой машины в целом? Ее действия в каждый момент времени полностью определяются совокупностью состояния управляющего автомата, строки на ленте и положения головки. Отметим, что символы на ленте для устройства управления представляют собой входные воздействия, однако, относительно машины в целом они не являются входными (внешними), а формируют часть внутреннего состояния вычислителя. Всевозможных строк на ленте, как и положений головки, бесконечно много, поэтому и у машины Тьюринга бесконечное число состояний.

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

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

ПРИМЕЧАНИЕ

Понятие «состояние», так же как и деление на управляющие и вычислительные состояния, не является «чужеродным» для программирования. Традиционно под состоянием программы подразумевают множество текущих значений всех используемых в ней переменных [7, 8]. И хотя число переменных, равно как и число потенциальных значений каждой переменной, можно считать конечным, получающееся пространство состояний оказывается необозримо большим. Однако не все исследователи трактуют понятие состояния программы столь же прямолинейно. Так, А. Дж. Перлис в 1966 г. [9] предложил в описания языка, среды и правил вычислений включать состояния, которые могут подвергаться мониторингу во время исполнения, позволяя диагностировать программы, не нарушая их целостности. В этом же году Э. Дейкстра [10] предложил ввести так называемые переменные состояния, с помощью которых можно описывать состояния системы в любой момент времени (Дейкстра использовал для этих целей целочисленные переменные). При этом им были поставлены вопросы о том, какие состояния должны вводиться, как много значений должны иметь переменные состояния и что эти значения должны означать. Он предложил сначала определять набор подходящих состояний, а лишь затем строить программу. По мнению Э. Дейкстры, диаграммы переходов между состояниями могут оказаться мощным средством для проверки программ. Это обеспечивает поддержку его идеи о том, что программы должны быть с самого начала составлены правильно, а не отлаживаться до тех пор, пока они не станут правильными.

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

Таблица 1.1. Управляющие и вычислительные состояния

Управляющие состояния	Вычислительные состояния
Их несколько	Их количество либо бесконечно, либо конечно, но очень велико
Каждое из них имеет вполне определенный смысл и качественно отличается от других	Большинство из них не имеет смысла и отличается от остальных лишь количественно
Они определяют действия, которые совершает сущность	Они непосредственно определяют лишь результаты действий

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

Переход от ленты, головки и простейших команд к языкам высокого уровня, конечно, упрощает программирование, но при реализации сущностей со сложным поведением полностью проблемы не решает. Вспомните электронные часы из разд. 1.1. Точно так же, как в нашей «воображаемой» машине, состоящей только из ленты, в листинге 1.1 логика затеряна среди деталей. Опыт рассмотрения машины Тьюринга подсказывает, что для того, чтобы сделать программу простой и понятной, необходимо явно выделить управляющие состояния (идентифицировать их, дать им имена) и описать поведение сущности в каждом из них. Например, при реализации электронных часов с будильником можно выделить три управляющих состояния: «Будильник выключен», «Установка времени будильника» и «Будильник включен». В каждом из этих состояний реакция будильника на нажатие любой кнопки будет однозначной и специфической.

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

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

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

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

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

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

Парадигма автоматного программирования состоит в представлении сущностей со сложным поведением в виде автоматизированных объектов управления.

1.4 Автоматные модели

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

В настоящее время предложены, исследованы и с успехом применяются различные математические модели, в названиях которых используется слово «автомат». Они имеют много общего в своих основах, но различаются, часто существенно, в деталях. Причина разнообразия автоматных моделей объясняется широтой области их применения (пример различного понимания природы автоматов при создании компиляторов и в задачах логического управления приведен в разд. 1.1). Автоматы являются незаменимым инструментом в таких далеких друг от друга областях как, например,

· математическая лингвистика;

· логическое управление;

· моделирование поведения человека;

· теория формальных языков, вычислимости и вычислительной сложности.

Выявить общее в различных автоматных моделях можно, если рассмотреть автоматы как частный случай динамических систем. Обычно термином «динамическая система» в технике, природе, жизни и т. д. обозначают систему, процессы которой развиваются во времени. Состояние системы в каждый момент времени характеризуют некоторым множеством обобщенных координат. Процессы в динамической системе описываются уравнениями разных типов относительно обобщенных координат [11].

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

· Модель времени. Время может считаться текущим непрерывно или дискретно. В первом случае время изменяется на континууме, во втором -- на счетном множестве, элементы этого счетного множества называются тактами.

· Размерность системы. Число обобщенных координат может быть конечным или счетным.

· Мощность множеств координат. Каждая из обобщенных координат может принимать значения из конечного, счетного или континуального множества.

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

Если же время дискретно, но обобщенные координаты принимают значения из континуальных множеств, то для описания процессов используются разностные уравнения. Те системы, в которых время дискретно, число обобщенных координат конечно и каждая координата может принимать значения из конечного множества, называют конечными динамическими системами. Конечные автоматы принадлежат к классу конечных динамических систем. Системы, которые отличаются от конечных тем, что число обобщенных координат или же множество значений координат может быть бесконечно, образуют более общий класс. К этому классу принадлежат, например, машины Тьюринга. Рассмотрим конечную динамическую систему с дискретным временем, состояние которой в каждый такт t характеризуется конечным числом обобщенных координат Y(t), |Y| = n, и на вход которой подается конечное число входных воздействий X(t), |X| = m. Такая конечная динамическая система называется конечным автоматом, если состояние системы в каждый такт однозначно определяется состоянием системы в предыдущий такт и значениями входных воздействий либо в текущий (1), либо в предыдущий (2) такт.

Y(t) = f (X (t),Y(t ?1)) ; (1)

Y(t) = f (X (t ?1),Y (t ?1)) . (2)

Из приведенных формул видно, что для описания поведения конечных автоматов используются рекуррентные соотношения определенного вида. Если используется рекуррентное соотношение (1), то автомат называется автоматом первого рода, а если соотношение (2) -- автоматом второго рода. Можно показать, что понятие «конечный автомат» охватывает и те конечные системы, состояния которых определяются предысторией любой наперед заданной конечной длины. Однако оно не охватывает системы, в которых состояние определяется статистически или же зависит от всей предыстории. Таким образом, класс конечных динамических систем, которые «помнят» конечное число предыдущих тактов не шире класса систем, которые «помнят» только один такт. В настоящей работе рассматриваются только автоматы с задержкой не более чем на один такт.

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

Далее будут рассмотрены две практически независимые «системы» автоматных моделей: одна заимствована из теории формальных языков, а другая - из области логического управления. Как упоминалось выше, в обеих областях традиционно используются конечные автоматы, однако, понимаются они очень по-разному: применяются различные системы терминов, различные классификации, сферы интересов двух областей практически не пересекаются.

В теории формальных языков изучаются, так называемые, абстрактные автоматы (называемые также абстрактными машинами или абстрактными вычислителями). Внутренняя структура абстрактных автоматов не раскрывается, интерес при их изучении представляет только вычислительная мощность - класс языков, которые может распознавать машина. Модели абстрактных автоматов рассматриваются в разд. 1.4.1. В логическом управлении рассматриваются структурные автоматы. Они выступают в роли управляющих устройств в системах управления. Интерес здесь представляет число параллельных входов и выходов автомата, его связи с объектом управления и другими элементами системы, простота реализации. Модели структурных автоматов рассматриваются в разд. 1.4.2.

Автоматное программирование, с одной стороны, объединяет в себе опыт двух указанных разделов теории автоматов [12], а с другой - является совершенно самостоятельной областью. При использовании автоматов в программировании не имеют значения ни исследования вычислительной мощности, ни минимизация числа функциональных элементов и вопросы кодирования. В этой области нас интересует только то, как использовать конечные автоматы для построения корректных и надежных программ. В разд. 1.4.3 приводится формальное описание модели автоматизированного объекта управления. Эта модель является, в некотором смысле, обобщением других автоматных моделей, и соединяет в себе черты как абстрактных, так и структурных автоматов. В то же время, рассмотрению подлежат именно те свойства модели, которые имеют значение для ее применения в программировании.

1.4.3 Автоматы в программировании

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

Цель этого раздела - построить модель автоматизированного объекта управления (для краткости называемого просто автоматизированным объектом, АО). Это понятие уже было введено неформально (разд. 1.3) как совокупность управляющего автомата и объекта управления. Предпосылкой для введения этой концепции была необходимость проектирования и реализации систем со сложным поведением.

Теперь попробуем придти к понятию автоматизированного объекта управления с другой стороны: путем обобщения традиционных автоматных моделей. Вспомним абстрактные модели автоматов, рассмотренные в разд. 1.4.1. Как отмечалось выше, все они имеют похожую структуру: они состоят из устройства управления (представляющего собой ДКА с выходом) и хранилища данных того или иного вида (ленты, магазина). Для теории формальных языков вид хранилища и набор элементарных операций с данными имеют решающее значение: они определяют вычислительную мощность машины. При моделировании и высокоуровневой программной реализации сущностей со сложным поведением, удобнее заменить конкретное хранилище данных объектом управления (ОУ), множество (вычислительных) состояний которого может быть любым и определяется спецификой решаемой задачи (рис. 1.18).

Рис. 1.18. Слева направо: автомат с магазинной памятью, автомат с ленточной памятью (машина Тьюринга), автомат с произвольной памятью (автоматизированный объект)

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

Важная черта устройства управления всех абстрактных машин - его конечность. Управляющий автомат не только имеет конечное число состояний, но, кроме того, реализуемые им функции переходов и выходов оперируют исключительно конечными множествами. Именно это свойство позволяет описывать логику поведения машины явно: в виде таблицы или графа переходов. Поэтому свойство конечности устройства управления необходимо сохранить при построении модели автоматизированного объекта. Более того, это свойство целесообразно усилить следующим неформальным требованием: число управляющих состояний, входных и выходных воздействий должно быть небольшим (обозримым). Управляющий автомат с миллиардом состояний, безусловно, является конечным, однако, изобразить его граф переходов практически невозможно, что сводит на нет преимущества явного выделения управляющих состояний. Напротив, число вычислительных состояний может быть сколь угодно большим (при переходе от модели к программной реализации оно с необходимостью станет конечным, однако, может остаться необозримым). В процессе работы управляющему автомату требуется получать информацию о вычислительном состоянии и изменять его. Однако, в силу свойства конечности, автомат не может напрямую считывать и записывать вычислительное состояние. Для этого и требуются операции объекта управления. Небольшое число запросов, возвращающих конечнозначные результаты, позволяет автомату получить информацию о вычислительном состоянии, которую он способен обработать. Небольшое число команд используется для «косвенного» изменения вычислительного состояния.

Операции с памятью в традиционных абстрактных вычислителях также можно считать командами и запросами. Рассмотрим, например, автомат с магазинной памятью. Его множество вычислительных состояний бесконечно: это есть множество всех возможных конфигураций стека. Для управления стеком автомат использует один запрос top, возвращающий символ на вершине стека, и две команды pop и push, первая из которых снимает символ со стека, а вторая заталкивает символ в стек Push можно считать как одной командой, аргументом которой является заталкиваемый символ, так и набором команд без аргументов - по одной для каждого символа магазинного алфавита. Это не имеет значения, поскольку магазинный алфавит конечен..

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

Некоторые из рассмотренных моделей (например, ДКА и детерминированный МП-автомат) начинают следующий такт работы только в том случае, если получают на вход очередной символ. Их работа всегда заканчивается по достижении конца входной строки. Обобщая такое поведение, введем понятие пассивной автоматной модели: каждый такт ее работы инициируется внешней средой, а по окончании такта управление передается обратно этой среде.

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

ПРИМЕЧАНИЕ

На самом деле, при аппаратной реализации синхронных структурных автоматных моделей начало нового такта инициируется тактовым генератором. Однако предполагается, что он является «внутренним» для автомата по сравнению с внешней средой, подающей входные воздействия. Поэтому, с точки зрения среды, такой автомат является активным.

Если активная автоматная модель в качестве входного воздействия считывает вычислительное состояние внешней среды, то для пассивной более характерно событийное взаимодействие: среда сама (асинхронно) сигнализирует о своем изменении, вызывая автоматную модель с некоторым событием. В программировании активные автоматные модели целесообразно применять при реализации трансформирующих и интерактивных систем, а пассивные - при создании реактивных систем. В пассивной модели, в общем случае, лишь некоторые компоненты входного воздействия являются событиями, а остальные представляют собой «традиционные» входные переменные: их значения опрашиваются самим автоматом, а их изменения не инициируют начало такта. Вернемся снова к абстрактным вычислителям. Заметим, что в некоторых из них (таких как ДКА) автомат взаимодействует только с внешней средой, получая от нее входные символы. В других (например, в машине Тьюринга) - автомат общается лишь со своим объектом управления, или, в терминах теории абстрактных автоматов, со своей дополнительной памятью. В-третьих (таких как МП-автомат) - устройство управление взаимодействует и с внешней средой и с объектом управления, причем от среды оно получает лишь входные воздействия, тогда как взаимодействие с объектом управления имеет двунаправленный характер. При построении модели автоматизированного объекта целесообразно использовать третий вариант как наиболее общий (рис. 1.19).

Рис. 1.19. Взаимодействие компонентов модели автоматизированного объекта

На рисунке сплошными стрелками обозначены традиционные и наиболее типичные для программных реализаций виды взаимодействия между автоматом, объектом управления и внешней средой. Автомат получает входные воздействия как со стороны среды, так и от объекта управления. В событийных системах часть или все компоненты входного воздействия со стороны среды могут быть событиями (множество событий обозначено на рисунке буквой E). Входное воздействие со стороны объекта управления формирует в модели обратную связь (от управляемого объекта к управляющему). Это воздействие может отсутствовать, тогда модель является разомкнутой - так в теории управления называются системы управления без обратной связи [14]. В противном случае модель называется замкнутой.

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

Если по назначению сущность близка к традиционной системе управления, то представление входных и выходных воздействий битовыми строками будет удобным по тем же причинам, что и для структурных автоматных моделей. Однако интерпретация этого представления может быть различной. В примере со счетным триггером (разд. 1.4.2) каждое из двух значений выходной переменной обозначало действие: единица соответствовала включению лампы, а ноль - выключению. В программировании чаще используется другая интерпретация: каждой выходной переменной сопоставляется единственное действие (команда). При этом единица обозначает наличие действия, а ноль - его отсутствие. В этом случае вектору из нулей соответствует отсутствие каких-либо команд. Такой вид выходного воздействия может привести к недетерминизму в том случае, если результат зависит от последовательности выполнения команд. Поэтому в качестве выходного воздействия вместо множества команд часто используется последовательность команд.

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

Глава II. Задача об «Умном муравье»

автоматная модель вычислительная управляющая

В последнее время все шире начинает применяться автоматное программирование, в рамках которого поведение программ описывается с помощью конечных детерминированных автоматов [1].

Для многих задач автоматы удается строить эвристически, однако существуют задачи, для которых такое построение автоматов затруднительно. К задачам этого класса относится, в частности, и задача об «Умном муравье» [2-4].

В этих работах генерация автоматов выполнялась с помощью генетических алгоритмов [5] на однопроцессорной ЭВМ. Однако построенные в этих работах автоматы содержат большое число состояний. Цель настоящей работы - устранить этот недостаток, также используя однопроцессорную ЭВМ.

1. ПОСТАНОВКА ЗАДАЧИ

Приведем описание задачи об «Умном муравье» [2]. Игра происходит на поверхности тора размером 32 на 32 клетки (рис. 1). В некоторых клетках (обозначены на рис. 1 черным цветом) находится еда. Она расположена вдоль некоторой ломаной, но не во всех ее клетках. Клетки ломаной, в которых нет еды обозначены серым цветом. Белые клетки не содержат еду и не принадлежат ломаной. Всего на поле 89 клеток с едой.

Рис. 1. Игровое поле

В клетке, помеченной меткой «Start», в начале игры находится муравей. Он занимает одну клетку и смотрит в одном из четырех направлений (север, юг, запад, восток). В начале игры муравей смотрит на восток. Муравей умеет определять находится ли непосредственно перед ним еда. За один игровой ход муравей может совершить одно из четырех действий:

· сделать шаг вперед, съедая еду, если она там находится;

· повернуть налево;

· повернуть направо;

· ничего не делать.

Съеденная муравьем еда не восполняется, муравей жив на протяжении всей игры, еда не является необходимым ресурсом для его жизни. Ломаная не случайна, а строго фиксирована. Муравей может ходить по любым клеткам поля. Игра длится 200 ходов, на каждом из которых муравей совершает одно из четырех действий. По истечении 200 ходов подсчитывается количество еды, съеденной муравьем. Это значение и есть результат игры.

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

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

Например, эвристически построенный автомат из [2], граф переходов которого изображен на рис. 2, описывает поведение муравья, который съедает 81 единицу еды за 200 ходов, а всю еду - за 314 ходов.

Рис. 2. Простой автомат, описывающий поведение муравья

Поясним используемые на рис. 2 обозначения. Пометки на переходах имеют формат условие / действие. Условия обозначаются следующим образом:

· F - перед муравьем есть еда;

· !F - перед муравьем нет еды.

Действия обозначаются следующим образом:

· M - «Сделать шаг вперед»;

· L - «Повернуть налево»;

· R - «Повернуть направо»;

· N - «Ничего не делать».

В работах [2-4] приведены графы переходов автоматов, которые сгенерированы с помощью генетических алгоритмов. Так, в [3] приведен автомат, который решает рассматриваемую задачу за 200 ходов и содержит 13 состояний. В [2] приведен автомат, граф переходов которого содержит 11 состояний, и позволяет, по утверждению авторов, съесть муравью всю еду за 193 хода. В [4] приведен автомат, содержащий 8 состояний и позволяющий муравью съесть всю еду за 193 хода. В [2] показано, что указанный выше автомат с 13 состояниями был найден в результате генерации 52 поколений, в течение которых было построено более трех миллионов автоматов, а построение автомата с 11 состояниями потребовало от 418 до 4051 поколений. При этом при переборе строилось от 63000 до 607950 автоматов. Ниже описывается алгоритм генетического программирования [6], который строит автомат с восемью состояниями, перебирая при этом от 200000 до 1500000 автоматов. Этот же алгоритм позволил построить автомат с семью состояниями за 130000 поколений. Перебор при этом осуществлялся среди 160 миллионов автоматов.

2. Описание алгоритма генетического программирования

Разработанный алгоритм генетического программирования состоит из пяти частей:

· создание начального поколения;

· мутация;

· скрещивание (кроссовер);

· отбор особей для формирования следующего поколения;

· вычисление функции приспособленности (фитнес-функции).

Каждая особь представляет собой некоторый автомат, описывающий поведение муравья. Хромосома особи состоит из номера начального состояния и описаний состояний. Описание состояния содержит описания двух переходов, соответствующих тому, что перед муравьем либо есть еда, либо ее нет. Описание перехода состоит из номера состояния, в которое он ведет, и действия, выполняемого при выборе этого перехода. Хромосома представляется не в виде битовой строки, как в генетических алгоритмах, а в виде объекта в языке программирования Java. Этот объект имеет описанную структуру:

public class Automaton {

public Transition[][] transitions;

public int initialState;

public int stateCount;

}

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

Мутация. При мутации случайно выбирается один из четырех равновероятных вариантов:

· изменение начального состояния - в этом случае новое начальное состояние

выбирается случайно и равновероятно;

· изменение действия на переходе - случайно и равновероятно выбирается переход, и действие на нем изменяется на случайное. При этом все возможные действия равновероятны;

· изменение состояния, в которое ведет переход, - случайно и равновероятно выбирается переход. После этого состояние, в которое ведет переход, заменяется на случайно выбранное состояние;

· изменение условия на переходе - случайно и равновероятно выбирается состояние.

После этого переходы из этого состояния, соответствующие условиям «Перед муравьем есть еда» и «Перед муравьем нет еды», меняются местами.

Скрещивание. Оператор скрещивания получает на вход две особи и выдает также две особи. Процесс скрещивания происходит следующим образом. Обозначим родительские особи P1 и P2, а потомков - S1 и S2. Обозначим начальное состояние автомата A как A.is. Тогда для потомков S1 и S2 будет верно одно из двух: либо S1.is = P1.is и S2.is = P2.is, либо S1.is = P2.is и S2.is = P1.is, причем оба варианта равновероятны. Опишем, как «устроены» переходы автоматов-потомков S1 и S2 -может быть реализован один из двух равновероятных вариантов.