1.3.Применение генетических алгоритмов для построения конечных автоматов
В данном разделе приведены примеры задач, в которых применение эволюционных алгоритмов для автоматизированного построения автоматов позволило улучшить существующие решения или получить решения, сравнимые по эффективности с существующими. Кроме того, следует принять во внимание, что трудозатраты человека при подходе, базирующемся на эволюционных алгоритмах, как правило, значительно меньше, чем при эвристическом построении автоматов. Важно отметить и то обстоятельство, что в некоторых случаях автоматизировано построенные автоматы могут быть изучены для выявления структуры «хороших» решений задачи.
При использовании эволюционных методов не требуется точно указывать, как решать задачу. Вместо этого достаточно ее сформулировать в терминах некоторой «цели» и «допустимых затрат», программа будет создана самой вычислительной системой в ходе эволюционного процесса. Высказывание «машина никогда не знает больше программиста» при этом оказывается просто неверным.
1.3.1.Эксперименты Фогеля
Один из создателей эволюционного программирования Л.Фогель рассматривал интеллектуальное поведение индивида, как способность успешно предсказывать поведение среды, в которой он находится, и сообразно с этим действовать. В 60-x годах прошлого века Фогель поставил ряд экспериментов [39] по созданию искусственных систем, способных адаптироваться к первоначально не известной им среде.
В проведенных экспериментах Л. Фогель моделировал поведение простейшего живого существа, которое способно предсказывать изменения параметра среды, обладающего периодичностью. Это живое существо моделировалось конечным автоматом с действиями на переходах – автоматом Мили. В качестве среды выступала последовательность символов над двоичным алфавитом, например, (1111010010)*. На вход автомата в каждый момент времени подавалась битовое значение параметра окружающей среды. Автомат формировал значение выходной переменной – возможное значение рассматриваемого параметра в следующий момент времени. На Рис. 3. приведен один из возможных автоматов, который построен для распознавания, указанной выше последовательности.
|
Граф переходов эвристически построенного автомата
|
Задача состояла в эволюционном построении автомата, способного как можно более точно в смысле какой-либо разумной функции приспособленности от входа и выхода (например, числа совпавших символов) предсказывать среду – угадывать следующий символ последовательности. Кроме того, Фогель накладывал ограничения на сложность порождаемого автомата, так как строить автоматы равные длине обозреваемой последовательности не представляет труда. Таким образом, предпочтение отдавалось автоматам, угадывающим как можно лучше, и в то же время имеющим как можно меньше состояний.
В начале эксперимента задавалась периодическая последовательность символов над двоичным алфавитом, например (101110011101)*. На начальной фазе выбирался префикс данной последовательности малой длины. После этого создавалась популяция автоматов с небольшим числом состояний (около пяти). Затем каждый из автоматов путем одной из пяти мутаций (выбираемой случайным образом равномерно) производил потомка. Далее над потомком подобным образом производилось еще несколько мутаций (их число определялось случайным образом). Получившийся в результате мутаций автомат добавлялся в популяцию. Были допустимы следующие мутации автомата:
добавление состояния;
удаление состояния (в случае, если число состояний больше единицы);
замена стартового состояния (в случае, если число состояний больше единицы);
замена перехода;
замена действия на переходе.
После добавления потомков в популяцию на всех ее особях вычислялась функция приспособленности. Половина наиболее приспособленных особей переносилась в популяцию следующего поколения, а менее приспособленные автоматы – отбрасывались. Таким образом, размер популяции оставался постоянным (стоит отметить, что в силу ограниченных возможностей компьютеров того времени, он был мал – всего несколько особей). Данный процесс продолжался до тех пор, пока не удавалось достигнуть желаемого результата – максимальное значение функции приспособленности не превосходило заданного порога. После этого к битовой последовательности, которая определяла среду, добавлялся очередной символ, и эволюционный процесс переходил в очередную фазу.
По мнению Л. Фогеля, результаты экспериментов показали, что эволюционное программирование может быть успешно применено для построения «интеллектуальных» искусственных систем. При этом было отмечено, что построение вручную автоматов столь же результативных и простых, как те, что были построены эволюционным алгоритмом, является крайне сложной задачей.
1.3.2.Задача «Умный муравей»
Приведем описание задачи «Умный муравей» на основе работ [46, 28]. Используется двумерный тор размером 32 на 32 клетки (Рис. 4.). На некоторых клетках поля расположены яблоки – черные клетки на Рис. 4.. Яблоки расположены вдоль некоторой ломаной линии, но не на всех ее клетках. Клетки ломаной, на которых яблок нет – серые. Белые клетки – не принадлежат ломаной и не содержат яблок. Всего на поле 89 яблок.
|
Поле с яблоками
|
В клетке с пометкой «Start» находится муравей. Он занимает клетку поля и смотрит в одном из четырех направлений (север, запад, юг, восток). В начале игры муравей смотрит на восток. Он умеет определять, находится ли яблоко непосредственно перед ним. За ход муравей совершает одно из четырех действий:
идет вперед на одну клетку, съедая яблоко, если оно находится перед ним;
поворачивается вправо;
поворачивается влево;
стоит на месте.
Съеденные муравьем яблоки не восполняются. Муравей жив на всем протяжении игры – еда не является необходимым ресурсом для его существования. Никаких других персонажей, кроме муравья, на поле нет. Ломаная строго задана. Муравей может ходить по любым клеткам поля. Игра длится 200 ходов, на каждом из которых муравей совершает одно из четырех описанных выше действий. В конце игры подсчитывается количество яблок, съеденных муравьем. Это значение – результат игры.
Цель игры – создать муравья, который за 200 ходов съест как можно больше яблок. Муравьи, съевшие одинаковое количество яблок, заканчивают игру с одинаковым результатом вне зависимости от числа ходов, затраченных каждым из них на процесс еды. Однако эта задача может иметь различные модификации, например, такую, в которой при одинаковом количестве съеденных яблок, лучшим считается муравей, съевший яблоки за меньшее число ходов. Ниже будет показано, что поведение муравья может быть задано конечным автоматом. При этом может быть поставлена задача о построении автомата с минимальным числом состояний для муравья, съедающего все яблоки, или автомата для муравья, съедающего максимальное количество яблок при заданном числе состояний.
Конечный автомат, изображенный на Рис. 5., содержит всего пять состояний.
|
Конечный автомат, задающий муравья
|
Этот автомат описывает поведение муравья, который не решает задачу – за 200 ходов съедает только 81 яблоко, а за 314 ходов — все 89 яблок. Муравей действует по принципу «Вижу яблоко – иду вперед. Не вижу – поворачиваю направо. Сделал круг, но яблок нет – иду вперед».
Приведем автомат (Рис. 6.), который построен в работе [46] с помощью генетических алгоритмов и решает поставленную задачу.
|
Конечный автомат с 13 состояниями, задающий муравья, съедающего все яблоки за 200 ходов
|
На этом рисунке используются следующие обозначения: N – непосредственно перед муравьем нет еды, F – непосредственно перед муравьем есть еда; M – идти вперед, L – повернуть налево, R – повернуть направо, NO – стоять на месте. Можно заметить, что действие NO никогда не выполняется. Данный автомат изображен некорректно – из одиннадцатого состояния изображен переход, помеченный входным воздействием 0, с «непонятным» действием S. Однако если это действие заменить на N, то автомат корректно решает задачу.
Автомат из работы [28], приведенный на Error: Reference source not found, содержит 11 состояний. По утверждению авторов, он съедает все яблоки за 193 хода.
|
Конечный автомат с 11 состояниями, задающий муравья, съедающего все яблоки за 193 хода
|
Для генерации конечных автоматов, задающего муравья, в работах [28, 46] были применены генетические алгоритмы. В работе [46] приспособленность особи (fitness) определяется как количество яблок, съеденное за 200 ходов. Кодирование автомата, задающего поведение муравья, в особь генетического алгоритма (битовую строку) в этой работе осуществлялось следующим образом: входному воздействию F сопоставлялась единица, а N – ноль. Каждое из четырех действий муравья кодировалось двоичными числами: 00 – NO, 01 – L, 10 – R, 11 – M.
Покажем, как выполняется кодирование автомата в целом. На Рис. 8. приведен пример графа переходов автомата, описывающего поведение некоторого муравья.
|
Пример автомата, описывающего поведение муравья
|
Кодирование этого графа переходов приведено в табл. Таблица 1..
Кодирование графа переходов
|
Состояние
|
Вход
|
Новое состояние
|
Действие
|
00
|
0
|
01
|
01
|
00
|
1
|
00
|
11
|
01
|
0
|
01
|
10
|
01
|
1
|
10
|
11
|
10
|
0
|
11
|
00
|
10
|
1
|
10
|
11
|
11
|
0
|
00
|
01
|
11
|
1
|
11
|
10
|
Преобразуем эту таблицу в битовую строку. Для этого сначала требуется запомнить число состояний автомата (в данном случае четыре). В начале строки задан двоичный номер начального состояния автомата (в данном примере – 00). Далее записаны пары (Новое состояние, Действие). Содержимое полей (Состояние, Вход) не записываются, так как они повторяются для каждого автомата с фиксированным числом состояний. Для рассматриваемого примера искомая строка имеет вид:
00 0101 0011 0110 1011 1100 1011 0001 1110
Здесь курсивом выделены биты, соответствующие новому состоянию, а обычным шрифтом — биты, соответствующие выполняемому на переходе действию. Жирным шрифтом выделены биты, кодирующие начальное состояние.
Отметим, что автором настоящей диссертации в бакалаврской работе [24] был предложен генетический алгоритм, с помощью которого был построен автомат, содержащий семь состояний и решающий задачу об «Умном муравье». Диаграмма переходов этого автомата приведена на Рис. 9.. В работе [26] с помощью перебора показано, что автоматы с меньшим, чем семь числом состояний задачу «Умный муравей» решить не могут.
|
Автомат, решающий задачу «Умный муравей»
|
Отметим, что в книге [49] создатель генетического программирования J. R. Koza предлагает другой подход к представлению автомата, нежели кодирование с помощью битовой строки, – поведение муравья задается в виде дерева разбора, которое далее может быть преобразовано в автомат. Апробация этого метода проводилась на другом игровом поле – Santa Fe Trail.
1.3.3.Построение конечных детерминированных автоматов для распознавания регулярных языков
Из теории формальных языков известно, что конечные детерминированные автоматы способны распознавать регулярные языки [23]. В связи с этим актуальна задача построения автомата, распознающего по множеству примеров некий язык. Для решения этой задачи успешно применялись различные генетические алгоритмы.
Задача может быть усилена до построения автомата с минимальным количеством состояний. Однако, в работе [41] показано, что эта задача является NP-трудной.
В работе [32] автоматы представлялись с помощью таблицы переходов. Разработанный в этой работе метод позволяет поддерживать в популяции автоматы с разным числом состояний. Функция приспособленности учитывает три компонента – количество верно распознанных тестовых примеров, количество состояний и переходов автомата, степень общности языка, соответствующего построенному автомату. Это позволяет сузить область поиска, и находить языки, соответствующие определенным критериям. В тестовую коллекцию могут входить примеры слов, которые как принадлежат, так и не принадлежат языку.
Приведем описание генетической операции репродукции. Число состояний потомка выбирается случайно из диапазона [N – 2, N + 2], где N — число состояний первого родителя. После этого каждый переход копируется из родителей, причем вероятность копирования перехода из заданной особи прямо пропорциональна значению ее функции приспособленности. Переходы, представленные только в одном из родителей, копируются из того родителя, в котором присутствуют. Переходы, отсутствующие в обоих родителях, генерируются случайно.
Генетическая операция мутации осуществляется изменением случайного перехода. При этом переход разрешается удалять. Это приводит к распаду графа переходов на несколько компонент. Результаты экспериментов показали, что удаление недостижимых состояний замедляет вывод – поэтому оно не производится.
Предложенный подход был проверен на практических задачах. Авторам удалось построить автомат из семи состояний, который распознает по множеству из ста примеров русские двухсложные слова.
В работе [34] для генерации автомата был применен следующий вариант генетического программирования: выводилось выражение, результатом вычисления которого являлся автомат. Выражение описывало последовательность действий, преобразующих исходный автомат (Error: Reference source not found) в результирующий. Для вывода выражений, кодирующих развитие автомата, было применено традиционное генетическое программирование, оперирующее над деревьями выражений.
|
Исходный автомат
|
Опишем процесс преобразования автомата. Построение автомата является неким аналогом онтогенеза – перехода клетки в организм путем деления и модификации. В каждый момент некая дуга автомата является активной. Операции, используемые в выражении, могут делить активную дугу или модифицировать ее, выбрав при этом другую дугу в качестве активной. Авторами этой работы вводятся следующие нетерминалы:
PARALLEL – создать новое допускающее состояние автомата и направить туда активную дугу. При этом созданное состояние копируется из состояния, в которое активная дуга вела до операции;
PARALLEL-REJ – создать новое отвергающее состояние и направить туда активную дугу аналогично PARALLEL;
RETRACT – зациклить активную дугу: направить ее в состояние, из которого она исходит;
WRITE-NODE – положить в стек состояние, в которое ведет активная дуга;
TO-NODE – снять состояние со стека и направить в него активную дугу. Если стек пуст, то активная дуга не модифицируется.
В работе [34] введен единственный терминал DONE, означающий конец редактирования. Пример выражения, использующего эти функции, приведен на Error: Reference source not found. Для наглядности нетерминалы пронумерованы в порядке исполнения. Для нетерминалов PARALLEL и PARALLEL-REJ первый аргумент соответствует действиям, совершаемым над созданным состоянием. При этом активная дуга переходит в первую дугу, исходящую из нового состояния. Второй аргумент этих нетерминалов соответствует действиям, совершаемым над исходным состоянием. При этом активная дуга заменяется следующей дугой, исходящей из состояния. Для остальных нетерминалов единственный аргумент вычисляется аналогично второму аргументу PARALLEL и PARALLEL-REJ.
|
Выражение, описывающее развитие автомата
|
На Error: Reference source not found показан процесс развития автомата из исходного по приведенному выражению.
|
Процесс построения автомата при вычислении выражения
|
Известно, что регулярные языки могут быть представлены как объединение, пересечение или дополнение других регулярных языков. Следовательно, можно произвести декомпозицию языка на более простые языки, для которых проще найти распознающие автоматы. В работе [34] определено решение в виде комбинации трех автоматов через нетерминалы AND, OR и NOT. Разложение также определяется с помощью генетического программирования. Пример выведенного с помощью этой методики распознавателя изображен на Error: Reference source not found.
|
Декомпозиция распознавателя
|
Описанный подход был протестирован на наборе из девяти регулярных языков. К сожалению, для одного из тестовых языков так и не удалось построить автоматический распознаватель.
В работе [51] произведено сравнение двух подходов к автоматическому построению автоматов: использование генетических алгоритмов и применение эвристики Evidence Driven State Merging (EDSM). После анализа проведенных экспериментов был сделан вывод, что автомат, построенный с помощью генетических алгоритмов, лучше соответствует искомому языку. С другой стороны, эвристика EDSM всегда строит автомат, который верно распознает множество примеров.
Кроме этого, в работе [53] предлагается подход, позволяющий существенно сократить пространство поиска в задаче построения конечного автомата для распознавания регулярного языка. Этот подход состоит в том, что в хромосоме генетического алгоритма кодируется только структура автомата, а его вершины помечаются одним из значений – «допускающее состояние» или «не допускающее состояние» – с помощью процедуры, которую авторы работы назвали «расстановкой пометок» (smart state labeling). Применение этого подхода позволило существенно ускорить работу генетического алгоритма.
1.3.4.Построение конечных преобразователей
Одной из областей применения автоматического построения автоматов является построение конечных преобразователей (Finite State Transducers), которые преобразуют входной поток в последовательность символов выходного алфавита. На Рис. 14. приведен пример простого преобразователя двоичной записи числа N в двоичную запись числа N + 1. При этом двоичная запись числа подается с конца.
|
Простой пример конечного преобразователя
|
Более сложным примером использования автоматических преобразователей является синтез речи — отображение последовательности букв в последовательность фонем. Важным достоинством применения конечных автоматов для описания преобразователей является легкость их реализации.
Как правило, в задаче построения конечного преобразователя исходными данными является «обучающее множество»: пары последовательностей символов, которые состоят из входной последовательности и соответствующей ей выходной последовательности. Задача же состоит в построении конечного преобразователя, который содержит заданное число состояний и корректно преобразует последовательности, входящие в обучающее множество.
В работе [57] предлагается метод генетического программирования для построения конечных автоматов, реализующих преобразователи. Автоматы в этой работе представляются в виде графов переходов, генетические операции определяются аналогично генетическим операциям над абстрактными помеченными графами. При этом ребра помечаются входным и выходным воздействиями.
Приведем описание операции рекомбинации. В используемом методе оператор рекомбинации принимает на вход две особи и возвращает две порожденных особи. Используется следующий алгоритм.
В двух рекомбинируемых графах выбирается по одной случайной вершине.
Подграфы, соответствующие вершинам меняются местами.
Ребра, которые ведут наружу, направляются в случайные вершины.
На Рис. 15. приведен пример рекомбинации.
|
Пример рекомбинации графов переходов
|
Операция мутации реализуется следующим образом.
Выбирается случайная вершина графа.
Подграф, соответствующий выбранной вершине, удаляется.
Из вершины выращивается случайный подграф.
Определенные таким образом генетические операции часто порождают потомство, имеющее меньшее значение функции приспособленности, чем у родителей. Для того чтобы исключить это, реализуется следующая эвристика: генетические операции повторяются, пока не будет построено потомство, превосходящее родителей. Если же после фиксированного числа итераций приемлемого результата не достигается, то родители переходят в следующую популяцию.
Предложенный подход был проверен на шести простых задачах построения преобразователей. Результаты экспериментов подтверждают работоспособность метода.
В работе [52] выполняется сравнение эволюционных алгоритмов и методов, основанных на эвристическом объединении состояний. При этом конечные преобразователи представлены в генетическом алгоритме с помощью двух таблиц: функции переходов и функции выходов.
Кроме этого, исследуются три подхода к вычислению функции приспособленности – на основе строго сравнения выходной последовательности с последовательностью из «обучающего множества», на основе вычисления расстояния Хэмминга [43] и на основе вычисления редакционного расстояний (расстояния Левенштейна) [9]. Из этих трех методов наиболее эффективным оказался метод, основанный на редакционном расстоянии.
Результаты этой работы показывают, что наиболее эффективно (для рассмотренных в этой работе) примеров работает алгоритм RMHC (random mutation hill climber), использующий только операцию мутации. Вторым по эффективности является генетический алгоритм, а наименее эффективно работает эвристическое объединение состояний.
Отметим также, что задача построения конечного преобразователя, корректно преобразующего заданный «тренировочный» набор последовательностей, является одним из видов машинного обучения [14], поэтому указанные работы (а также настоящая работа, в которой рассматривается похожая задача) могут быть отнесены к этому разделу искусственного интеллекта.
1.3.5.Работы в СПбГУ ИТМО
В рамках исследований по теме «Технология генетического программирования для генерации автоматов управления системами со сложным поведением» на кафедре «Технологии программирования» СПбГУ ИТМО был разработан ряд методов генерации конечных автоматов с помощью генетических алгоритмов.
Один из этих методов – метод сокращенных таблиц переходов был предложен Н. Поликарповой и В. Точилиным в работе [17]. Этот метод позволяет решить проблему экспоненциального роста размера описания автомата, которая возникает при использовании полных таблиц переходов – число строк в таблице есть  , где  – число предикатов. Опыт показывает, что в реальных задачах управляющие автоматы, построенные вручную, имеют гораздо меньше переходов, чем  (здесь как |S| обозначено размер множества состояний автомата). Причина этого состоит в том, что в большинстве задач предикаты имеют «локальную природу» по отношению к управляющим состояниям. В каждом состоянии значимым является лишь определенный, небольшой поднабор предикатов, остальные же не влияют на значение управляющей функции. Именно это свойство позволяет существенно сократить размер описания состояний. Кроме того, использование этого свойства в процессе оптимизации позволяет получить результат, более похожий на автомат, построенный вручную, а следовательно, и более понятный человеку.
Свойство локальности предикатов можно применять для сокращения описания управляющего состояния разными способами. При разработке метода сокращенных таблиц был выбран один из подходов, при котором число значимых в состоянии предикатов ограничивается некоторой константой  .
К таблице, задающей сужение управляющей функции на данное состояние, в этом случае добавляется битовый вектор, описывающий множество значимых предикатов (Рис. 16.).
|
Хромосома состояния: сокращенная таблица (n = 6, m = 3, r = 2, |S| = 3)
|
Число строк таблицы в этом случае  , однако, константа обычно невелика. Ее выбор зависит от сложности задачи. Как показывает опыт, для большинства автоматизированных объектов среднее по всем состояниям значение не больше пяти.
Второй метод – метод представления автоматов деревьями решений предложен В. Даниловым в работах [6, 7]. Дерево решений является удобным способом задания дискретной функции, зависящей от конечного числа логических переменных. Оно представляет собой помеченное дерево, метки в котором расставлены по следующему правилу:
внутренние узлы помечены символами переменных;
ребра – значениями переменных;
листья – значениями искомой функции.
Для определения значения функции по значениям переменных необходимо спуститься от корня до листа, и сформировать значение, которым помечен полученный лист. При этом из вершины, помеченной переменной x, переход производится по тому ребру, которое помечено тем же значением, что и значение переменной x.
Метод представления автомата с помощью деревьев решений заключается в следующем: функции переходов и выходов автомата выражаются с помощью деревьев решений. Более формально: зададим для каждого состояния  функцию  , такую что  для  . Здесь  – множество состояний автомата,  – множество входных воздействий,  – множество выходных воздействий,  – функция переходов,  – функция выхода. Каждая из этих функций может быть определена собственным деревом решений. Таким образом, автомат в целом может быть представлен упорядоченным набором деревьев решений и стартовым состоянием.
Каждое состояние автомата представляется с помощью соответствующего дерева решений. Деревья решений состоят из узлов, среди которых выделяется корень. Каждый узел представляется следующим образом:
номер переменной, соответствующей метке узла;
указатель на дочерний узел, соответствующий нулевому значению переменной (для внутренних узлов);
указатель на дочерний узел, соответствующий единичному значению переменной (для внутренних узлов);
ассоциированное выходное действие (для листьев);
номер состояния, в которое ведет переход из данной вершины (для листьев).
Следовательно, при использовании описываемого метода автомат представляется объектом следующего вида на языке Java:
class TreeAutomata {
Tree[] trees;
int startState;
}
class Tree {
Node root;
private class Node {
Node left;
Node right;
int transState;
int action;
}
}
Третий метод – метод совместного применения конечных автоматов и нейронных сетей был предложен автором настоящей диссертации в работах [24, 25]. При использовании этого метода для управления системой со сложным поведением предлагается совместно применять нейронную сеть и конечный автомат, которые совместно строятся генетическим алгоритмом.
При этом, как отмечалось выше, нейронная сеть используется для классификации значений вещественных входных переменных и выработки входных логических переменных для автомата, а автомат – для выработки выходных воздействий на систему со сложным поведением (Рис. 17.).
|
Структурная схема системы управления при использовании метода совместного применения конечных автоматов и нейронных сетей
|
Одна из возможных структур нейронной сети и способ ее взаимодействия с конечным автоматом показаны на Рис. 18.. Отметим, что для решения других задач структура нейронной сети может быть изменена.
|
Возможная структура нейронной сеть и ее взаимодействие с конечным автоматом
|
Символами S на Рис. 18. обозначены нейроны с сигмоидальной функцией активации, символом L – нейроны с пороговой функцией активации. Рядом с нейронами указаны их номера (они используются при описании операции скрещивания нейронных сетей). На каждый из трех выходов нейронной сети поступает число равное нулю или единице. Таким образом, существует восемь вариантов комбинаций выходных сигналов нейронной сети (000, 001, 010, 011, 100, 101, 110, 111), подаваемых на вход конечного автомата.
Указанные методы применялись для построения конечных автоматов управления моделью беспилотного летательного аппарата. При этом в ряде случаев построенные автоматы были более эффективными, чем построенные вручную [18].
1.3.6.Другие работы по построению конечных автоматов с помощью генетических алгоритмов
Кроме указанных выше задач, генетические алгоритмы успешно применяются для построения автоматов в следующих задачах:
итерированная дилемма узника (теория игр) [30, 37];
распознавание изображений [33];
автоматические переговоры [57, 60];
управление человекоподобным роботом [61].
|
