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

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

3 Ф. Н. Царев Разработка методов совместного применения генетического и автоматного программирования Генетическое программирование Использование принципа естественного отбора Операции мутации и скрещивания

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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