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

• Автор: Царев, Федор Николаевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Санкт-Петербург
• Количество страниц: 196 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ.

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

1.1. Автоматное программирование

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

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

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

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

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 Операция скрегцивания.
2.1 Совместное использование генетического алгоритма, эволюционной стратегии и метода спуска на основе случайных мутаций
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. Экспериментальное исследование метода построения
АВТОМАТОВ ПО ОБУЧАЮЩИМ ПРИМЕРАМ И ТЕМПОРАЛЬНЫМ ФОРМУЛАМ
Выводы ПО ГЛАВЕ
ГЛАВА 3. ТЕХНОЛОГИЯ И ИНСТРУМЕНТАЛЬНОЕ СРЕДСТВО ПОСТРОЕНИЯ УПРАВЛЯЮЩИХ КОНЕЧНЫХ АВТОМАТОВ НА ОСНОВЕ ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ И ВЕРИФИКАЦИИ
3.1. ТЕХНОЛОГИЯ ПОСТРОЕНИЯ УПРАВЛЯЮЩИХ КОНЕЧНЫХ АВТОМАТОВ НА ОСНОВЕ ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ И ВЕРИФИКАЦИИ
3.2. Инструментальное средство для автоматизированного ПОСТРОЕНИЯ УПРАВЛЯЮЩИХ КОНЕЧНЫХ АВТОМАТОВ
3.2.1. Формат входных данных.
3.2.2. Формат выходных данных
3.2.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. Виртуальная лаборатория на языке v.
4.2.2. Виртуальная лаборатория на языке .
4.2.3. Применение виртуальных лабораторий в учебном процессе.
Выводы ПО ГЛАВЕ
ЗАКЛЮЧЕНИЕ.
СПИСОК ИСТОЧНИКОВ


Практическое значение работы состоит в том, что разработана технология автоматизированного построения управляющих конечных автоматов на основе эволюционных алгоритмов и создано инструментальное средство для автоматизации построения автоматов, поддерживающее эту технологию. По постренным автоматам, как отмечено выше, автоматически может быть сгенерирован программный код. Предложенные в работе эволюционные алгоритмы позволяют решить задачи построения автоматов, которые не удается решить вручную, а для других автоматов существенно сократить затраты времени на их построение по сравнению с известными методами, что подтверждается результатами экспериментальных исследований, приведенными в работе. Внедрение результатов работы. П от г. Федеральной целевой программе Научные и научнопедагогичсские кадры инновационной России на годы, Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных автоматов государственный контракт П от г. Федеральной целевой программе Научные и научнопедагогические кадры инновационной России на годы, Применение методов искусственного интеллекта в разработке управляющих программных систем государственный контракт П от г. Федеральной целевой программе Научные и научнопедагогические кадры инновационной России на годы, в рамках проекта Подготовка и переподготовка профильных специалистов на базе центров образования и разработок в сфере информационных технологий в СевероЗападном федеральном округе Государственный контракт . Р от г. Компьютерные технологии в рамках курса Теория автоматов и программирование. Апробация результатов работы. Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интеллекте ИММВИИ Коломна, , VI и VII межвузовская конференция молодых ученых СПбГУ ИТМО, , , X, XI и XII Международная конференции по мягким вычислениям и измерениям СПбГЭТУ ЛЭТИ, , , , Международная научная конференция Компьютерные науки и информационные технологии памяти А. М. Богомолова Саратовский государственный университет имени Н. Г. Чернышевского, , я конференция молодых ученых и специалистов Института проблем передачи информации им. А. А. Харкевича РАН Информационные технологии и системы , X научная и учебнометодическая конференция профессорскопреподавательского и научного состава СПбГУ ИТМО , i vi i , i, IV, , вторая межвузовская научная конференция по проблемам информатики СПИСОК, СПбГУ, , XI научная и учебнометодическая конференция НИУ ИТМО , i vi i , ii, IV, , третья российская конференция с международным участием Технические и программные средства систем управления, контроля и измерения Институт проблем управления имени В. А. Трапезникова РАН, пленарный доклад. Публикации. По теме диссертации опубликованы печатные работы, в том числе шесть статей, из которых пять в журналах из перечня ВАК. Свидетельства о регистрации программ для ЭВМ. В рамках диссертационной работы получены три свидетельства о регистрации программ для ЭВМ от г. Программное средство для построения управляющих конечных автоматов на основе обучающих примеров с использованием генетических алгоритмов, от г. Программное средство для генерации конечных автоматов с дискретными и непрерывными выходными воздействиями, от г. Структура диссертации. Диссертация изложена на 6 страницах и состоит из введения, четырех глав, заключения и двух приложений. Список источников содержит 0 наименований. Работа проиллюстрирована рисунком и таблицами. В первой главе приводится обзор работ, посвященных автоматному программированию, поисковой инженерии ПО и применению эволюционных алгоритмов для построения автоматов. На основе результатов обзора формулируются задачи, решаемые в настоящей диссертации. Вторая глава посвящена методам построения автоматов по обучающим примерам на основе эволюционных алгоритмов и выполнения операции скрещивания с учетом поведения автоматов на обучающих примерах, а также построения управляющих автоматов на основе эволюционных алгоритмов по обучающим примерам и темпоральным формулам.