Применение генетического программирования для реализации систем со сложным поведением Санкт-Петербургский Государственный Университет Информационных Технологий, Механики и Оптики Кафедра «Компьютерных Технологий» Поликарпова Надежда Игоревна Точилин Владимир Николаевич Научный руководитель: д.т.н., профессор Шалыто Анатолий Абрамович

2 Системы со сложным поведением Программные и аппаратные системы часто имеют сложное поведение (например, устройства управления, сетевые протоколы, диалоговые окна, персонажи компьютерных игр,...) Для их реализации применяется автоматный подход: сущность со сложным поведением представляется в виде автоматизированного объекта

3 Проблемы автоматного подхода Объект управления легко реализуется традиционными методами Описание логики (управляющего автомата) производится с помощью графа переходов: + Граф переходов хорошо структурирован + Разработан ряд методов декомпозиции - Для ряда задач эвристическое построение автомата невозможно (или очень сложно) - Часто автомат, построенный вручную, содержит ошибки - Даже если автомат корректен, он часто не оптимален Решение: поручить построение логики системы со сложным поведением машине!

4 Генетическое программирование Генетическое программирование (ГП) – применение генетического алгоритма для оптимизации параметров некоторой модели вычислений В ГП написать программу в данной модели = задать оценочную функцию, определяющую для каждого результата вычисления в данной модели его пригодность (fitness)

5 ГП + автоматы: состояние вопроса Существующие работы по генетической оптимизации автоматов: Простые задачи: распознаватели (parsers) и преобразователи (transducers) Для сложных задач в ГП используют низкоуровневые модели (в т.ч. в виде графов) + Универсальность - Отсутствие высокоуровневой структуры (непонятно человеку) - Большое пространство поиска (требуется много времени) В существующих работах не рассматриваются наиболее актуальные для задач управления автоматы с произвольным числом входов и выходов Решение: использовать в качестве модели вычислений автоматизированный объект (это высокоуровневый вычислитель с произвольным количеством входов и выходов)

6 Постановка задачи Задача построения управляющего автомата: найти такой автомат, что за k шагов работы под его управлением заданный объект управления перейдет в вычислительное состояние с максимальной пригодностью Адаптация генетического алгоритма: Выбор представления автомата в виде особи Адаптация генетических операторов (мутации и скрещивания)

7 Представление автоматов: наивный подход (полные таблицы состояний) В ГП особь – набор хромосом Автомат – набор состояний Удобно сопоставить хромосому каждому состоянию Естественный способ записи хромосомы состояния – табличное представление функций переходов и действий Полная таблица состояния Значения предикатов (аргументов функций переходов и действий) Значение функции переходов (номер целевого состояния) Значение функции действий (множество действий)

8 Мутация и скрещивание полных таблиц состояний Мутация полных таблиц: с некоторой вероятностью может измениться каждая ячейка Скрещивание полных таблиц: одноточечное скрещивание соответствующих столбцов

9 Сокращенные таблицы состояний Проблема полных таблиц – экспоненциальный рост размера хромосомы с увеличением числа предикатов В реальных задачах предикаты имеют «локальную природу» Одно из решений: ограничить число предикатов, значимых в каждом состоянии Сокращенная таблица состояния Множество значимых предикатов

10 Мутация и скрещивание сокращенных таблиц состояний Мутация множества значимых предикатов: каждый значимый предикат с некоторой вероятностью заменяется незначимым Мутация остальной хромосомы происходит так же, как для полных таблиц Выбор значимых предикатов детей при скрещивании сокращенных таблиц При заполнении таблиц детей несколько ячеек родительских таблиц голосуют за значение в одной ячейке таблицы ребенка

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

12 Экспериментальная проверка Схема связей разливочной линии

13 Экспериментальная проверка Управляющий автомат разливочной линии, построенный вручную Управляющий автомат разливочной линии, сгенерированный автоматически с помощью генетического алгоритма

14 Нерешенные задачи Другие решения проблемы экспоненциального роста размерности хромосомы состояния (ограничение числа переходов, деревья принятия решений) Проблема «долгого» вычисления оценочной функции (изменение числа шагов эмуляции в процессе оптимизации, турнирный метод) Более общие постановки задачи построения систем со сложным поведением (не задавать предикаты и действия, оптимизировать некоторые параметры предикатов и действий) Представление результатов генетической оптимизации в виде, более понятном человеку (ввести в оценочную функцию структурную оценку, генерировать систему взаимодействующих автоматов)

15 Спасибо за внимание!