УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»

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

© 2008 Ю.Д. Бедный
Научный руководитель - докт. техн. наук, профессор А. А. Шалыто

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

Магистерская диссертация
Исходные коды
Презентация

Аннотация

Работа состоит их двух основных частей. В первой части устанавливается неприменимость алгоритма Баума-Велша для построения некоторого класса задач скрытых марковских моделей. Далее рассматривается метод, в котором генетические алгоритмы используются для выбора начальных параметров алгоритма Баума-Велша. Такая модификация приводит к значительному улучшению результатов работы алгоритма Баума-Велша. Автором предлагается применять рассмотренный метод для решения практической задачи - нахождения ошибок в автоматах. Рассматривается один тип возможных ошибок - неучтенный переходы. Поставленная задача успешно решается. При этом производится сравнения и с другими возможными подходами, например, с алгоритмом случайного поиска.

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