Heuristic optimization methods for linear ordering of automata

Стремительное развитие общества связано с двумя ключевыми направлениями науки и технологий: методами работы с большими данными (Big Data) и искусственным интеллектом (Artificial Intelligence). Есть распространенное мнение, что до 80% процесса анализа данных — это время, потраченное на их подготовку. Одним из аспектов подготовки данных к анализу является структурирование и приведение в порядок наборов данных, так называемое data tidying. Отношения порядка встречаются повсеместно: мы встречаем их, когда рассматриваем числа, булевы алгебры, разбиения, мультимножества, графы, логические формулы и многие другие математические объекты. С одной стороны, отношения порядка используются для представления данных и знаний, с другой стороны, они служат важными инструментами для описания моделей и методов анализа данных, таких как деревья решений, случайные леса, пространства версий, правила ассоциации и т. д. Поскольку серьезным ограничением многих методов анализа шаблонов является вычислительная сложность, важно иметь эффективный алгоритм упорядочивания данных. В данной работе рассматриваются детерминированные автоматы без выходных сигналов и исследуется задача линейного упорядочения таких автоматов, заключающаяся в построении на множестве состояний автомата данного линейного порядка, который будет согласован с действием каждого входного сигнала автомата. Для решения этой задачи мы рассматриваем эвристические методы глобальной оптимизации: метод имитации отжига и алгоритм пчелиной колонии. Для обоих методов написана программная реализация и проведено тестирование на автоматах специального вида.