Эта публикация цитируется в 1 статье

Научный отдел
Информатика

Heuristic optimization methods for linear ordering of automata

[Эвристические методы оптимизации для линейного упорядочивания автоматов]

R. A. Farakhutdinov

Saratov State University, 83 Astrakhanskaya St., Saratov 410012, Russia

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

Ключевые слова: наука о данных, оптимизация, автомат, линейный порядок, имитация отжига, пчелиная колония.

УДК: 519.688

Поступила в редакцию: 22.11.2023
Исправленный вариант: 04.03.2024

Язык публикации: английский

DOI: 10.18500/1816-9791-2025-25-2-295-302