«Методы построения конечных автоматов на основе эволюционных алгоритмов ...»

Санкт-Петербургский национальный исследовательский университет

информационных технологий, механики и оптики

На правах рукописи

Царев Федор Николаевич

Методы построения конечных автоматов на основе

эволюционных алгоритмов

Специальность 05.13.11 – Математическое и программное обеспечение

вычислительных машин, комплексов и компьютерных сетей

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель:

доктор технических наук, профессор А. А. Шалыто Санкт-Петербург – 2012 г.

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. АВТОМАТНОЕ ПРОГРАММИРОВАНИЕ И

ПОИСКОВАЯ ИНЖЕНЕРИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ.......... 1.1. АВТОМАТНОЕ ПРОГРАММИРОВАНИЕ

1.1.1. Сущности со сложным поведением

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

1.1.3. Управляющий конечный автомат

1.1.4. Верификация автоматных программ на основе метода Model Checking

1.2. ПОИСКОВАЯ ИНЖЕНЕРИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ

1.2.1. Основные понятия

1.2.2. Метод спуска

1.2.3. Эволюционная стратегия

1.2.4. Генетические алгоритмы

1.3. ПРИМЕНЕНИЕ ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ ДЛЯ ПОСТРОЕНИЯ

КОНЕЧНЫХ АВТОМАТОВ

1.3.1. Методы, использующие моделирование при вычислении функции приспособленности

1.3.2. Методы, использующие обучающие примеры при вычислении функции приспособленности

1.3.3. Методы, использующие верификацию при вычислении функции приспособленности

1.3.4. Анализ эволюционных алгоритмов построения автоматов.... 1.4. ЗАДАЧИ, РЕШАЕМЫЕ В ДИССЕРТАЦИОННОЙ РАБОТЕ

ВЫВОДЫ ПО ГЛАВЕ 1

ГЛАВА 2. МЕТОДЫ ПОСТРОЕНИЯ УПРАВЛЯЮЩИХ

КОНЕЧНЫХ АВТОМАТОВ НА ОСНОВЕ ЭВОЛЮЦИОННЫХ

АЛГОРИТМОВ ПО ОБУЧАЮЩИМ ПРИМЕРАМ И ТЕМПОРАЛЬНЫМ

ФОРМУЛАМ

2.1. МЕТОД ПОСТРОЕНИЯ УПРАВЛЯЮЩИХ КОНЕЧНЫХ АВТОМАТОВ ПО

ОБУЧАЮЩИМ ПРИМЕРАМ НА ОСНОВЕ ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ................ 2.1.1. Входные данные

2.1.2. Выходные данные

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

2.1.4. Алгоритм расстановки выходных воздействий

2.1.5. Вычисление функции приспособленности

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

2.1.7. Операция удаления дублированных и противоречивых переходов

2.1.8. Операция мутации, использующаяся в эволюционной стратегии

2.1.9. Генетический алгоритм

2.1.10. Операция скрещивания

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

2.2. МЕТОД ВЫПОЛНЕНИЯ ОПЕРАЦИИ СКРЕЩИВАНИЯ С УЧЕТОМ

ПОВЕДЕНИЯ АВТОМАТОВ НА ОБУЧАЮЩИХ ПРИМЕРАХ

2.3. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ МЕТОДОВ ПОСТРОЕНИЯ

УПРАВЛЯЮЩИХ АВТОМАТОВ ПО ОБУЧАЮЩИМ ПРИМЕРАМ НА ОСНОВЕ

ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ

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

2.4. МЕТОД ПОСТРОЕНИЯ АВТОМАТОВ ПО ОБУЧАЮЩИМ ПРИМЕРАМ И

ТЕМПОРАЛЬНЫМ ФОРМУЛАМ НА ОСНОВЕ ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ И

ВЕРИФИКАЦИИ

2.4.1. Входные данные

2.4.2. Выходные данные

2.4.3. Представление конечного автомата в виде хромосомы эволюционного алгоритма

2.4.4. Вычисление функции приспособленности

2.4.5. Операции мутации и скрещивания

2.5. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ МЕТОДА ПОСТРОЕНИЯ

АВТОМАТОВ ПО ОБУЧАЮЩИМ ПРИМЕРАМ И ТЕМПОРАЛЬНЫМ ФОРМУЛАМ........ ВЫВОДЫ ПО ГЛАВЕ 2

ГЛАВА 3. ТЕХНОЛОГИЯ И ИНСТРУМЕНТАЛЬНОЕ СРЕДСТВО

ПОСТРОЕНИЯ УПРАВЛЯЮЩИХ КОНЕЧНЫХ АВТОМАТОВ НА

ОСНОВЕ ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ И ВЕРИФИКАЦИИ........

3.1. ТЕХНОЛОГИЯ ПОСТРОЕНИЯ УПРАВЛЯЮЩИХ КОНЕЧНЫХ АВТОМАТОВ

НА ОСНОВЕ ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ И ВЕРИФИКАЦИИ

3.2. ИНСТРУМЕНТАЛЬНОЕ СРЕДСТВО ДЛЯ АВТОМАТИЗИРОВАННОГО

ПОСТРОЕНИЯ УПРАВЛЯЮЩИХ КОНЕЧНЫХ АВТОМАТОВ

3.2.1. Формат входных данных

3.2.2. Формат выходных данных

3.2.3. Структура программной реализации

ВЫВОДЫ ПО ГЛАВЕ 3

ГЛАВА 4. ВНЕДРЕНИЕ РЕЗУЛЬТАТОВ РАБОТЫ

4.1. ВНЕДРЕНИЕ РАЗРАБОТАННЫХ МЕТОДОВ НА ПРИМЕРЕ ПОСТРОЕНИЯ

АВТОМАТА УПРАВЛЕНИЯ МОДЕЛЬЮ БЕСПИЛОТНОГО САМОЛЕТА

4.1.1. Описание объекта управления

4.1.2. Входные переменные и события

4.1.3. Набор обучающих примеров

4.1.4. Вычисление функции приспособленности

4.1.5. Модифицировнный алгоритм расстановки выходных воздействий

4.1.6. Результаты построения автомата

4.2. ВНЕДРЕНИЕ РЕЗУЛЬТАТОВ РАБОТЫ В УЧЕБНЫЙ ПРОЦЕСС

4.2.1. Виртуальная лаборатория на языке Java

4.2.2. Виртуальная лаборатория на языке C#

4.2.3. Применение виртуальных лабораторий в учебном процессе.. ВЫВОДЫ ПО ГЛАВЕ 4

ЗАКЛЮЧЕНИЕ

СПИСОК ИСТОЧНИКОВ

ПЕЧАТНЫЕ ИЗДАНИЯ НА РУССКОМ ЯЗЫКЕ

ПЕЧАТНЫЕ ИЗДАНИЯ НА АНГЛИЙСКОМ ЯЗЫКЕ

РЕСУРСЫ СЕТИ ИНТЕРНЕТ

ПУБЛИКАЦИИ АВТОРА

Статьи в журналахиз перечня ВАК

Другие статьи автора

Материалы конференций с участием автора

ПРИЛОЖЕНИЕ 1. СВИДЕТЕЛЬСТВА О РЕГИСТРАЦИИ

ПРОГРАММ ДЛЯ ЭВМ

ПРИЛОЖЕНИЕ 2. ПРИМЕР ОТЧЕТА ПО ЛАБОРАТОРНОЙ

РАБОТЕ

ВВЕДЕНИЕ

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

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

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

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

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

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

При использовании автоматного программирования существенно упрощается (по сравнению с программами, написанными традиционными методами) верификация программ с использованием метода Model checking [6, 9, 125, 56], так как построение модели Крипке по автоматной программе может быть автоматизировано [125]. Кроме этого, при использовании инструментальных средств для поддержки автоматного программирования таких, как, например, UniMod [3], до 70% исходного кода автоматной программы может быть сгенерировано автоматически [27, 137]. Уровень автоматизации программирования этого класса программ станет значительно выше, если удастся автоматизировать процесс построения управляющих конечных автоматов, что и является предметом исследования в настоящей работе.

В последнее десятилетие активно развивается область исследований, называемая поисковая инженерия ПО (Search-Based Software Engineering, SBSE) [45, 69 – 71], в рамках которой для решения задач программной инженерии (включая анализ требований [37, 121], прогнозирование хода разработки [30], проектирование [110], тестирование [34, 67, 93] и рефакторинг [68, 106]) предлагается применять алгоритмы поисковой оптимизации. В число методов, которые нашли применение в поисковой инженерии ПО [69], входят эволюционные алгоритмы [7] (генетические эволюционные стратегии [40]), а также муравьиные алгоритмы [49], метод роя частиц [82], метод имитации отжига [94], метод спуска [66], алгоритмы оценки распределений [86], поиск с запретами [58], квадратичное программирование [105], целочисленное программирование [113], искусственные иммунные системы [47]. При этом в настоящее время наибольшее распространение получили эволюционные алгоритмы [71].

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

беспилотных летательных аппаратом в соревнованиях с другой командой [21, 136], итерированная дилемма узника [98], задача о «Флибах» [1, 53], задача «Умный муравей» [79]. Полный перебор управляющих конечных автоматов даже при их небольших размерах крайне трудоемок, а эвристическое их построение, как отмечено выше, не всегда дает приемлемые результаты.

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

Как отмечается в работе [69], большая часть работ в области поисковой инженерии ПО основана на использовании эволюционных алгоритмов, а для решения задач проектирования ПО (к которым относится задача построения конечных автоматов) применялись только эволюционные и муравьиные алгоритмы, методы имитации отжига и спуска. Так как метод имитации отжига не дает существенного улучшения результатов по сравнению с генетическими алгоритмами [8, 124], а муравьиные алгоритмы более приспособлены для задач, в которых решением является путь в графе, то для решения задачи построения конечных автоматов обычно применялись эволюционные алгоритмы и метод спуска.

Подобные идеи возникали у ряда исследователей. В 1962 г.

Л. Фогель занялся изучением интеллектуального поведения индивида и его развития в процессе эволюции [52]. При этом поведение индивида задавалось конечным автоматом. Продолжая данные исследования, Л. Фогель, А. Оуэнс и М. Уолш предложили в 1966 г. схему эволюции конечных автоматов, решающих задачи предсказания [53].

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

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

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

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

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

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

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

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

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

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

Работа алгоритма считается оконченной, когда будет достигнуто необходимое значение функции приспособленности.

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

На каждой итерации рассматриваются точки, соседние с текущей. Если некоторая соседняя точка представляет собой улучшенное решение, то она становится текущей на следующей итерации. В противном случае поиск считается оконченным, а текущая точка – оптимальным решением.

программированием, рассматривались, прежде всего, методы, приспособленности [5, 14, 15, 17, 35, 53, 73, 76, 79, 95, 112, 114, 129 – 132, 135].

Эти методы обладают следующими недостатками:

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

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

«Математическое обеспечение вычислительных машин, комплексов и компьютерных сетей» областями исследования, к которым относится настоящая диссертация, в частности, являются «5. Теория построения программ, пакетов прикладных программ (ППП), программных комплексов (ПК), а также сетевых программ (СП), в том числе, поддерживающих сетевые протоколы» и «9. Модели и методы разработки программных средств обработки данных и знаний в ВМ, ВК и КС».

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

Основные задачи

диссертационной работы состоят в следующем:

1. Разработать метод построения автоматов по обучающим примерам на основе эволюционных алгоритмов.

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

5. Разработать инструментальное средство для автоматизации 6. Внедрить разработанные методы при построении автомата управления моделью беспилотного самолета и в учебный Научная новизна. В работе получены следующие новые научные результаты, которые выносятся на защиту:

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

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

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

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

Внедрение результатов работы. Результаты диссертации были получены при выполнении научно-исследовательских работ на кафедрах «Компьютерные технологии» и «Технологии программирования» НИУ ИТМО по следующим государственным контрактам: «Технология генетического программирования для генерации автоматов управления системами со сложным поведением» (государственный контракт № 02.514.11.4044 от 18.05.2007 г. по Федеральной целевой программе «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007–2013 годы»), «Разработка методов совместного применения генетического и автоматного программирования для построения систем управления беспилотными летательными аппаратами» (государственный контракт № П1188 от 27.08.2009 г. по Федеральной целевой программе «Научные и научно-педагогические кадры инновационной России» на 2009– годы), «Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных автоматов»

(государственный контракт № П2174 от 09.11.2009 г. по Федеральной целевой программе «Научные и научно-педагогические кадры инновационной России» на 2009–2013 годы), «Применение методов искусственного интеллекта в разработке управляющих программных систем» (государственный контракт № П2236 от 11.11.2009 г. по Федеральной целевой программе «Научные и научно-педагогические кадры инновационной России» на 2009–2013 годы), в рамках проекта «Подготовка и переподготовка профильных специалистов на базе центров образования и разработок в сфере информационных технологий в СевероЗападном федеральном округе» (Государственный контракт № 07.Р20.11.0028 от 07.09.2011 г.) и были внедрены на примере построения автомата управления моделью беспилотного самолета, а также в учебном процессе на кафедре «Компьютерные технологии» в рамках курса «Теория автоматов и программирование».

диссертационной работы докладывались на следующих научных и научнопрактических конференциях: IV Международная научно-практическая конференция «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Коломна, научно-техническая конференция «Научное программное обеспечение в образовании и конференция по проблемам науки и высшей школы «Фундаментальные исследования и инновации в технических университетах» (СПбГПУ, 2008), Second Spring Young Researchers' Colloquium on Software Engineering – SYRCoSE'2008 (SPbSU, 2008), III и IV Международная научнопрактическая конференция «Современные информационные технологии и ИТ-образование» (ВМК МГУ, 2008, 2009), научно-практическая конференция студентов, аспирантов, молодых ученых и специалистов «Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интеллекте (ИММВИИ-2009)»

(Коломна, 2009), VI и VII межвузовская конференция молодых ученых (СПбГУ ИТМО, 2009, 2010), X, XI и XII Международная конференции по мягким вычислениям и измерениям (СПбГЭТУ (ЛЭТИ), 2009, 2010, 2011), Международная научная конференция «Компьютерные науки и информационные технологии» памяти А. М. Богомолова (Саратовский государственный университет имени Н. Г. Чернышевского, 2009), 32-я конференция молодых ученых и специалистов Института проблем передачи информации им. А. А. Харкевича РАН «Информационные технологии и системы» (2009), XL научная и учебно-методическая конференция профессорско-преподавательского и научного состава СПбГУ ИТМО (2011), 14-th Annual Graduate Students Workshop (part of the «Genetic and Evolutionary Computation Conference» GECCO – 2011, Dublin, ACM SIGEVO, 2011), вторая межвузовская научная конференция по проблемам информатики (СПИСОК, СПбГУ, 2011), XLI научная и учебнометодическая конференция НИУ ИТМО (2012), 15-th Annual Graduate Students Workshop (part of the «Genetic and Evolutionary Computation Conference» GECCO – 2012, Philadelphia, ACM SIGEVO, 2012), третья российская конференция с международным участием «Технические и программные средства систем управления, контроля и измерения»

(Институт проблем управления имени В. А. Трапезникова РАН, 2012) – пленарный доклад.

Публикации. По теме диссертации опубликованы 23 печатные работы, в том числе шесть статей, из которых пять в журналах из перечня ВАК.

Свидетельства о регистрации программ для ЭВМ. В рамках диссертационной работы получены три свидетельства о регистрации программ для ЭВМ: № 2010 614197 от 29.06.2010 г. «Программное средство для построения управляющих конечных автоматов на основе обучающих примеров с использованием генетических алгоритмов», № 2011 615664 от 19.07.2011 г. «Программное средство для генерации конечных автоматов с дискретными и непрерывными выходными воздействиями», № 2011 616977 от 08.09.2011 г. «Виртуальная лаборатория для обучения методам искусственного интеллекта при построении конечных автоматов».

Структура диссертации. Диссертация изложена на 196 страницах и состоит из введения, четырех глав, заключения и двух приложений.

проиллюстрирована 41 рисунком и 14 таблицами.

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

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

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

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

диссертации.

ГЛАВА 1. АВТОМАТНОЕ ПРОГРАММИРОВАНИЕ И ПОИСКОВАЯ

ИНЖЕНЕРИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ

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

1.1. АВТОМАТНОЕ ПРОГРАММИРОВАНИЕ

посвященных автоматному программированию.

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

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

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

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

Вместо этого в автоматном программировании предлагается [18] описывать системы со сложным поведением, приписывая каждой из них некоторое множество управляющих состояний (в дальнейшем, если не оговаривается особо, состояний). В этих состояниях поведение системы является простым и может быть описано явно. Связь управляющих состояний с выходными воздействиями и механизм переходов между состояниями удобно описывать с помощью конечных автоматов с выходами [26]. При этом все описание поведения системы оказывается сосредоточенным в автомате или системе взаимодействующих автоматов.

Одним из наиболее широких классов систем, для которых целесообразно применять такой подход, являются реактивные системы.

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

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

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

Также как и в системах логического управления, в «реактивных»

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

системах число способов взаимодействия увеличилось.

1.1.2. Парадигма автоматного программирования Автоматное программирование, предложенное в работе [22], – это парадигма программирования, которая состоит в представлении сущностей со сложным поведением в виде автоматизированных объектов управления.

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

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

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

число управляющих состояний не очень велико, а число качественно, а управляющие – количественно;

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

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

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

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

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

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

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

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

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

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

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

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

предполагается, что управляющий автомат взаимодействует и с объектом управления, и с внешней средой (рис. 3).

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

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

Кроме того, объект управления может взаимодействовать с внешней средой напрямую.

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

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

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

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

1.1.3. Управляющий конечный автомат множество событий, Y – множество состояний, y0 – начальное состояние, функция переходов.

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

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

Если будильник выключен, то кнопки «H» и «M» предназначены, соответственно, для увеличения на единицу числа часов и минут в текущем времени. Кнопка «A» в этом режиме служит для перехода в режим настройки времени срабатывания будильника. В этом режиме кнопки «H» и «M» позволяют увеличивать на единицу число часов и минут во времени срабатывания будильника. Нажатие кнопки «A» в этом режиме приводит к включению будильника. Он срабатывает, как только время срабатывания совпадает с текущим временем. Звонок автоматически выключается через минуту или может быть выключен нажатием кнопки «A», которая также выключает будильник. Кроме кнопок часы содержат таймер, который срабатывает каждую минуту – при каждом его срабатывании текущее время увеличивается на одну минуту.

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

Эта система имеет четыре события:

H – нажата кнопка «H» на корпусе часов;

M – нажата кнопка «M» на корпусе часов;

A – нажата кнопка «A» на корпусе часов;

Она также содержит две входные переменные:

x1 – верно ли, что время срабатывания будильника совпадает с срабатывания будильника ровно на одну минуту?

Система имеет семь выходных воздействий:

z1 – увеличить на единицу число часов текущего времени;

z2 – увеличить на единицу число минут текущего времени;

z3 – увеличить на единицу число часов времени срабатывания z4 – увеличить на единицу число минут времени срабатывания z5 – прибавить минуту к текущему времени;

z6 – включить звонок будильника;

z7 – выключить звонок будильника.

На рис. 5 приведен граф переходов автомата управления часами с будильником из работы [22].

Рис. 5. Граф переходов конечного автомата управления часами с Начальным состоянием этого автомата является состояние «1. Будильник выключен». На приведенном графе переходов каждый переход t помечен событием e, логической формулой f относительно входных переменных (она выражает условие перехода и приведена в квадратных скобках) и последовательностью o выходных воздействий (приведена после косой черты). Переход t выполняется в случае поступления события e, если при подстановке значений входных переменных в формулу f ее значение есть «истина». При выполнении этого перехода генерируются выходные воздействия, составляющие последовательность o, а автомат переходит в состояние, в которое ведет переход t.

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

Отметим, что приведенный на рис. 5 автомат обладает свойством полноты, но не обладает свойством непротиворечивости, так как в состоянии «3. Будильник включен» при поступлении события T и одновременной истинности входных переменных x1 и x2 задано два перехода.

Если этот граф переходов исправить, как показано на рис. 6, то получится автомат, обладающий свойством непротиворечивости, но не обладающий свойством полноты, так как в этом случае не задано ни одного перехода из состояния «3. Будильник включен» при поступлении события T и одновременной истинности входных переменных x1 и x2.

Рис. 6. Исправленный граф переходов конечного автомата При этом отметим, что оба автомата корректно описывают поведение системы управления часами с будильником, так как из семантики входных переменных следует, что x1 и x2 не могут быть истинными одновременно. Это означает, что даже если некоторый непротиворечивостью и полнотой переходов, то он все равно может поведением.

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

1.1.4. Верификация автоматных программ на основе метода Метод проверки того, что программная система удовлетворяет применимым на практике методом верификации в настоящее время является верификация моделей программ (Model Checking) [9, 73]. При использовании этого метода процесс верификации состоит из трех этапов.

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

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

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

Рис. 7. Процесс верификации программы При использовании автоматного программирования проблемы построения модели по программе и преобразования контрпримеров из терминов модели в термины программы не возникают, так как конечный автомат может быть автоматически преобразован в модель, пригодную для верификации, а контрпримеры могут быть автоматически преобразованы из терминов модели в термины автомата [4, 125 – 128]. Эта особенность автоматных программ упрощает их верификацию по сравнению с программами, написанными традиционным путем.

Для верификации автоматных программ в работах [6, 125 – 128] было разработано несколько инструментальных средств. Некоторые из них использовали существующие верификаторы (например, SPIN [76], SMV [92], Bogor [143]) и осуществляли только преобразование в их входной язык, а инструментальное средство, предложенное в работе [6], использует собственную реализацию алгоритма верификации. Именно оно и использовалось в настоящей работе.

В указанном инструментальном средстве для описания утверждений, верификация которых проводится, используется логика линейного времени (Linear Time Logic, LTL) [9]. Синтаксис LTL включает в себя предикаты P, булевы связки (! – логическое «НЕ», & – логическое «И», || – логическое «ИЛИ») и темпоральные операторы, применяющиеся для составления утверждений о событиях в будущем.

В этой логике допустимы следующие темпоральные операторы:

X (neXt) – «X p» верно тогда, когда в следующий момент времени в программе будет выполняться предикат p;

G (Globally) – «G p» верно, если во время работы программы F (Future) – «F p» верно, если в будущем наступит момент, U (Until) – «p U q» верно, если в программе в каждый момент времени выполняется p до тех пор, пока не выполнится q. При этом q обязательно должно когда-либо выполниться;

R (Release) – «q R p» верно, если p выполняется до тех пор, пока не станет выполняться q (включая момент, когда выполнится q), или всегда, если q не выполнится никогда Множество LTL-формул таково:

требования к программе, преобразуется в автомат Бюхи [9] – конечный автомат над бесконечными словами. Переходы автомата Бюхи помечаются предикатами из исходной LTL-формулы. Методы построения автомата Бюхи по LTL-формуле описаны в работах [9, 44, 56].

Так как задача верификатора – найти контрпример, если он существует, то автомат Бюхи строится для отрицания исходной LTLформулы. Такой автомат допускает любые последовательности значений предикатов, которые не удовлетворяют требованиям.

Приведем несколько примеров автоматов Бюхи, построенных по LTL-формулам.

темпоральных операторов Future, Until и Release. При этом как «init»

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

Рис. 8. Автоматы Бюхи для LTL-формул Fp (а), pUq (б), pRq (в) Далее модель Крипке, построенная для исходной программы, также преобразуется в автомат Бюхи, в котором метка на переходе – это выполнимость определенного предиката. Для автоматных программ под предикатом будем понимать утверждение о текущем переходе, например, сгенерированные автоматом выходные воздействия в объекте управления или состояние, в которое перешел автомат.

После этого строится его пересечение с автоматом Бюхи, построенным по отрицанию LTL-формулы. Это пересечение также является автоматом Бюхи, и для него запускается алгоритм двойного поиска в глубину [9], который находит допускающую последовательность предикатов. Если эта последовательность существует, то:

она допускается автоматом Бюхи, построенным по модели Крипке. Следовательно, эта последовательность является историей работы исходной программы;

построенным из отрицания LTL-формулы. Следовательно, эта последовательность является историей, нарушающей проверяемые требования.

1.2. ПОИСКОВАЯ ИНЖЕНЕРИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ

посвященных поисковой инженерии ПО.

В рамках поисковой инженерии ПО [45, 69 – 71] для решения задач прогнозирование хода разработки [30], проектирование [110], верификация на основе метода Model Checking [31 – 33, 60], тестирование [34, 67, 93], разбиение на модули [91] и рефакторинг [68, 106], предлагается применять алгоритмы поисковой оптимизации.

Отметим, что эта область исследований является новой – на апрель 2012 г. по этой тематике было опубликовано всего 1020 работ (http://crestweb.cs.ucl.ac.uk/resources/sbse_repository/repository.html).

В число методов, которые нашли применение в поисковой инженерии ПО [69], входят эволюционные алгоритмы (генетические алгоритмы [2, 11, 12, 43, 24, 25], генетическое программирование [84] и эволюционные стратегии [40]), а также муравьиные алгоритмы [49], метод роя частиц [82], метод имитации отжига [94], метод спуска [66], алгоритмы оценки распределений [86], поиск с запретами [58], меметические программирование [105], целочисленное программирование [113], распространение получили эволюционные алгоритмы [71].

В работе [45] приводятся следующие критерии, которые позволяют определить, насколько задача подходит для решения с помощью методов поисковой оптимизации:

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

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

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

3. Применение методов поисковой оптимизации следует начать с метода спуска. Если он дает достаточно хорошие результаты, то имеет смысл применять и другие алгоритмы поисковой Последний пункт объясняется тем, что во многих задачах метод спуска часто дает удовлетворительные результаты [66, 83, 96, 97]. При этом существуют как задачи [119], в которых генетический алгоритм работает лучше метода спуска, так и задачи, в которых метод спуска работает лучше генетического алгоритма [100].

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

Как отмечается в работе [69], для решения задач проектирования ПО, к которым относится задача построения автоматов, применялись следующие алгоритмы: метод спуска, метод имитации отжига [94], муравьиные алгоритмы, эволюционные алгоритмы. Как отмечалось выше, в литературе для построения автоматов применяются в основном эволюционные алгоритмы, которые улучшаются в настоящей работе и рассматриваются ниже.

Наиболее простым из алгоритмов решения задач поисковой оптимизации является метод спуска (англ. hill climbing). Процесс поиска начинается со случайно выбранной точки в пространстве решений задачи.

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

В противном случае поиск считается оконченным, а текущая точка – оптимальным решением.

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

У метода спуска существует множество вариаций. Например, вопрос о том, требуется ли выбирать первую соседнюю точку, оказавшуюся в указанном смысле лучше текущей, или требуется ли рассмотреть все соседние точки и выбрать среди них оптимальный вариант, порождает различные версии алгоритма (first ascent hill climbing, steepest ascent hill climbing).

Еще одним вариантом метода спуска является метод спуска на основе случайных мутаций (random mutation hill climbing), который эволюционным алгоритмам. В этом методе к текущему решению на каждом шаге применяется случайное локальное изменение (мутация), и полученное решение сравнивается с текущим. Если оно не хуже его, то оно становится текущим. Если в течение некоторого числа итераций не происходит улучшения значения функции приспособленности, то происходит перезапуск алгоритма (рис. 9).

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

алгоритмом, и во многих случаях применение этого метода дает достаточно хорошие результаты, например, в задаче разбиения на модули [66, 97] и оценки стоимости проекта [83].

В течение заданного числа шагов не было улучшения значения функции приспособленности Рис. 9. Схема работы метода спуска на основе случайных мутаций Опишем (1+1)-эволюционную стратегию [40]. Процесс поиска начинается со случайно выбранной точки в пространстве решений задачи.

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

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

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

Известны и (+)-эволюционные стратегии, в которых рассматривается не одно текущее решение, а решений, из которых на каждой итерации с помощью мутаций генерируются новых решений. Также существуют скрещивания [40], что делает их во многом похожими на генетические алгоритмы.

Генетический алгоритм (genetic algorithm) [36, 73] представляет использовании принципа естественного отбора, составляющего основы теории эволюции живых организмов, предложенной Ч. Дарвином.

Подобные идеи возникали у ряда исследователей. В 1962 г.

Л. Фогель занялся изучением интеллектуального поведения индивида и его развития в процессе эволюции [52]. Такое поведение задавалось конечным автоматом. Продолжая данные исследования, Л. Фогель, А. Оуэнс и М.

Уолш предложили в 1966 г. схему эволюции конечных автоматов, решающих задачи предсказания [53]. Примерно в это же время (в середине 60-х годов) Дж. Холланд разработал новый метод поиска оптимальных решений – генетические алгоритмы. Результатом работы Дж. Холланда стала книга [73], вышедшая в 1975 г. Эти работы заложили основы эволюционных вычислений.

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

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

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

Процесс работы генетического алгоритма состоит в генерации поколений особей до тех пор, пока не будет выполнено некоторое условие приспособленности или сгенерировано заданное число поколений). На рис. 11 приведена общая схема работы генетического алгоритма.

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

предложенное Дж. Козой в 1992 г. [84], предполагает применение генетических алгоритмов для автоматизированного построения программ.

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

Рис. 11. Общая схема работы генетического алгоритма

1.3. ПРИМЕНЕНИЕ ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ ДЛЯ

ПОСТРОЕНИЯ КОНЕЧНЫХ АВТОМАТОВ

эволюционных алгоритмов построения конечных автоматов. Методы построения конечных автоматов с помощью эволюционных алгоритмов и генетического программирования можно разделить на три типа:

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

вычисления функции приспособленности;

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

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

Один из создателей эволюционного программирования Л.Фогель рассматривал интеллектуальное поведение индивида как способность успешно предсказывать поведение среды, в которой он находится, и сообразно с этим действовать. В 60-x годах прошлого века годах Л. Фогель поставил ряд экспериментов [53] по созданию искусственных систем, способных адаптироваться к первоначально неизвестной им среде.

В проведенных экспериментах Л. Фогель моделировал поведение простейшего живого существа, которое способно предсказывать изменения параметра среды, обладающего периодичностью. Это существо моделировалось конечным автоматом с действиями на переходах – автоматом Мили. В качестве среды выступала последовательность символов над двоичным алфавитом, например, (1111010010)*. На вход автомата в каждый момент времени подавалось битовое значение параметра окружающей среды. Автомат формировал значение выходной переменной – возможное значение рассматриваемого параметра в следующий момент времени. На рис. 12 приведен один из возможных автоматов, который построен для распознавания указанной выше последовательности.

Рис. 12. Граф переходов эвристически построенного автомата Задача состояла в эволюционном построении автомата, способного как можно более точно в смысле какой-либо разумной функции приспособленности от входа и выхода (например, числа совпавших последовательности. Кроме того, Л. Фогель накладывал ограничения на сложность порождаемого автомата, так как строить автоматы с числом представляет труда. Таким образом, предпочтение отдавалось автоматам, угадывающим как можно лучше, и в то же время имеющим как можно меньше состояний.

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

добавление состояния;

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

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

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

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

Еще одной задачей, в которой построенные с помощью генетических алгоритмов автоматы обладают подобными свойствами, является задача «Умный муравей» [35, 79]. В этой задаче рассматривается поле, имеющее форму тора размером 32 на 32 клетки (рис. 13). В некоторых клетках поля расположены яблоки – черные клетки на рис. 13. Яблоки расположены вдоль некоторой ломаной линии, но не во всех ее клетках. Клетки ломаной, на которых яблок нет – серые. Белые клетки не принадлежат ломаной и не содержат яблок. Всего на поле 89 яблок.

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

идет вперед на одну клетку, съедая яблоко, если оно находится поворачивает вправо;

поворачивает влево;

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

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

Игра длится 200 ходов. В конце игры подсчитывается число яблок, съеденных муравьем. Это значение – результат игры.

Поведение муравья может быть задано конечным автоматом.

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

Рис. 14. Конечный автомат, описывающий поведение муравья В рассматриваемой задаче требуется построить конечный автомат, под управлением которой муравей за 200 ходов съест все 89 яблок.

Приведенный на рис. 14 автомат не решает задачу – за 200 ходов муравей съедает только 81 яблоко (на все 89 яблок ему требуется 314 ходов).

В работе [79] с помощью генетических алгоритмов построен автомат из 13 состояний, решающий поставленную задачу. В работе [35] также с помощью генетических алгоритмов построен автомат из 11 состояний, который позволяет муравью съесть все яблоки за 193 хода. В указанных приспособленность особи определялась как число яблок, съеденное за ходов.

В работах [156 – 159] при участии автора настоящей диссертации для решения рассматриваемой задачи было предложено применять генетическое программирование – в отличие от указанных выше работ в генетическом алгоритме автомат представлялся не в виде битовой строки, а в виде графа переходов. Кроме этого, существенное отличие предлагаемого в этой работе алгоритма состоит в использовании двух операторов скрещивания – традиционного и сохраняющего значимые части автоматов [157].

Оператор скрещивания, предложенный в указанной работе, получает на вход две особи и выдает также две особи. Процесс скрещивания происходит следующим образом. Обозначим родительские особи 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, причем оба варианта равновероятны.

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

Множество переходов некоторого автомата A обозначим T(A). Для автоматов, получающихся в результате скрещивания возможны два равновероятных варианта:

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

Рис. 15. Граф переходов автомата из семи состояний, решающего Кроме этого, в работе [156] описывается алгоритм перебора, с помощью которого было установлено, что автоматы с шестью и менее состояниями задачу «Умный муравей» не решают.

В рамках исследований по теме «Технология генетического программирования для генерации автоматов управления системами со сложным поведением» на кафедре «Технологии программирования»

НИУ ИТМО для сравнения методов генерации конечных автоматов с помощью генетических алгоритмов [129 – 132] была предложена задача работе [123], содержит несколько существенных отличий от задачи «Умный муравей».

Во-первых, расширена область обзора муравья – вместо одной клетки он видит восемь. Таким образом, множество значений входных переменных содержит 28 = 256 элементов. На рис. 16 изображена область обзора муравья (клетка, в которой находится муравей, обозначена серым цветом).

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

В этом случае число яблок, съеденных муравьем за 200 ходов, является случайной величиной (определяемой муравьем) на дискретном множестве элементарных исходов – множестве расположений яблок – битовых матриц 3232. Для каждого исхода, обозначим как apples() соответствующее ему число яблок на поле, и поставим в соответствие ему вероятность p() = apples()(1–)1024- apples().

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

В рамках указанных исследований было предложено три метода генерации конечных автоматов с помощью генетических алгоритмов:

метод сокращенных таблиц переходов;

метод представления автоматов деревьями решений;

Метод сокращенных таблиц переходов был предложен в работе [22].

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

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

К таблице, задающей сужение функции переходов на данное состояние, в этом случае добавляется битовый вектор, описывающий множество значимых входных переменных. Число строк таблицы в этом случае 2 r '. Ее выбор зависит от сложности задачи. Как показывает опыт, для большинства автоматизированных объектов значение r’ не превышает пяти.

Второй метод – метод представления автоматов деревьями решений [5, 135, 149]. Дерево решений является удобным способом задания дискретной функции, зависящей от конечного числа логических переменных. Оно представляет собой помеченное дерево, метки в котором расставлены по следующему правилу:

внутренние узлы помечены символами переменных;

ребра – значениями переменных;

листья – значениями искомой функции.

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

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

номер переменной, соответствующей метке узла (для внутренних указатель на дочерний узел, соответствующий нулевому значению переменной (для внутренних узлов);

указатель на дочерний узел, соответствующий единичному значению переменной (для внутренних узлов);

ассоциированное выходное действие (для листьев);

номер состояния, в которое ведет переход из данной вершины (для листьев).

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

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

Рис. 17. Структурная схема системы управления при использовании метода совместного применения конечных Одна из возможных структур нейронной сети и способ ее взаимодействия с конечным автоматом показаны на рис. 18. Отметим, что для решения других задач структура нейронной сети может быть изменена.

Числовые или логические входные переменные Рис. 18. Возможная структура нейронной сеть и ее взаимодействие Символами S на рис. 18 обозначены нейроны с сигмоидальной функцией активации, символом L – нейроны с пороговой функцией активации. Рядом с нейронами указаны их номера (они используются при описании операции скрещивания нейронных сетей). На каждый из трех выходов нейронной сети поступает число равное нулю или единице. Таким образом, существует восемь вариантов комбинаций выходных сигналов нейронной сети (000, 001, 010, 011, 100, 101, 110, 111), подаваемых на вход автомата.

Экспериментальные исследования, проведенные в работе [132], показали, что при построении автомата для задачи «Умный муравей-3» три метода представления автоматов, рассмотренные выше, привели примерно одинаковые результаты.

1.3.1.4. Игра «Соревнование за ресурсы»

В работе [114] рассматривается задача построения автоматов для игры «Соревнование за ресурсы» (Competition for Resources). Игровое поле в этой игре имеет форму тора размером 10 на 10 клеток (тор можно представить в виде квадрата, у которого верхняя сторона склеена с нижней, а правая – с левой). Оно моделирует компьютерную сеть, в которой могут распространяться программные агенты.

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

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

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

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

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

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

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

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

Вычисление функции приспособленности выполняется в два этапа – на первом из них для всех автоматов, описываемых особями текущего поколения, проводится 500 игр против заданной стратегии поведения второго агента. Если в текущем поколении находится автомат, который по результатам этого вычисления показывает результат, превосходящий наилучший автомат, рассмотренный в процессе работы алгоритма, то для автомата из текущего поколения проводится более точное вычисление функции приспособленности – по итогам 10 000 игр.

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

Вычислительные эксперименты проводились при значениях числа состояний в генерируемых автоматах от одного до десяти. Их результаты показывают, что при решении этой задачи существенное преимущество имеют автоматы, имеющие более двух состояний. Автоматы с числом состояний от трех до десяти показывали примерно одинаковые результаты – около 90% побед. Кроме этого, были проведены эксперименты, в которых в процессе мутации разрешалось добавлять и удалять состояния – в этом случае было замечено, что в построенных автоматах используется меньше половины состояний. На основании результатов экспериментов был сделан вывод о том, что операции добавления и удаления состояний являются слишком «разрушительными»

для их применения в эволюционных алгоритмах построения автоматов.

Анализ поведения агентов, управляемых построенными автоматами, показал, что поведение агента достаточно быстро зацикливается, что приводит к ухудшению его результатов. Для того чтобы устранить этот недостаток, в рассматриваемой работе предлагается метод, основанный на наблюдении за поведением агента во время игры. Этот метод состоит в том, что к автомату добавляется память размером в 20 ячеек, которая позволяет отслеживать циклы в поведении агента. В этой памяти записывались ячейки, посещенные агентом. Если далее обнаруживалось, что действие, генерируемое автоматом, приводит к зацикливанию, то действие выбиралось случайным образом. Применение такого метода позволило построить систему управления агентом, которая добивалась побед в 96% игр. Описанный метод устранения зацикливания является одной из разновидностей динамической верификации [101].

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

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

Конечным распознавателем A называется пятерка (Q,,, q0, F), где Q – множество состояний автомата, – его входной алфавит, – функция переходов, q0 – начальное состояние, F – множество допускающих состояний. Аргументами функции переходов являются текущее состояние и входной символ, а значением – новое состояние.

детерминированные автоматы способны распознавать регулярные языки [26]. В связи с этим в ряде работ рассматривалась задача построения по множеству примеров автомата, распознающего некий язык. Для решения этой задачи успешно применялись генетические алгоритмы.

Задача может быть усилена до построения автомата с минимальным числом состояний. В работе [61] показано, что эта задача является NPполной.

В работе [38] автоматы представлялись с помощью таблицы переходов. Разработанный в этой работе метод позволяет поддерживать в приспособленности учитывает три компонента – число верно распознанных обучающих примеров, число состояний и переходов автомата, степень общности языка, соответствующего построенному автомату. Это позволяет сузить область поиска, и находить языки, соответствующие определенным критериям. В обучающий набор могут входить примеры слов, которые как принадлежат, так и не принадлежат языку.

Приведем описание генетической операции «репродукция». Число состояний потомка выбирается случайно из диапазона [k – 2, k + 2], где k – число состояний первого родителя. После этого каждый переход копируется из родителей, при этом вероятность копирования перехода из приспособленности. Переходы, представленные только в одном из родителей, копируются из того родителя, в котором присутствуют.

Переходы, отсутствующие в обоих родителях, генерируются случайно.

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

Предложенный подход был проверен на практических задачах.

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

В работе [88] производится сравнение алгоритмов построения конечных автоматов-распознавателей. При этом рассматриваются два типа алгоритмов: эволюционные и основанные на построении префиксного дерева и дальнейшем объединении состояний на основе свидетельств (Evidence-Driven State Merging, далее EDSM).

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

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

рассматриваемой работе применяется табличная форма задания его функции переходов. При этом начальным состоянием всегда считается состояние, имеющее номер «0». В рассматриваемой работе рассматриваются только автоматы, обрабатывающие слова над двухсимвольным алфавитом, поэтому число возможных таблиц переходов для k состояний равно k2k. Если учитывать то, что каждое состояние автомата может быть допускающим или недопускающим, то общий размер пространства поиска равен 2k·k2k.

Для сокращения пространства поиска в работе [88] применяется специальный метод определения того, какие состояния автомата являются допускающими, а какие – нет. Для этого предлагается использовать так называемый «алгоритм расстановки пометок» на состояниях. Он состоит в следующем. Для каждой строки t из множества обучающих примеров на единицу увеличивается значение h[f(t)][], где f(t) – номер состояния, в которое приходит рассматриваемый автомат после обработки строки t, а число равно единице, если строка t должна допускаться автоматом, и равно нулю, если не должна допускаться автоматом. После этого те состояния s, для которых h[s][1] > h[s][0], помечаются как допускающие, а все остальные – как недопускающие. За счет применения описанного алгоритма размер пространства поиска существенно сокращается – его размер становится равным k2k.

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

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

Сравнение эволюционного алгоритма проводилась на двух наборах тестовых данных. Первый набор тестовых данных был предложен в работе [116]. На этом наборе входных данных сравнение проводилось не только с алгоритмом EDSM, но и с алгоритмом генетического программирования, разработанный алгоритм эволюционного программирования превосходит и алгоритм EDSM, и алгоритм из работы [116], как по точности построенных автоматов, так и по времени работы. Например, среднее время, которое требуется предложенному в рассматриваемой работе алгоритму для построения конечного автомата, составляет 1. миллисекунды, а алгоритму EDSM требуется 37 миллисекунд в среднем (вычислительные эксперименты проводились на компьютере с процессором Pentium IV с тактовой частотой 2.4 ГГц).

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

2. Генерировался случайный ориентированный граф из 5m/ вершин, в котором каждая вершина имеет степень два.

3. Случайным образом выбиралась вершина – начальное состояние.

4. Рассматривались все достижимые из начального состояния.

5. Каждое из состояний с равной вероятностью становилось либо допускающим, либо недопускающим.

6. После этого генерировалось множество строк над двухсимвольным алфавитом, для каждой из которых с помощью построенного на шагах 1 – 5 автомата определялось, допускается На этом наборе данных эволюционный алгоритм при m = 4, 8, превосходил алгоритм EDSM, но при m = 32 ему уступал.

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

В работе [89] также рассматривается задача построения конечных автоматов-распознавателей с помощью эволюционных алгоритмов.

Предлагаемый в рассматриваемой работе эволюционный алгоритм является улучшенной версией алгоритма, предложенного в работе [88].

Конечный распознаватель в рассматриваемой работе представляется так же, как и в работе [88]: в хромосому входит таблица переходов, а пометки на состояниях расставляются с помощью специального алгоритма. В качестве эволюционного алгоритма в работе [89] также используется (1+1)-эволюционная стратегия, но операцию мутации предлагается выполнять не так, как в работе [88].

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

Для каждого перехода t в автомате вычисляются две величины.

Число строк, которые были правильно классифицированы автоматом и при обработке которых использовался переход t, обозначается как cor(t). Число строк, неправильно классифицированных автоматом и при обработке которых использовался переход t, обозначается как err(t). При этом вероятность того, что переход t будет выбран при выполнении операции err(t) = 0. Такой подход к выполнению операции мутации требует приспособленности и указанных вероятностей. На первом из них неизвестно, какие состояния являются допускающими, а какие – нет. Этот проход необходим для алгоритма пометки состояний. На втором проходе известно, какие состояния являются допускающими, поэтому указанные вероятности могут быть вычислены.

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

Для сравнения алгоритмов в рассматриваемой работе применялось два набора тестовых данных. Первый строился так же, как второй набор тестовых данных в работе [88] (описание приведено выше). Второй набор данных был зашумленным – для некоторых строк из обучающего набора было неправильно указано, должны они допускаться автоматом или нет.

На первом наборе данных проводилось сравнение четырех алгоритмов:

не использующего алгоритм расстановки пометок (plain);

метода из работы [88] (smart labeling);

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

метода, использующего второй из предлагаемых в рассматриваемой работе подходов к выполнению операции мутации (quick-sampled).

Результаты вычислительных экспериментов показали, что при восьми состояниях автомата, на основе которого генерировались обучающие наборы, из 50 случаев алгоритм plain построил автомат в 26, алгоритм smart labeling – в 42, алгоритм sampled – в 47, а алгоритм quicksampled – в 43. При использовании автомата из 16 состояний результаты были такими: plain – 5 из 50, smart – 21 из 50, sampled – 26 из 50, quicksampled – 4 из 50. Если же в исходном автомате было 32 состояния, то только два алгоритма справились с задачей: smart правильно строил автомат в 6 случаях из 50, а sampled – в 12 случаях из 50.

Как отмечалось выше, второй набор данных содержал зашумленные обучающие наборы. На этом наборе данных сравнение проводилось с алгоритмом EDSM и с другими алгоритмами, участвовавшими в соревновании в рамках конференции GECCO 2004 [144]. Результаты вычислительных экспериментов показали, что предлагаемый в рассматриваемой работе эволюционный алгоритм (sampled) превосходит все существующие алгоритмы построения автоматов на этом обучающем наборе по точности их построения. При этом отметим, что предложенный алгоритм эффективен только для построения автоматов из относительно небольшого числа состояний (порядка нескольких десятков), в то время как с помощью алгоритма EDSM могут быть успешно построены автоматы из сотен состояний.

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

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

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

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

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

1.3.2.2. Построение конечных преобразователей Конечным преобразователем называется шестерка (Q,, O,,, q0), где Q – множество состояний автомата, – его входной алфавит, O – его выходной алфавит, – функция переходов, – функция выходов, q0 – начальное состояние. Аргументами функции переходов являются текущее состояние и входной символ, а значением – новое состояние. Аргументами функции выходов также являются текущее состояние и входной символ, а значением – символ из выходного алфавита или пустая строка.

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

Входными данными для построения конечного автоматараспознавателя является набор обучающих примеров – пар слов, одно из которых является входным, а второе – соответствующим ему выходным.

Опишем алгоритм выполнения операции мутации в алгоритме, предложенном в рассматриваемой работе. Выполняется мутация одного из трех типов:

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

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

удаление состояния;

случайное изменение одного перехода.

равновероятно.

В рассматриваемой работе рассматриваются три варианта функции приспособленности:

на основе строгого сравнения;

на основе вычисления расстояния Хэмминга [64];

на основе вычисления редакционного расстояний (расстояния Левенштейна) [13].

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