Правила поведения
<<  Факторы риска и факторы защиты аддиктивного поведения Теория поведения производителя: технологии  >>
Разработка технологии генетического программирования для генерации
Разработка технологии генетического программирования для генерации
Парадигма автоматного программирования
Парадигма автоматного программирования
Решаемая проблема
Решаемая проблема
Рассматриваемая задача – управление моделью беспилотного летательного
Рассматриваемая задача – управление моделью беспилотного летательного
–
«Наивный» метод – полные таблицы переходов
«Наивный» метод – полные таблицы переходов
Предлагаемые методы
Предлагаемые методы
Метод сокращенных таблиц переходов
Метод сокращенных таблиц переходов
Операции мутации и скрещивания для метода сокращенных таблиц переходов
Операции мутации и скрещивания для метода сокращенных таблиц переходов
Метод представления автоматов деревьями решений
Метод представления автоматов деревьями решений
Операция мутации для метода представления автоматов деревьями решений
Операция мутации для метода представления автоматов деревьями решений
Операция скрещивания для метода представления автоматов деревьями
Операция скрещивания для метода представления автоматов деревьями
Алгоритм обрезки недостижимых ветвей
Алгоритм обрезки недостижимых ветвей
Пример работы алгоритма
Пример работы алгоритма
Метод совместного применения конечных автоматов и нейронных сетей
Метод совместного применения конечных автоматов и нейронных сетей
Структура хромосомы
Структура хромосомы
Мутация особи Мутация нейронной сети Мутация конечного автомата
Мутация особи Мутация нейронной сети Мутация конечного автомата
Особенности методов
Особенности методов
Результаты применения генетического программирования
Результаты применения генетического программирования
Прототипы программных средств
Прототипы программных средств
GAAP
GAAP
AutoAnt
AutoAnt
3Genetic
3Genetic
Результаты
Результаты
Выполнение программных индикаторов
Выполнение программных индикаторов
Спасибо за внимание
Спасибо за внимание

Презентация на тему: «Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением». Автор: Fedor Tsarev. Файл: «Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением.ppt». Размер zip-архива: 723 КБ.

Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением

содержание презентации «Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением.ppt»
СлайдТекст
1 Разработка технологии генетического программирования для генерации

Разработка технологии генетического программирования для генерации

автоматов управления системами со сложным поведением

Руководитель проекта – А. А. Шалыто Докладчик – Ф. Н. Царев

Санкт-Петербургский государственный университет информационных технологий, механики и оптики

2 Парадигма автоматного программирования

Парадигма автоматного программирования

Предложено в России в 1991 году Программные системы разрабатываются как системы взаимодействующих автоматизированных объектов управления Система управления является системой взаимодействующих конечных автоматов

Состояния События и входные переменные Выходные воздействия Конечный автомат Система конечных автоматов

Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением

3 Решаемая проблема

Решаемая проблема

Основная сложность в автоматном программировании – построение автоматов В большинстве случаев автоматы проектируются вручную Однако эвристическое построение автоматов часто затруднено или невозможно Решение – автоматическое построение конечных автоматов с помощью генетического программирования

Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением

4 Рассматриваемая задача – управление моделью беспилотного летательного

Рассматриваемая задача – управление моделью беспилотного летательного

аппарата

Предлагаемые методы рассматриваются на примере задачи управления моделью беспилотного летательного аппарата Соревнование на дальность полета Две команды по восемь аппаратов Ограничения: запас топлива, столкновения, аэродинамическое взаимодействие Цель – разработка управляющей программы Была решена путем эвристического построения автоматов

Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением

5 –

+

+

Аэродинамическое взаимодействие

Области повышенного сопротивления воздуха

Области пониженного сопротивления воздуха

20°

20°

20°

20°

Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением

6 «Наивный» метод – полные таблицы переходов

«Наивный» метод – полные таблицы переходов

Естественный способ записи хромосомы состояния – табличное представление функций переходов и действий Полная таблица состояния

Значения предикатов (аргументов функций переходов и действий)

Значение функции действий (множество действий)

Значение функции переходов (номер целевого состояния)

Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением

7 Предлагаемые методы

Предлагаемые методы

Метод сокращенных таблиц переходов Метод представления автоматов деревьями решений Метод совместного применения конечных автоматов и нейронных сетей

Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением

8 Метод сокращенных таблиц переходов

Метод сокращенных таблиц переходов

Проблема полных таблиц – экспоненциальный рост размера хромосомы с увеличением числа предикатов В реальных задачах предикаты имеют «локальную природу» Одно из решений: ограничить число предикатов, значимых в каждом состоянии

Множество значимых предикатов

Сокращенная таблица переходов

Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением

9 Операции мутации и скрещивания для метода сокращенных таблиц переходов

Операции мутации и скрещивания для метода сокращенных таблиц переходов

Выбор значимых предикатов детей при скрещивании сокращенных таблиц

Мутация множества значимых предикатов: каждый значимый предикат с некоторой вероятностью заменяется незначимым Мутация остальной хромосомы происходит так же, как для полных таблиц

При заполнении таблиц детей несколько ячеек родительских таблиц голосуют за значение в одной ячейке таблицы ребенка

Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением

10 Метод представления автоматов деревьями решений

Метод представления автоматов деревьями решений

Дерево решений – способ представления функции от логических аргументов Конечный автомат представляется в виде набора деревьев решений – по одному на каждое состояние

Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением

11 Операция мутации для метода представления автоматов деревьями решений

Операция мутации для метода представления автоматов деревьями решений

Мутация автомата: с вероятностью 0.5 случайное изменение стартового состояния; мутацию случайного состояния. Мутация дерева решений: рекурсивный алгоритм; если текущий узел является листом, то обязательно, а для внутренних узлов с вероятностью P, вернуть случайно сгенерированное дерево решений; иначе равновероятно перейти в одно из поддеревьев.

Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением

12 Операция скрещивания для метода представления автоматов деревьями

Операция скрещивания для метода представления автоматов деревьями

решений

Выбирает два поддерева: одно из первого дерева решений, второе из второго, а затем меняет их местами

Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением

13 Алгоритм обрезки недостижимых ветвей

Алгоритм обрезки недостижимых ветвей

Модификация алгоритма обхода дерева в глубину При рекурсивном спуске запоминаются переменные, по которым уже проводилось расщепление Если переменная встречается второй раз, то текущий узел, заменяется на корень достижимого поддерева этого узла Решение о том, какое из поддеревьев достижимо, принимается на основании запомненных значений переменных

Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением

14 Пример работы алгоритма

Пример работы алгоритма

Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением

15 Метод совместного применения конечных автоматов и нейронных сетей

Метод совместного применения конечных автоматов и нейронных сетей

Система управления = нейронная сеть + конечный автомат Нейронная сеть преобразует вещественные входные переменные в логические

Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением

16 Структура хромосомы

Структура хромосомы

Особь = две системы управления беспилотным объектом Особь из двух систем – для учета взаимодействия объектов

Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением

17 Мутация особи Мутация нейронной сети Мутация конечного автомата

Мутация особи Мутация нейронной сети Мутация конечного автомата

Скрещивание особей Скрещивание автоматов Скрещивание нейронных сетей

Скрещивание и мутация для метода совместного применения конечных автоматов и нейронных сетей

Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением

18 Особенности методов

Особенности методов

Метод сокращенных таблиц переходов – в каждом состоянии переход выбирается на основе значений только небольшого числа входных переменных Метод представления деревьев решений – в каждом состоянии переменные имеют разные приоритеты Метод совместного применения нейронных сетей и конечных автоматов позволяет автоматически строить входные переменные логического типа на основе переменных произвольного числового типа

Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением

19 Результаты применения генетического программирования

Результаты применения генетического программирования

Построение вручную

Деревья решений

Сокращенные таблицы

Автоматы + нейронные сети

Высокая

Средняя

Средняя

Низкая

Сложность системы управления

7 автоматов, 24 состояния

Дальность полета

От 200 до 225, в среднем – 215

От 200 до 305,в среднем – 235

От 210 до 310,в среднем – 240

От 200 до 250,в среднем – 220

Степень автоматизации построения

1 автомат, 6 состояний

1 автомат, 6 состояний

2 автомата по 6 состояний, 2 нейронных сети

Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением

20 Прототипы программных средств

Прототипы программных средств

GAAP – поддерживает метод сокращенных таблиц переходов autoant – поддерживает метод представления автоматов деревьями решений 3genetic – поддерживает метод совместного применения конечных автоматов и нейронных сетей

Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением

21 GAAP

GAAP

Cодержит набор компонентов для визуализации и анализа работы генетического алгоритма Содержит компоненты для реализации распределенных вычислений функции приспособленности, что часто является наиболее затратной по времени частью генетического алгоритма

Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением

22 AutoAnt

AutoAnt

Поддерживает метод представления автоматов деревьями решений Содержит набор классов и интерфейсов, позволяющих использовать генетические алгоритмы в других приложениях, написанных на Java

Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением

23 3Genetic

3Genetic

Имеет модульную архитектуру Генетические алгоритмы и способы представления хромосом реализованы в виде подключаемых модулей

Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением

24 Результаты

Результаты

Разработаны три метода генетического программирования для генерации автоматов управления системами со сложным поведением Эффективность методов продемонстрирована на задаче построения системы управления моделью беспилотного летательного аппарата Разработаны прототипы программных средств, поддерживающих указанные методы

Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением

25 Выполнение программных индикаторов

Выполнение программных индикаторов

Защищена одна диссертация на соискание ученой степени кандидата технических наук – Лобанов П. Г. Использование генетических алгоритмов для генерации конечных автоматов Опубликовано 12 статей в ведущих научных журналах Получено одно свидетельство об официальной регистрации программы для ЭВМ

Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением

26 Спасибо за внимание

Спасибо за внимание

Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением

«Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением»
http://900igr.net/prezentacija/pedagogika/razrabotka-tekhnologii-geneticheskogo-programmirovanija-dlja-generatsii-avtomatov-upravlenija-sistemami-so-slozhnym-povedeniem-138821.html
cсылка на страницу
Урок

Педагогика

135 тем
Слайды
900igr.net > Презентации по педагогике > Правила поведения > Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением