Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением Ф. Н. Царев, А. А. Шалыто 2007 год

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16 Царев Ф. Н. Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением Столкновение объектов Столкновение – абсолютно упругое и описывается законами сохранения энергии и импульса При этом, если относительная скорость столкновения > 1 м/с, то оба объекта выбывают из соревнования

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

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

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

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

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

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

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

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