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

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

• Выполнил: Бедный Юрий, группа 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

Ход эволюции

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

• Методы:

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

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

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

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

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

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

• x1 → x1  x2, при 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»

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

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