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

Номер гранта:14-01-00551
Область научного знания:математика, механика, информатика
Тип конкурса: («а» (до 2016))(«а») инициативные научные проекты
Год выполнения:2014г.
Руководитель: Шалыто А.А.
Статус заявки:поддержана

Аннотация к заявке:

Для автоматизированного построения управляющих конечных автоматов предлагается разработать новый класс муравьиных алгоритмов. Необходимость разработки нового класса муравьиных алгоритмов обосновывается тем, что применение классических муравьиных алгоритмов для построения управляющих конечных автоматов не дает существенных преимуществ по сравнению с эволюционными алгоритмами.Отличие разрабатываемого класса алгоритмов от классических муравьиных алгоритмов заключается в том, что вместо графа конструирования будет использоваться динамически изменяющийся граф поиска. Вершины данного графа будут соответствовать управляющим конечным автоматам, а ребра – их небольшим изменениям (мутациям). Из-за большого размера пространства поиска явное построение данного графа поиска осуществляться не будет. Вместо этого в процессе работы алгоритма будет строиться часть этого графа, в чем заключается отличие от классического муравьиного алгоритма. Также, если в классических муравьиных алгоритмах допустимые решения соответствуют путям в графе конструирования, то в предлагаемом подходе решения соответствуют вершинам графа поиска. Таким образом, предлагаемые алгоритмы сочетают в себе черты классических муравьиных алгоритмов и эволюционных алгоритмов.Настоящий проект является продолжением исследований по гранту РФФИ № 10-01-0654-а «Разработка методов машинного обучения на основе генетического программирования для построения управляющих конечных автоматов».

Аннотация к отчету по результатам реализации проекта:

Разработаны методы представления вершин и ребер графа поиска для муравьиных алгоритмов построения управляющих конечных автоматов. На их основе разработано три муравьиных алгоритма для построения управляющих конечных автоматов: параллельный алгоритм pMuACO, в каждом потоке запускающищий муравьиный алгоритм MuACO, параллельный алгоритм psMuACO, использующий для генерации начального решения точный метод генерации управляющих конечных автоматов по сценариям работы на основе решения задачи выполнимости булевой формулы, и параллельный алгоритм pstMuACO, в котором набор сценариев разбивается на части для независимого запуска точного метода и получения нескольких начальных решений для параллельного муравьиного алгоритма. Разработан метод "ленивого" вычисления значения функции приспособленности автомата, повышающий эффективность алгоритма MuACO при решении задачи генерации управляющего конечного автомата только по сценариям работы. В разработанных алгоритмах был применен принцип "symmetry breaking". Также было предложено применить в функции приспособленности новый компонент, основанный на графе совместимости дерева сценариев. Разработана модель, позволяющая генерировать управляющие конечные автоматы, переходы которых могут быть помечены булевыми формулами общего вида. Предлагаемые алгоритмы были адаптированы, в результате чего был разработан метод построения автоматов Мура. Данные результаты позволили расширить применимость разрабатываемых в проекте методов и алгоритмов. Проведено экспериментальное иследование методов выбора значений параметров муравьиных алгоритмов. Было установлено, что программное средство irace, реализующее метод iterated racing, обеспечивает стабильную работу муравьиного алгоритма на тестовом наборе при достаточном времени, отведенном на настройку. Кроме того, увеличение времени, отведенного на настройку, в среднем увеличивает производительность муравьиного алгоритма. Проведено исследование возможности применения эмпирических моделей сложности для предсказания времени работы SAT-солверов при генерации управляющих конечных автоматов. Было установлено, что хотя метод обеспечивает достаточно высокую точность предсказания, его применение не приводит к уменьшению общего времени работы, поскольку вычисление характеристик булевой формулы занимает больше времени, чем нахождение выполняющей подстановки. Проведено общее экспериментальное исследование предложенных в проекте муравьиных алгоритмов. Было установлено, что наиболее эффективным среди однопоточных алгоритмов является алгоритм SAT+MuACO, основанный на муравьином алгоритме и использующий для нахождения начального решения метода на основе сведения к SAT. Среди многопоточных алгоритмов лучшим оказался алгоритм pstMuACO, использующий метод на основе SAT для получения нескольких различных начальных решений для параллельного муравьиного алгоритма. По итогам проведенных работ была опубликована статья в журнале "Автоматика и телемеханика", входящем в перечень ВАК, cделано три доклада на международных конференциях BIOMA'14, INDIN’15 и GECCO'16, опубликовано две статьи в изданиях, индексируемых в системах Web Of Science и Scopus, сделано три доклада на всероссийских конференциях. Один из исполнителей проекта, Чивилихин Даниил Сергеевич, подготовил и успешно защитил в 2015 году диссертацию на соискание ученой степени кандидата технических наук на тему "Генерация конечных автоматов на основе муравьиных алгоритмов". Поданная в 2015 году в журнал IEEE Transactions on Industrial Informatics (импакт-фактор 4,708) статья "Reconstruction of Function Block Logic using Metaheuristic Algorithm" прошла три стадии рецензирования c результатами "Reject & resubmit", "Major revision", "Minor revision" - ожидается, что статья выйдет в 2016 году.
Аннотации к заявке и отчету приведены в авторской редакции. по состоянию на 28.03.2024.

Библиография

Приведена в авторской редакции.
Помог ли вам материал?
0    0