Бедный Юрий, группа 6538 Научный Шалыто Анатолий Абрамович, докт техн наук, профессор, спбгу итмо




НазваниеБедный Юрий, группа 6538 Научный Шалыто Анатолий Абрамович, докт техн наук, профессор, спбгу итмо
К.Ю. Тема охватывает Present, Past and Future Simple. Предназна
Дата22.07.2013
Размер1.88 Mb.
ТипЗадача


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

  • Выполнил: Бедный Юрий, группа 6538

  • Научный руководитель: Шалыто Анатолий Абрамович, докт.техн.наук, профессор, СПбГУ ИТМО


Генетические алгоритмы



Генетические алгоритмы и автоматы

  • Теория игр (итерированная дилемма узника)

  • Молекулярная биология (выбор праймера для ПЦР)

  • Роботехника (движение человекоподобного робота)

  • Зоология (искусственная этология)

  • Теория клеточных автоматов (DCT)

  • Регрессия (задача «о Флибах»)

  • Задача управления (задача об «Умном муравье»)

  • Задачи оптимизации

  • Проектирование логических схем

  • Распознавание изображений

  • Распознавание языков



В работе генетические алгоритмы и автоматы применяются для:

  • Построения моделей максимального правдоподобия одного класса. Задача: поиск ошибок в автоматах с помощью скрытых марковских моделей.

  • Решения нетривиальных задач оптимального управления. Задача: построение системы управления танком в игре Robocode.



Модели максимального правдоподобия. Скрытые марковские модели: λ=(A, B, π)

  • Наблюдения: O=O1O2…OT

  • Состояния: Q=q1q2…qT

  • Три классические задачи:

  • Определить P(O|λ). Forward-Backward: O(TN2)

  • Найти Q для max P(O|λ). Viterbi: O(TN2)

  • Найти λ для max P(O|λ). Baum-Welch: как повезет



Недостатки алгоритма Баума-Велша

  • Успешно применяется для решения актуальных задач – распознавание речи, предсказание структуры белка,…

  • Но имеются существенные недостатки:

  • Поскольку алгоритм градиентного спуска – застревание в локальных экстремумах

  • Как следствие – необходимость тщательного выбора начальных параметров



Поиск структуры графа – переходов с ненулевой вероятностью – с помощью генетических алгоритмов. Won K., Hamelryck T., Prugel-Bennett A., Krogh A. Evolving Hidden Markov Models for Protein Secondary Structure Prediction / Proceedings of the IEEE. 2005.



Предлагается выяснить когда BW алгоритм не работает без ГА и на сколько эффективно применение ГА в этом случае. «Сильно детерминированные» модели



«Сильно детерминированные» модели. Гипотеза и проверка

  • Основное наблюдение, не отмеченное ранее – чем более «детерминирована» матрица переходов, тем хуже работает BW. Тем важнее использовать генетические алгоритмы.



Проверка гипотезы. Построение модели максимального правдоподобия

  • Один переход с большой вероятностью и не более двух – с малой. Граф связен.

  • N = 12, M = 3, чтобы задача была сложной:

  • пространство поиска (N2/2)N ≈ 2·1022

  • Набор из 10 входных последовательностей

  • Длина каждой – 200 элементов

  • Несколько десятков экспериментов



Типичный пример. Сравнение с алгоритмом случайного поиска

  • Исходная модель: -690

  • Оптимизированная модель: -678

  • Рассматриваемый метод: -675

  • Может быть задача не сложна?

  • Два алгоритма случайного поиска: -824



Ход эволюции



Есть ли практическая польза? Поиск ошибок в автоматах с помощью скрытых марковских моделей

  • Методы:

  • Верификация

  • Тестирование

  • Преимущества предлагаемого метода:

  • не требует изменения структуры автомата

  • не требует добавления отладочной информации



Тип ошибок – неучтенные переходы между состояниями

  • x1x1x2, при x2=1



Результаты по первой части

  • Эмпирически установлена неприменимость BW алгоритма при построении моделей максимального правдоподобия некоторого класса HMM

  • Для указанного класса показана эффективность метода построения модели максимального правдоподобия, основанного на использовании генетических алгоритмов

  • Предложена и решена задача поиска ошибок одного типа в автоматах



Решение нетривиальных задач управления. Примеры и актуальность.

  • Беспилотным летательным аппаратом

  • Наземным средством передвижения

  • Различными системами этих средств (двигателем, системой стабилизации)

  • Бытовыми устройствами (лифтом, телевизором)

  • Транспортными потоками

  • Виртуальными объектами в играх и моделях (танком в игре Robocode, футболистами в виртуальном футболе)



Описание задачи



Формальная постановка задачи

  • Выделим n существенных для задачи управления вещественных параметров

  • Множество значений, принимаемых данными параметрами – Q = Rn

  • Временной интервал разбит на T мин. интервалов

  • Фазовая кривая φ – элемент QT, на момент t: φt

  • Качество управления – функция g: QT → R

  • Функция управления –

  • Вспомогательная функция

  • Начальные условия φ0 – элемент Rn

  • Задача управления –



Проблемы, возникающие при решении задачи

  • Зависимости между параметрами сложны. Задаются функцией h в неявном виде системой дифференциальный уравнений. Сложно решить аналитически.



Автоматный подход

  • При решении задачи управления часто можно выделить состояния, в которых может находиться объект управления

  • Количество различных координат функции управления полагается равным количеству состояний автомата

  • Координата функции управления управляет объектом исходя только из значений параметров в настоящий момент времени



Недостатки автоматного подхода

  • Задача эвристического определения конечного множества воздействий трудна

  • Сложность эвристического выбора компромисса между числом воздействий и размером пространства, на котором решается задача управления

  • Сложность эвристического построения графа переходов автомата, в частности, задания условий на переходах



Предлагаемый метод. Основная идея – применение ГА для автоматического построения автомата

  • Метод – программирование с экспрессией генов

  • Решение задачи управления – автомат – особь генетического алгоритма. Необходимо выбрать способ кодирования

  • Функция приспособленности ГА выражается через функцию g оценки качества решения. Определяется задачей

  • Генетические операции (мутация, скрещивание, отбор) – стандартные для программирования с экспрессией генов



Представление решения задачи управления в виде хромосомы



Построение функции, отображающей из Rn в R



Апробация. Создание системы управления танком в игре Robocode



Параметры



Контролируемые параметры и базовые функции



Результаты поединков (100 раундов)



Заключение (результаты)

  • Эмпирически установлена неприменимость BW алгоритма при построении моделей максимального правдоподобия некоторого класса HMM

  • Для указанного класса показана эффективность метода построения модели максимального правдоподобия, основанного на использовании генетических алгоритмов

  • Предложена и решена задача поиска ошибок одного типа в автоматах

  • Предложен метод решения задач оптимального управления

  • Метод успешно опробован для построения системы управления танком в игре Robocode



Публикации

  • Государственный контракт: «Технология генетического программирования для генерации автоматов управления системами со сложным поведением»

  • Труды V Межвузовской конференции молодых ученых, 2008

  • Труды XII Всероссийской конференции «Фундаментальные исследования и инновации в технических Университетах», 2008

  • IV международная конференции по проблемам управления, 2009

  • XI Международной конференции по мягким вычислениям и измерениям, 2008

  • Конкурс грантов 2008 года для студентов и аспирантов ВУЗов и академических институтов

  • XV Всероссийская научно-методическая конференция «Телематика'2008»

  • На рецензию в журнал «Известия РАН. Теория и системы управления»



Спасибо за внимание! Вопросы…



Похожие:

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

Бедный Юрий, группа 6538 Научный Шалыто Анатолий Абрамович, докт техн наук, профессор, спбгу итмо iconРазвитие инноваций в спбгу итмо н. Р. Тойвонен Проректор спбгу итмо 28. 09. 2010 Нормативная база развития инноваций
Управление: модернизация системы управления вузом, направленная на обеспечение его динамичного развития и финансовой устойчивости,...

Бедный Юрий, группа 6538 Научный Шалыто Анатолий Абрамович, докт техн наук, профессор, спбгу итмо iconИсследовательский центр спбгу итмо «Технологии автоматного программирования» Научный
Комплексное решение для организации услуг ott. Транскодирование, доставка контента, управление абонентами

Бедный Юрий, группа 6538 Научный Шалыто Анатолий Абрамович, докт техн наук, профессор, спбгу итмо iconСонячна активність та захворюваність
Артем Чуйков Кіровоградський державний педагогічний університет імені Володимира Винниченко, м. Кіровоград Науковий керівник – докт...

Бедный Юрий, группа 6538 Научный Шалыто Анатолий Абрамович, докт техн наук, профессор, спбгу итмо iconНубіп україни технічний навчально-науковий інститут Факультет інженерії агробіосистем Бойко Юрій Васильович студент магістратури Науковий керівник, докт., техн., наук, професор Ю. Г. Сухенко Науковий консультант, аспірант М. Магістерська робота на тему
Дослідження і проектування машинної технології виробництва дизельного біопалива з удосконаленням процесу кавітаційного змішування...

Бедный Юрий, группа 6538 Научный Шалыто Анатолий Абрамович, докт техн наук, профессор, спбгу итмо iconКретов В. С., доктор техн наук, профессор Котов М. Н
Коммутаторы S3100 не нуждаются во внешнем питании. Они питаются за счет технологии PoE, поэтому из можно расположить где угодно

Бедный Юрий, группа 6538 Научный Шалыто Анатолий Абрамович, докт техн наук, профессор, спбгу итмо iconДиссертация на соискание ученой степени кандидата филологических наук
Научный доктор филологических наук, профессор Воробьев Василий Петрович

Бедный Юрий, группа 6538 Научный Шалыто Анатолий Абрамович, докт техн наук, профессор, спбгу итмо iconОснователь: член-корреспондент ран, профессор, доктор химических наук О. А. Алекин Основатель: член-корреспондент ран, профессор, доктор химических наук О. А. Алекин
Основатель: член-корреспондент ран, профессор, доктор химических наук О. А. Алекин Основатель: член-корреспондент ран, профессор,...

Бедный Юрий, группа 6538 Научный Шалыто Анатолий Абрамович, докт техн наук, профессор, спбгу итмо iconВведение в байесовские сети
Алгоритмы для Интернета, итмо & спбгу с. Петербург, 26 октября 2006 Рук семинара

Бедный Юрий, группа 6538 Научный Шалыто Анатолий Абрамович, докт техн наук, профессор, спбгу итмо iconНаучный профессор, д м. н. Опарин Анатолий Георгиевич Аспирант: Титкова Анна Владимировна
Место воспаления при хронической обструктивной болезни легких и его влияние на развитие гастроэзофагеальной рефлюксной болезни

Разместите кнопку на своём сайте:
rpp.nashaucheba.ru


База данных защищена авторским правом ©rpp.nashaucheba.ru НашаУчеба
связаться с администрацией
rpp.nashaucheba.ru
Главная страница