Генетика
<<  По технологии про еду Пол Кругман о роли образования и знаний в свете экономических трансформаций начала второго десятилетия XXI века  >>
Применение генетического программирования для построения автоматов,
Применение генетического программирования для построения автоматов,
Автоматное программирование
Автоматное программирование
Преимущества автоматного подхода
Преимущества автоматного подхода
Инструментальное средство UniMod (1)
Инструментальное средство UniMod (1)
Инструментальное средство UniMod (2)
Инструментальное средство UniMod (2)
Инструментальное средство UniMod (3)
Инструментальное средство UniMod (3)
Решаемая проблема
Решаемая проблема
Этапы решения проблемы
Этапы решения проблемы
Три рассматриваемые задачи
Три рассматриваемые задачи
«Простая» задача – задача об «Умном муравье»
«Простая» задача – задача об «Умном муравье»
Эвристическое построение задачу не решает
Эвристическое построение задачу не решает
Решение «простой» задачи
Решение «простой» задачи
«Сложная» задача – задача «Беспилотные летательные объекты»
«Сложная» задача – задача «Беспилотные летательные объекты»
Беспилотный летательный объект
Беспилотный летательный объект
–
Столкновение объектов
Столкновение объектов
Решение (1)
Решение (1)
Решение (2)
Решение (2)
Решение (3)
Решение (3)
Результаты применения генетического программирования
Результаты применения генетического программирования
«Народная» задача – «Разливочная линия»
«Народная» задача – «Разливочная линия»
Решения задачи
Решения задачи
Результаты
Результаты
Спасибо за внимание
Спасибо за внимание

Презентация: «Эвристические методы моделирования 7 класс». Автор: Fedor Tsarev. Файл: «Эвристические методы моделирования 7 класс.ppt». Размер zip-архива: 594 КБ.

Эвристические методы моделирования 7 класс

содержание презентации «Эвристические методы моделирования 7 класс.ppt»
СлайдТекст
1 Применение генетического программирования для построения автоматов,

Применение генетического программирования для построения автоматов,

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

Ф. Н. Царев, А. А. Шалыто 2007 год

2 Автоматное программирование

Автоматное программирование

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

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

Царев Ф. Н. Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением

3 Преимущества автоматного подхода

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

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

Царев Ф. Н. Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением

4 Инструментальное средство UniMod (1)

Инструментальное средство UniMod (1)

Инструментальное средство для поддержки автоматного программирования Создано в рамках ФЦНТП «Исследования и разработки по приоритетным направлениям развития науки и техники» на 2002-2006 годы по приоритетному направлению «Информационно-телекоммуникационные системы» Критическая технология – «Технологии производства программного обеспечения» Вошел в число 15 наиболее инновационно перспективных и социально значимых проектов Федерального агентства по науке и инновациям

Царев Ф. Н. Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением

5 Инструментальное средство UniMod (2)

Инструментальное средство UniMod (2)

Семь автоматов Вручную Автоматическая генерация Вручную

Царев Ф. Н. Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением

6 Инструментальное средство UniMod (3)

Инструментальное средство UniMod (3)

Один из автоматов – AL

Царев Ф. Н. Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением

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

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

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

Царев Ф. Н. Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением

8 Этапы решения проблемы

Этапы решения проблемы

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

Царев Ф. Н. Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением

9 Три рассматриваемые задачи

Три рассматриваемые задачи

«Простая» задача – задача об «Умном муравье» «Сложная» задача – задача «Беспилотные летательные объекты» «Народная» задача – «Разливочная линия»

Царев Ф. Н. Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением

10 «Простая» задача – задача об «Умном муравье»

«Простая» задача – задача об «Умном муравье»

Тор – 32x32 89 клеток с едой 200 ходов Расположение еды и начальная позиция муравья фиксированы Цель – создать муравья, который съест всю еду Муравей = конечный автомат

Царев Ф. Н. Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением

11 Эвристическое построение задачу не решает

Эвристическое построение задачу не решает

Пять состояний, за 200 ходов съедается 81 единица еды или все 89 единиц еды за 314 ходов

Царев Ф. Н. Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением

12 Решение «простой» задачи

Решение «простой» задачи

Известные решения: 13 состояний (1992) 11 состояний (1993) 8 состояний (1999) Известные подходы – кодирование битовыми строками + генетический алгоритм Предлагаемый подход – генетическое программирование Построены два автомата с 7 состояниями после перебора 160 и 230 млн. автоматов Полный перебор ~3·1018 автоматов

Царев Ф. Н. Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением

13 «Сложная» задача – задача «Беспилотные летательные объекты»

«Сложная» задача – задача «Беспилотные летательные объекты»

Соревнование на дальность полета Две команды по восемь объектов Ограничения: запас топлива, столкновения, аэродинамическое взаимодействие Цель – разработка управляющей программы Задача заочного тура VI Открытой Всесибирской олимпиады по программированию (2005 год) Была решена при участии автора путем эвристического построения автоматов http://is.ifmo.ru/unimod-projects/plates/

Царев Ф. Н. Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением

14 Беспилотный летательный объект

Беспилотный летательный объект

Бортовой компьютер

Двигатель

Аэродинамические рули

Бак с топливом

Царев Ф. Н. Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением

15 –

+

+

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

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

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

20°

20°

20°

20°

Царев Ф. Н. Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением

16 Столкновение объектов

Столкновение объектов

Столкновение – абсолютно упругое и описывается законами сохранения энергии и импульса При этом, если относительная скорость столкновения > 1 м/с, то оба объекта выбывают из соревнования

Царев Ф. Н. Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением

17 Решение (1)

Решение (1)

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

Царев Ф. Н. Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением

18 Решение (2)

Решение (2)

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

Царев Ф. Н. Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением

19 Решение (3)

Решение (3)

Мутация особи Мутация системы управления летательным объектом Мутация нейронной сети Мутация элемента сети Мутация конечного автомата Изменение начального состояния Мутация перехода Скрещивание особей Скрещивание систем управления летающей тарелкой Скрещивание автоматов Скрещивание нейронных сетей

Царев Ф. Н. Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением

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

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

За сутки была построена управляющая система, содержащая нейронную сеть и один автомат с шестью состояниями (вместо семи автоматов с 21 состоянием)

Построенная с помощью ГП система

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

Среднее

216,55

212,59

Минимум

203,05

203,44

Максимум

241,11

225,09

Царев Ф. Н. Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением

21 «Народная» задача – «Разливочная линия»

«Народная» задача – «Разливочная линия»

Задача: налить как можно больше бутылок за заданный промежуток времени

Царев Ф. Н. Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением

22 Решения задачи

Решения задачи

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

Царев Ф. Н. Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением

23 Результаты

Результаты

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

Царев Ф. Н. Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением

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

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

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

Царев Ф. Н. Применение генетического программирования для построения автоматов, управляющих системами со сложным поведением

«Эвристические методы моделирования 7 класс»
http://900igr.net/prezentacija/biologija/evristicheskie-metody-modelirovanija-7-klass-264525.html
cсылка на страницу
Урок

Биология

136 тем
Слайды
900igr.net > Презентации по биологии > Генетика > Эвристические методы моделирования 7 класс