Построение автоматов управления системами со сложным поведением на основе тестов с помощью генетического программирования Федор Николаевич Царев, СПбГУ ИТМО Научный руководитель – докт. техн. наук, профессор, зав. каф. технологий программирования Анатолий Абрамович Шалыто 2009 год

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

3 Ф. Н. Царев Построение автоматов управления системами со сложным поведением на основе тестов с помощью генетического программирования Генетическое программирование

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

5 Ф. Н. Царев Построение автоматов управления системами со сложным поведением на основе тестов с помощью генетического программирования Автоматное и генетическое программирование – предлагаемый метод Метод на основе тестов Каждый тест: входная последовательность событий Input соответствующая ей последовательность выходных воздействий Answer Для новой задачи необходимо подготовить только новые тесты

6 Ф. Н. Царев Построение автоматов управления системами со сложным поведением на основе тестов с помощью генетического программирования Функция приспособленности Основана на вычислении редакционного расстояния между последовательностью выходных воздействий и «правильным ответом» ED – редакционное расстояние transitionsN – число переходов в автомате

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

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

9 Ф. Н. Царев Построение автоматов управления системами со сложным поведением на основе тестов с помощью генетического программирования Операция скрещивания Два варианта – обычное и с учетом тестов Обычное – для каждого номера состояния проводятся следующие операции: Переходы автоматов-родителей объединяются в общий список Элементы списка переставляются случайным образом Элементы списка распределяются по автоматам- потомкам С учетом тестов – переходы, которые используются при обработке нескольких тестов, которые автоматы проходят лучше всего, не затрагиваются

10 Ф. Н. Царев Построение автоматов управления системами со сложным поведением на основе тестов с помощью генетического программирования Операция мутации Каждое из следующих действий производится с вероятностью 5%: Изменение начального состояния Изменение каждого из переходов Изменение на единицу числа переходов для каждого из состояний (уменьшение или увеличение с вероятностью по 0.5)

11 Ф. Н. Царев Построение автоматов управления системами со сложным поведением на основе тестов с помощью генетического программирования Часы с будильником Четыре события: H, M, A, T Две входные переменные: x1, x2 Семь выходных воздействий: z1, z2, z3, z4, z5, z6, z7 Пример системы со сложным поведением из книги Н. И. Поликарповой и А. А. Шалыто «Автоматное программирование»

12 Ф. Н. Царев Построение автоматов управления системами со сложным поведением на основе тестов с помощью генетического программирования Система тестов События, используемые в тестах: H, M, A, T, T [x1], T[x2], T [!x1 & !x2] 38 тестов, описывающих поведение часов в различных режимах работы Размер входных последовательностей – от трех до 12 событий Размер выходных последовательностей – от одного до 12 выходных воздействий

13 Ф. Н. Царев Построение автоматов управления системами со сложным поведением на основе тестов с помощью генетического программирования Построенный автомат Задача – построить автомат из четырех состояний, содержащий 14 переходов – значение функции приспособленности Размер поколения – 2000 В 1482 поколении построен автомат из трех состояний, содержащий 14 переходов, полностью совпадающий с построенным вручную

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

15 Ф. Н. Царев Построение автоматов управления системами со сложным поведением на основе тестов с помощью генетического программирования Направления развития Применение методов верификации моделей программ (model checking) при вычислении функции приспособленности Применение разработанного метода в контексте «обучения с учителем» Разработка программного средства, позволяющего интегрировать генетическое программирование в процесс разработки ПО

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