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

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

© 2013, Д.С. Чивилихин

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

Полный текст работы
Презентация

Аннотация

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

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