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

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

3 Ф. Н. Царев Разработка методов совместного применения генетического и автоматного программирования Автоматное программирование

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

5 Ф. Н. Царев Разработка методов совместного применения генетического и автоматного программирования Генетическое программирование

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

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

8 Ф. Н. Царев Разработка методов совместного применения генетического и автоматного программирования Существующие методы представления автоматов Метод сокращенных таблиц переходов Метод представления автоматов деревьями решений Метод совместного применения конечных автоматов и нейронных сетей Разработаны в СПбГУ ИТМО

9 Ф. Н. Царев Разработка методов совместного применения генетического и автоматного программирования Задача «Умный муравей–3» Игровое поле – тор 32x32 В каждой клетке еда есть с вероятностью μ Функция приспособленности вычисляется с помощью моделирования работы на случайных полях

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

11 Ф. Н. Царев Разработка методов совместного применения генетического и автоматного программирования Дерево решений и конечный распознаватель Дерево решений Конечный распознаватель

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

13 Ф. Н. Царев Разработка методов совместного применения генетического и автоматного программирования Сравнение с методом деревьев решений Значение параметра μ 2 состояния 4 состояния 8 состояний 16 состояний

14 Ф. Н. Царев Разработка методов совместного применения генетического и автоматного программирования Автоматное и генетическое программирование – метод на основе тестов Каждый тест – пара из входной последовательности событий Input и соответствующей ей последовательности выходных воздействий Answer Функция приспособленности отражает то, насколько «хорошо» автомат проходит эти тесты Для новой задачи необходимо подготовить только новые тесты Задача похожа на построение конечного преобразователя

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

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

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

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

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

20 Ф. Н. Царев Разработка методов совместного применения генетического и автоматного программирования Алгоритм генетического программирования Стратегия отбора – элитизм (напрямую переходит 10% наилучших особей) Используются «большие» и «малые» мутации поколений Размер поколения – 2000

21 Ф. Н. Царев Разработка методов совместного применения генетического и автоматного программирования Часы с будильником Четыре события: H, M, A, T Две входные переменные: x1, x2 Семь выходных воздействий: z1, z2, z3, z4, z5, z6, z7

22 Ф. Н. Царев Разработка методов совместного применения генетического и автоматного программирования Обработка входных переменных При построении автоматов вручную используются так называемые сторожевые условия (guard conditions): e1 [!x1 & (x2 | x3)] Это необходимо учитывать при построении тестов

23 Ф. Н. Царев Разработка методов совместного применения генетического и автоматного программирования Система тестов События, используемые в тестах: H, M, A, T, T [x1], T[x2], T [!x1 & !x2] 38 тестов T, M, H, T, T, T, M, T, H, H, T, M z5, z2, z1, z5, z5, z5, z2, z5, z1, z1, z5, z2 A, T, M, H, T, T, T, M, T, H, H, T, M z5, z4, z3, z5, z5, z5, z4, z5, z3, z3, z5, z4 A, A, T [!x1 & !x2], M, H, T [!x1 & !x2], T [!x1 & !x2], T [!x1 & !x2], M, T [!x1 & !x2], H, H, T [!x1 & !x2], M z5, z2, z1, z5, z5, z5, z2, z5, z1, z1, z5, z2 A, A, A, A, H z7, z3

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

25 Ф. Н. Царев Разработка методов совместного применения генетического и автоматного программирования Ход эволюции

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

27 Ф. Н. Царев Разработка методов совместного применения генетического и автоматного программирования Направления развития Совместное применение метода построения автоматов на основе тестов с: методом сокращенных таблиц переходов методом представления автоматов деревьями решений Применение методов верификации моделей программ (model checking) при вычислении функции приспособленности

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