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

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

ОГЛАВЛЕНИЕ
Введение
Глава 1. Обзор задач, в которых генерация конечных автоматов осуществляется с помощью генетических алгоритмов.

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

1.2. Эксперименты Фогеля регрессия.

1.3. Задача оптимизации функций

1.4. Автоматические переговоры.

1.5. Распознавание нерегулярных языков.

1.6. Проектирование логических схем для автоматов Мили.

1.6.1. Задача кодирования состояний

1.7. Обзор методов генерации автоматов с помощью генетических

алгоритмов.
Выводы по главе 1
Глава 2. Генерация автоматов для решения задачи о флибах.
2.1. Постановка задачи.
2.2. Схемы работы генетических алгоритмов в задаче о флибах
2.2.1. Известный алгоритм
2.2.2. Предлагаемая модификация алгоритма
2.3. Реализация флиба
2.3.1. Известный метод.
2.3.2. Предлагаемый метод
2.4. Генератор значений входной переменной.
2.5. Функция приспособленности.
2.6. Оператор одноточечного скрещивания
2.6.1. Известный алгоритм
2.6.2. Предлатемый алгоритм
2.7. Оператор мутации.
2.7.1. Известный алгоритм.
2.7.2. Предлагаемый алгоритм
2.8. Алгоритм восстановления связей между состояниями.
2.8.1. Программа для проведения экспериментов на флибах.
2.8.2. Эксперименты по применению алгоритма восстановления связей
между состояниями.
2.9. Использование автоматов с флагами
2.9.1. Эксперименты по использованию автоматов с флагами
Выводы по главе 2.
Глава 3. Генерация автоматов для задачи об умном муравье
3.1. Постановка задачи
3.2. Известный генетический алгоритм
3.2.1. Стратегия отбора.
3.2.2. Оператор скрещивания.
3.2.3. Оператор мутации.
3.3. Предложенные модификации алгоритма.
3.3.1. Сортировка состояний в порядке использования.
3.3.2. Оператор мутации всегда вперед, если впереди еда.
3.3.3. Уменьшение числа состояний.
3.4. Описание модели программы для сравнения эффективности
генетических алгоритмов, решающих задачу об умном муравье.
3.5. Эксперименты.
Выводы по главе 3.
Глава 4. Генерация автоматов для задачи построения автопилота для
упрощенной модели вертолета.
4.1. Постановка задачи
4.2. Модель вертолета
4.3. Модель окружающей среды.
4.4. Алгоритм построения автопилота
4.5. Общая схема генетического алгоритма.
4.6. Описание программы
4.7. Эксперименты
Выводы по главе 4
Заключение.
Литература


Исследования и разработки но приоритетным направлениям развития научнотехнологического комплекса России» на - гг. Достоверность научных положений, выводов и практических рекомендаций, полученных в диссертации, подтверждается корректным обоснованием постановок задач, точной формулировкой критериев, а также результатами экспериментов по использованию предложенных в диссертации методов. Практическое значение работы заключается в том, что полученные результаты могут быть использованы для решения практических задач. Предложенные модификации генетических алгоритмов для построения автоматов, позволяют повысить эффективность работы алгоритмов, что подтверждается экспериментальными данными. Практическая ценность подтверждается внедрением результатов работы. Внедрение результатов работы. Результаты, полученные в диссертации, используются на практике в компании Транзас (Санкт-Петербург) при разработке тренажера вертолета, а также в учебном процессе на кафедре «Компьютерные технологии» СПбГУ ИТМО но курсу «Теория автоматов в программировании». Апробации диссертации. Основные положения диссертационной работы докладывались на 4-й Всероссийской научной конференции «Управление и информационные технологии» СПбГЭТУ «ЛЭТИ» (), XXXVI научной и учебно-методической конференции профессорско-преподавательского и научного состава СПбГУ ИТМО (), IV межвузовской конференции молодых ученых СПбГУ ИТМО (), XIV Всероссийской научно-методической конференции «Телсматика-» (Санкт-Петербург), XXXVII научной и учебно-методической конференции СПбГУ ИТМО (), V Всероссийской межвузовской конференции молодых ученых СПбГУ И'ГМО (), XV международной научно-методической конференции «Высокие интеллектуальные технологии и инновации в образовании и науке» (Санкт-Петербургский государственный политехнический университет, ). Публикации. По теме диссертации опубликовано шесть печатных работ, в том числе три в изданиях из перечня ВАК («Известия РАИ. Теория и системы управления» и «Научно-технический вестник СГГУ ИТМО»). Структура диссертации. Диссертация изложена на 4 страницах и состоит из введения, четырех глав и заключения. Список литературы содержит наименования. Работа содержит рисунков и таблиц. В первой главе приведен обзор задач, в которых автоматы строятся с помощью генетических алгоритмов. Вторая глава содержит описание методов генерации автоматов для задачи о флибах, которая появилась в ходе первых работ по моделированию способностей живых существ к предсказанию. Третья глава содержит описание методов генерации автоматов для задачи об умном муравье, которая стала классической в рассматриваемой области. В четвертой главе, используя сортировку состояний в порядке использования, предложенную в предыдущей главе, разработан генетический алгоритм генерации автоматов для задачи построения автопилота для упрощенной модели вертолета (в дальнейшем вертолета). ГЛАВА 1. Для различных биологических объектов характерна оптимальность, а также согласованность и эффективностью их работы. Многих исследователей давно интересовал «философский» вопрос — возможно ли эффективное построение значимых и полезных для человека систем на основе принципов биологической эволюции? Подобные идеи возникали у ряда исследователей. В г. Л. Фогель начал моделировать интеллектуальное поведение индивида и его развитие в процессе эволюции [6]. При этом поведение индивида задавалось конечным автоматом. Продолжая эти исследования, Л. Фогель, А. Оуэнс и М. Уолш предложили в г. Примерно в это же время (в середине -х годов) Дж. Холланд разработал новый метод поиска оптимальных решений - генетические алгоритмы. Результатом его исследований стала книга [7], вышедшая в г. Эти работы заложили основы эволюционных вычислений. Приведем ряд определений, которые играют важную роль в теории эволюционных вычислений и необходимы для описания генетических алгоритмов. Популяция - это совокупность особей на рассматриваемой стадии эволюции. Индивид (особь) - единичный представитель популяции. Хромосома - структура, содержащая генетический код индивида. Ген - определенная часть хромосомы, кодирующая врожденное качество индивида.