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

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



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

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

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