МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
(МИНОБРНАУКИ)
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ»
(СПбГУ ИТМО)
Факультет информационных технологий и программирования
Кафедра «Компьютерные технологии»
Федор Николаевич Царев
Разработка методов совместного применения генетического и автоматного программирования
Магистерская диссертация
Научный руководитель – доктор технических наук, профессор, заведующий кафедрой технологий программирования СПбГУ ИТМО
Анатолий Абрамович Шалыто
Санкт-петербург
2009
Оглавление
Оглавление 4
Введение 6
Глава 1. автоматное и генетическое программирование 10
1.1. Основные концепции автоматного программирования 10
1.1.1. Системы со сложным поведением 10
1.1.2. Автоматное программирование 13
1.2. Генетические алгоритмы 14
1.2.1. Основные определения 15
1.2.2. Традиционный генетический алгоритм 18
1.2.3. Генетическое программирование 19
1.3. Применение генетических алгоритмов для построения конечных автоматов 20
1.3.1. Эксперименты Фогеля 20
1.3.2. Задача «Умный муравей» 23
1.3.3. Построение конечных детерминированных автоматов для распознавания регулярных языков 28
1.3.4. Построение конечных преобразователей 33
1.3.5. Работы в СПбГУ ИТМО 36
1.3.6. Другие работы по построению конечных автоматов с помощью генетических алгоритмов 41
Выводы по главе 1 43
Глава 2. Метод представления автоматов с помощью конечных распознавателей 44
2.1. Задача «Умный муравей–3» 44
2.2. Решение задачи без применения конечных автоматов 46
2.3. Решение задачи с помощью метода представления автоматов деревьями решений 46
2.4. Предлагаемый метод 48
2.4.1. Описание алгоритма 50
2.4.2. Операция мутации 51
2.4.3. Операция скрещивания 51
2.4.4. Формирование следующего поколения 53
2.4.5. Настраиваемые параметры алгоритма 54
2.5. Результаты вычислительных экспериментов 54
Выводы по главе 2 56
Глава 3. Метод построение конечных автоматов управления системами со сложным поведением на основе тестов 57
3.1. Постановка задачи 57
3.2. Описание предлагаемого метода 58
3.2.1. Представление конечного автомата в виде хромосомы генетического алгоритма 59
3.2.2. Генетический алгоритм 66
3.2.3. Вычисление функции приспособленности 66
3.3. Пример применения метода 68
3.3.1. Система тестов 70
3.3.2. Результаты применения генетического алгоритма 77
Выводы по главе 3 80
Заключение 81
Источники 83
Введение
Генетические алгоритмы [4, 35, 55] являются одним из современных и быстро развивающихся направлений в искусственном интеллекте [20]. С их помощью могут быть найдены решения многих задач в различных областях. Примерами таких задач являются: задачи синтеза расписаний, задачи планирования работ и распределения ресурсов, задачи маршрутизации транспортных средств, синтез топологии сетей различного назначения, построение искусственных нейронных сетей, деревьев принятия решений, автоматическое построение программ, проектирование конечных автоматов и клеточных автоматов.
Генетическое программирование [49] – разновидность генетических алгоритмов, в которой вместо низкоуровневого представления объектов в виде битовых строк используется высокоуровневое представление: деревья разбора программ, диаграммы переходов конечных автоматов и т.д. С помощью генетического программирования наиболее эффективно решаются задачи автоматического построения программ, конечных автоматов и клеточных автоматов.
Автоматное программирование [17] – парадигма программирования, при использовании которой программу предлагается строить в виде совокупности автоматизированных объектов управления, каждый из которых содержит систему управления (взаимодействующие конечные автоматы) и объект управления.
Объект управления характеризуется множеством вычислительных состояний, а также двумя наборами функций: множеством предикатов, отображающих вычислительное состояние в логическое значение (истина или ложь), и множеством действий, позволяющих изменять вычислительное состояние.
Управляющий автомат определяется конечным множеством управляющих состояний, функцией переходов и функцией действий. Взаимодействие между автоматами может осуществляться различными способами: за счет вложенности автоматов, с помощью обмена сообщениями, с помощью обмена номерами состояний и т.д.
Управляющие конечные автоматы часто характеризуются сложным поведением, как например, в задаче «Умный муравей–3», рассматриваемой в настоящей работе. В таком случае их эвристическое проектирование представляет собой весьма трудоемкую задачу. Возникает естественное желание – автоматизировать процесс проектирования автоматов, поручив основную работу компьютеру.
В настоящей работе в качестве метода автоматизированного построения автоматов выбрано генетическое программирование. Цель работы состоит в:
разработке нового метода совместного применения генетического и автоматного программирования, основанного на использовании тестов;
разработке нового метода представления конечных автоматов, который может быть использован в контексте традиционного метода совместного применения генетического и автоматного программирования.
В существующих работах по совместному применению автоматного и генетического программирования для вычисления функции приспособленности используется моделирование работы системы со сложным поведением в некоторой внешней среде. Одним из недостатков этого метода является то, что при его применении для новой задачи необходимо полностью «с нуля» программно реализовывать вычисление функции приспособленности. Кроме этого, моделирование зачастую связано с большими затратами вычислительных ресурсов. Эти недостатки ограничивают возможность применения метода на основе моделирования (далее он будет называться традиционным методом) на практике.
В работе разрабатывается метод совместного применения генетического и автоматного программирования, лишенный указанных недостатков. В качестве такого метода в работе предлагается метод, основанный на использовании тестов. Он может быть проще применен на практике, так как тесты достаточно активно применяются в разработке программного обеспечения (ПО), поэтому предлагаемый метод может проще встроен в существующие процессы разработки ПО. Для достижения этой цели предполагается решение следующих задач: разработка структуры хромосомы алгоритма генетического программирования, разработка алгоритмов осуществления мутации и скрещивания, апробация метода на примере задачи построения автомата управления часами с будильником.
С другой стороны, метод, основанный на тестах, предполагает, что разработчик уже обладает представлением не только о желаемых результатах поведения системы, но и о самом поведении. Если же необходимо строить систему со сложным поведением только на основе информации о желаемом результате ее поведения, то единственным методом, который может быть применен, является традиционный метод, основанный на моделировании.
В работе также производится исследование возможностей традиционного метода при использовании новых методов представления автоматов с большим числом входных переменных. Для представления таких автоматов ранее были разработаны различные методы: метод сокращенных таблиц переходов, метод представления автоматов деревьями решений. В настоящей работе делается попытка расширить метод представления автоматов деревьями решений – вместо деревьев решений предлагается использовать конечные преобразователи. Для достижения этой цели предполагается решение следующих задач: разработка структуры хромосомы алгоритма генетического программирования, разработка алгоритмов мутации и скрещивания, сравнение нового метода с существующим на примере задачи «Умный муравей–3».
В начале работы излагаются общие концепции генетических алгоритмов, генетического программирования и автоматного программирования, приводится перечень задач, в которых успешно применяются указанные методы. Далее описывается метод представления управляющих конечных автоматов с помощью конечных преобразователей, применение которого иллюстрируется на примере задачи «Умный муравей–3». Приводится его сравнение с решением, построенным вручную и с решением, построенным с помощью метода представления автоматов деревьями решений. В третьей главе описывается метод построения конечных автоматов управления системами со сложным поведением на основе тестов. Описывается структура особи алгоритма генетического программирования, алгоритм расстановки пометок, операции мутации и скрещивания для разработанной структуры особи. Применение этого метода иллюстрируется на примере построения автомата управления часами с будильником.
Метод построения автоматов на основе тестов интересен тем, что при его применении нет необходимости строить программную модель внешней среды для вычисления функции приспособленности – за счет этого требуется меньше вычислительных ресурсов. При этом для новой задачи необходимо подготовить только новый набор тестов, а «ядро» вычисления функции приспособленности остается неизменным.
В заключении работы анализируются ее результаты, и приводится ряд открытых вопросов и направлений для дальнейших исследований в этой области.
|
