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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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