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

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

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

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

5/18 Ф. Н. Царев Разработка методов совместного применения генетического и автоматного программирования Решение задачи без применения автоматов «Жадный» алгоритм На каждом шаге муравей выбирает ближайшую клетку из области видимости, в которой есть еда, и двигается к этой клетке Может быть реализован с помощью автомата с достаточно большим числом состояний

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

7/18 Ф. Н. Царев Разработка методов совместного применения генетического и автоматного программирования Сравнение с методом деревьев решений μ / «жадный» алгоритм 2 состояния 4 состояния 8 состояний 16 состояний 0.01 / / / / поколений, размер поколения – 200 особей Предлагаемый методСуществующий метод

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

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

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

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

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

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

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

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

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

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

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

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