Разработка методов совместного применения генетического и автоматного программирования Федор Николаевич Царев, гр. 6538 Магистерская диссертация Научный.

Презентация:



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

Разработка методов совместного применения генетического и автоматного программирования Федор Николаевич Царев, гр Магистерская диссертация Научный.
Разработка методов совместного применения генетического и автоматного программирования Федор Николаевич Царев, гр Магистерская диссертация Научный.
Разработка методов совместного применения генетического и автоматного программирования Федор Николаевич Царев, гр Магистерская диссертация Научный.
Построение автоматов управления системами со сложным поведением на основе тестов с помощью генетического программирования Федор Николаевич Царев, СПбГУ.
Разработка метода совместного применения генетического программирования и конечных автоматов Царев Федор Николаевич, гр Научный руководитель – докт.
Применение метода представления функции переходов с помощью абстрактных конечных автоматов в генетическом программировании Царев Ф. Н. Научный руководитель.
Совместное применение генетического программирования и верификации моделей для построения автоматов управления системами со сложным поведением К. В. Егоров,
Разработка методов машинного обучения на основе генетических алгоритмов и эволюционной стратегии для построения управляющих конечных автоматов Второй этап.
Разработка программного средства 3Genetic для генерации автоматов управления системами со сложным поведением Государственный контракт «Технология.
Применение генетического программирования для генерации автомата в задаче об «Умном муравье» Царев Ф.Н., Шалыто А.А. IV Международная научно-практическая.
Применение генетического программирования для реализации систем со сложным поведением Санкт-Петербургский Государственный Университет Информационных Технологий,
Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» А. А. Давыдов, Д.
Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением Ф. Н. Царев, А. А. Шалыто 2007 год.
Применение методов решения задачи удовлетворения ограничениям для построения управляющих конечных автоматов по сценариям работы Владимир Ульянцев Научный.
Применение генетических алгоритмов для генерации числовых последовательностей, описывающих движение, на примере шага вперед человекоподобного робота Ю.К.
Автоматное программирование А. А. Шалыто Санкт-Петербургский государственный университет информационных технологий, механики и оптики 2009 г.
Применение генетического программирования в задаче поиска усердных бобров Д. О. Соколов, П.В. Федотов, Ф. Н. Царев Научный руководитель – А. А. Шалыто.
1 Метод сокращенных таблиц для генерации автоматов с большим числом входных воздействий Автор Научный руководитель В. Н. Точилин А. А. Шалыто Санкт-Петербургский.
Применение автоматного программирования во встраиваемых системах В. О. Клебан, А. А. Шалыто Санкт-Петербургский государственный университет информационных.
Транксрипт:

Разработка методов совместного применения генетического и автоматного программирования Федор Николаевич Царев, гр Магистерская диссертация Научный руководитель – докт. техн. наук, профессор, зав. каф. технологий программирования Анатолий Абрамович Шалыто 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 Ф. Н. Царев Разработка методов совместного применения генетического и автоматного программирования Спасибо за внимание!