Применение генетического программирования для построения автоматов А. А. Шалыто Г. А. Корнеев Санкт-Петербургский государственный университет информационных технологий, механики и оптики

2 Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением Парадигма автоматного программирования Предложено в России в 1991 году Программные системы разрабатываются как системы взаимодействующих автоматизированных объектов управления Система управления является системой взаимодействующих конечных автоматов Состояния События и входные переменные Выходные воздействия Конечный автомат Система конечных автоматов

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

4 Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением Инструментальное средство UniMod (1) Инструментальное средство для поддержки автоматного программирования Создано в рамках ФЦНТП «Исследования и разработки по приоритетным направлениям развития науки и техники» на годы по приоритетному направлению «Информационно- телекоммуникационные системы» Критическая технология – «Технологии производства программного обеспечения» Вошел в число 15 наиболее инновационно перспективных и социально значимых проектов Федерального агентства по науке и инновациям

5 Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением Инструментальное средство UniMod (2) Семь автоматов ВручнуюАвтоматическая генерация Вручную

6 Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением Инструментальное средство UniMod (3) Один из автоматов – AL

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

8 Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением Три рассматриваемые задачи «Простая» задача – задача об «Умном муравье» «Сложная» задача – задача «Беспилотные летательные объекты» «Народная» задача – «Разливочная линия»

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

10 Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением Эвристическое построение задачу не решает Пять состояний, за 200 ходов съедается 81 единица еды или все 89 единиц еды за 314 ходов

11 Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением Решение «простой» задачи Известные решения: 13 состояний (1992) 11 состояний (1993) 8 состояний (1999) Известные подходы – кодирование битовыми строками + генетический алгоритм Предлагаемый подход – генетическое программирование Построены два автомата с 7 состояниями каждый после перебора 160 и 230 млн. автоматов Полный перебор ~3·10 18 автоматов

12 Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением Максимальное число яблок Число состоянийЧисло яблок (1,5 часа, перебор) 685 (6 суток, перебор) 789 (6 часов, генетическое программирование

13 Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением «Сложная» задача – задача «Беспилотные летательные объекты» Соревнование на дальность полета Две команды по восемь объектов Ограничения: запас топлива, столкновения, аэродинамическое взаимодействие Цель – разработка управляющей программы Задача заочного тура VI Открытой Всесибирской олимпиады по программированию (2005 год) Была решена при участии автора путем эвристического построения автоматов

14 Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением Беспилотный летательный объект Двигатель Бак с топливом Бортовой компьютер Аэродинамические рули

15 Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением Аэродинамическое взаимодействие Области пониженного сопротивления воздуха Области повышенного сопротивления воздуха 20° – – ++

16 Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением Решение (1) Система управления = нейронная сеть + конечный автомат Нейронная сеть преобразует вещественные входные переменные в логические

17 Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением Решение (2) Особь = две системы управления беспилотным объектом Особь из двух систем – для учета взаимодействия объектов

18 Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением Решение (3) Мутация особи Мутация системы управления летательным объектом Мутация нейронной сети Мутация элемента сети Мутация конечного автомата Изменение начального состояния Мутация перехода Скрещивание особей Скрещивание систем управления летающей тарелкой Скрещивание автоматов Скрещивание нейронных сетей

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

20 Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением Задача: налить как можно больше бутылок за заданный промежуток времени «Народная» задача – «Разливочная линия»

21 Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением Решения задачи Построен вручную Построен автоматически

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

23 Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением Публикации по теме (1) 1. Лобанов П.Г., Шалыто А.А. Использование генетических алгоритмов для автоматического построения конечных автоматов в задаче о флибах //Известия РАН. Теория и системы управления Мандриков Е.А., Кулев В.А., Шалыто А.А. Применение генетических алгоритмов для создания управляющих автоматов в задаче о «флибах» //Информационные технологии Бедный Ю.Д., Данилов В.Р., Кулев В.А., Мандриков Е.А. Разработка методов построения автоматов с помощью генетических алгоритмов /Сборник тезисов IV межвузовский конференции молодых ученых. СПб.: СПбГУ ИТМО Лобанов П.Г. Использование генетических алгоритмов для решения задачи об «Умном муравье» /Сборник тезисов IV межвузовский конференции молодых ученых. СПб.: СПбГУ ИТМО

24 Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением Публикации по теме (2) 5. Царев Ф.Н., Шалыто А.А. Применение генетического программирования для генерации автоматов в задаче об «умном муравье» /Сборник научных трудов. IV-я Международная научно- практическая конференция «Интегрированные модели и мягкие вычисления в искусственном интеллекте». М.: Физматлит Поликарпова Н.И., Точилин В.Н., Шалыто А.А. Применение генетического программирования для реализации систем со сложным поведением /Сборник научных трудов. IV-я Международная научно-практическая конференция «Интегрированные модели и мягкие вычисления в искусственном интеллекте». М.: Физматлит Лобанов П.Г., Шалыто А.А. Использование генетических алгоритмов для решения задачи об «умном муравье» /XIV Всероссийская научно-методическая конференция «Телематика- 2007». СПб.: СПбГУ ИТМО Т Царев Ф.Н., Шалыто А.А. О построении автоматов с минимальным числом состояний для задачи об «умном муравье» //Сборник докладов X международной конференции по мягким вычислениям и измерениям. СПбГЭТУ «ЛЭТИ». Т.2, 2007.

25 Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением Публикации по теме (3) 9. Поликарпова Н.И., Точилин В.Н., Шалыто А.А. Разработка библиотеки для генерации управляющих автоматов методом генетического программирования //Сборник докладов X международной конференции по мягким вычислениям и измерениям. СПбГЭТУ «ЛЭТИ». Т.2, Мандриков Е.А., Кулев В.А., Шалыто А.А. Построение автоматов с помощью генетических алгоритмов для решения задачи о «флибах» //Сборник докладов X международной конференции по мягким вычислениям и измерениям. СПбГЭТУ «ЛЭТИ». Т.1, Царев Ф.Н., Шалыто А.А. Применение генетического программирования для построения мультиагентной системы одного класса /Материалы международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы» (МВУС`2007). Таганрог: НИИМВС. Т Гунич И.С., Иринев А.В., Шалыто А.А. Автоматный подход к моделированию микроорганизмов с использованием генетических алгоритмов /Материалы международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы» (МВУС`2007). Таганрог: НИИМВС. Т. 2.

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

27 Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением Дополнительная информация Раздел «Верификация» сайта кафедры «Технологии программирования» СПбГУ ИТМО по автоматному программированию

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