Разработка метода совместного применения генетического программирования и конечных автоматов Царев Федор Николаевич, гр Научный руководитель – докт. техн. наук Шалыто Анатолий Абрамович 2007 год

2 Царев Ф.Н. Разработка метода совместного применения генетического программирования и конечных автоматов Решаемая проблема Автоматное программирование Часто эвристическое построение автоматов затруднено Построенные вручную автоматы зачастую не оптимальны Одно из решений – автоматизированное построение конечных автоматов с помощью генетического программирования

3 Царев Ф.Н. Разработка метода совместного применения генетического программирования и конечных автоматов Задача об «Умном муравье» Тор – 32x32 89 клеток с едой 200 ходов Расположение еды и начальная позиция муравья фиксированы Цель – создать муравья, который съест всю еду Муравей = конечный автомат

4 Царев Ф.Н. Разработка метода совместного применения генетического программирования и конечных автоматов Решение задачи Известные решения – автоматы с 8 и более состояниями Известные подходы – кодирование битовыми строками + генетический алгоритм Предлагаемый подход – генетическое программирование Построен автомат с 7 состояниями

5 Царев Ф.Н. Разработка метода совместного применения генетического программирования и конечных автоматов Задача «Летающие тарелки» Соревнование летающих тарелок на дальность полета Две команды по восемь тарелок Ограничения: запас топлива, столкновения, аэродинамическое взаимодействие Цель – разработка управляющей программы Задача заочного тура VI Открытой Всесибирской олимпиады по программированию (2005 год)

6 Царев Ф.Н. Разработка метода совместного применения генетического программирования и конечных автоматов Проблемы Существующие генетические алгоритмы не работают, если входные переменные автомата не логические (в рассматриваемой задаче они вещественны) Слишком большой размер особи генетического алгоритма, если в ней хранить управляющие системы для всех восьми тарелок

7 Царев Ф.Н. Разработка метода совместного применения генетического программирования и конечных автоматов Решение – 1 Совместное использование нейронной сети и конечного автомата Нейронная сеть преобразует вещественные входные переменные в логические

8 Царев Ф.Н. Разработка метода совместного применения генетического программирования и конечных автоматов Решение – 2 Особь = две системы управления летающей тарелкой При управлении тарелкой в команде из восьми используются данные о трех ближайших тарелках

9 Царев Ф.Н. Разработка метода совместного применения генетического программирования и конечных автоматов Решение – 3 Генетическое программирование Структурированное представление особи Адаптированы генетические операторы скрещивания и мутации Стратегия отбора – элитизм Функция приспособленности вычисляется с помощью соревнований с заданными заранее системами управления летающими тарелками

10 Царев Ф.Н. Разработка метода совместного применения генетического программирования и конечных автоматов Результаты применения генетического программирования За сутки была построена управляющая система, которая по ряду параметров оказалась лучше построенной вручную Построенная с помощью ГП система Построенная вручную система Среднее 216,55212,59 Минимум 203,05203,44 Максимум 241,11225,09

11 Царев Ф.Н. Разработка метода совместного применения генетического программирования и конечных автоматов Результаты работы Разработан алгоритм генетического программирования, позволяющий в ряде задач автоматически строить конечные автоматы Разработан метод, позволяющий использовать в качестве входных переменных вещественные числа С помощью разработанного алгоритма построено решение задачи об «Умном муравье» (автомат из семи состояний) С помощью разработанного метода и алгоритма построено решение задачи «Летающие тарелки», по ряду критериев лучшее, чем построенное вручную

12 Царев Ф.Н. Разработка метода совместного применения генетического программирования и конечных автоматов Спасибо за внимание!