Для цитирования:
Farakhutdinov R. A. Heuristic optimization methods for linear ordering of automata [Фарахутдинов Р. А. Эвристические методы оптимизации для линейного упорядочивания автоматов] // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2025. Т. 25, вып. 2. С. 295-302. DOI: 10.18500/1816-9791-2025-25-2-295-302, EDN: ZTYLML
Heuristic optimization methods for linear ordering of automata
[Эвристические методы оптимизации для линейного упорядочивания автоматов]
Стремительное развитие общества связано с двумя ключевыми направлениями науки и технологий: методами работы с большими данными (Big Data) и искусственным интеллектом (Artificial Intelligence). Есть распространенное мнение, что до 80% процесса анализа данных — это время, потраченное на их подготовку. Одним из аспектов подготовки данных к анализу является структурирование и приведение в порядок наборов данных, так называемое data tidying. Отношения порядка встречаются повсеместно: мы встречаем их, когда рассматриваем числа, булевы алгебры, разбиения, мультимножества, графы, логические формулы и многие другие математические объекты. С одной стороны, отношения порядка используются для представления данных и знаний, с другой стороны, они служат важными инструментами для описания моделей и методов анализа данных, таких как деревья решений, случайные леса, пространства версий, правила ассоциации и т. д. Поскольку серьезным ограничением многих методов анализа шаблонов является вычислительная сложность, важно иметь эффективный алгоритм упорядочивания данных. В данной работе рассматриваются детерминированные автоматы без выходных сигналов и исследуется задача линейного упорядочения таких автоматов, заключающаяся в построении на множестве состояний автомата данного линейного порядка, который будет согласован с действием каждого входного сигнала автомата. Для решения этой задачи мы рассматриваем эвристические методы глобальной оптимизации: метод имитации отжига и алгоритм пчелиной колонии. Для обоих методов написана программная реализация и проведено тестирование на автоматах специального вида.
- Evsyutin O. O., Rossoshek S. K. Use of cellular automatons for problems solving of information transformation. Doklady TUSUR, 2010, vol. 21, iss. 1–1, pp. 173–174 (in Russian).
- Molchanov V. A., Farakhutdinov R. A. Linear ordering of automata. Matematika. Mekhanika [Mathematics. Mechanics], 2019, vol. 21, pp. 45–48 (in Russian).
- Binder K. Monte Carlo methods in statistical physics. Berlin, Springer, 1979. 376 p.
- Metropolis N., Rosenbluth A. W., Rosenbluth M. N., Teller A. H., Teller E. Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 1953, vol. 21, pp. 1087–1092. https://doi.org/10.1063/1.1699114
- Kirkpatrick S., Gelatt C. D. Jr., Vecchi M. P. Optimization by simulated annealing. Science, 1983, vol. 220, pp. 671–680.
- Savin A. N., Timofeeva N. E. The application of optimization algorithm using simulated annealing method for parallel computing systems. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2012, vol. 12, iss. 1, pp. 110–116 (in Russian). https://doi.org/10.18500/1816-9791-2012-12-1-110-116, EDN: OUPILL
- Doerr B., Rajabi A., Witt C. Simulated annealing is a polynomial-time approximation scheme for the minimum spanning tree problem. Algorithmica, 2024, vol. 86, pp. 64–89. https://doi.org/10.1007/s00453-023-01135-x
- Lopatin A. S. Simulated Annealing Method. Stokhasticheskaya Optimizatsiya v Informatike, 2005, vol. 1, pp. 133–149. (in Russian). EDN: KYIMEB
- Bogomolov A. M., Saliy V. N. Algebraicheskie osnovy teorii diskretnykh sistem [Algebraic foundations of the theory of discrete systems]. Moscow, Nauka, 1997. 368 p. (in Russian).
- Kats M. M. Criterion for linear ordering of a partial automaton. Izvestiya Vysshih Uchebnyh Zavedenij. Matematika, 1997, iss. 10, pp. 37–43 (in Russian). EDN: HQUVBJ
- Gabovich E. Ya. Fully ordered semigroups and their applications. Russian Mathematical Surveys, 1976, vol. 31, iss. 1, pp. 147–216. https://doi.org/10.1070/RM1976v031n01ABEH001447
- Kl´ıma O., Pol´ak L. On varieties of ordered automata. In: Martin-Vide C., Okhotin A., Shapira D. (eds.) Language and automata theory and applications. LATA 2019. Lecture notes in computer science, vol. 11417. Springer, Cham, 2019, pp. 108–120. https://doi.org/10.1007/978-3-030-13435-8_8
- Cotumaccio N., D’Agostino G., Policriti A., Prezza N. Co-lexicographically ordering automata and regular languages. Part I. Journal of the ACM, 2023, vol. 70, iss. 4, pp. 1–73. https://doi.org/10.1145/3607471
- Karaboga D. An idea based on honey bee swarm for numerical optimization. Technical Report, Erciyes University, 2005. Available at: https://abc.erciyes.edu.tr/pub/tr06_2005.pdf (accessed November 22, 2023).
- Pham D. T., Castellani M. The bees algorithm: Modelling foraging behaviour to solve continuous optimization problems. Proceedings of the Institution of Mechanical Engineers. Part C: Journal of Mechanical Engineering Science, 2009, vol. 223, iss. 12, pp. 2919–2938. https://doi.org/10.1243/09544062JMES1494
- Cuevas E., Sencion-Echauri F., Zaldivar D., Perez-Cisneros M. Multi-circle detection on images using Artificial Bee Colony (ABC) optimization. Soft Computing, 2012, vol. 16, iss. 2, pp. 281–296. https://doi.org/10.1007/s00500-011-0741-0
- Toktas A. Multi-objective design of multilayer microwave dielectric filters using artificial bee colony algorithm. In: Carbas S., Toktas A., Ustun D. (eds.) Nature-Inspired Metaheuristic Algorithms for Engineering Optimization Applications. Springer Tracts in Nature-Inspired Computing. Springer, Singapore, 2021, pp. 357–372. https://doi.org/10.1007/978-981-33-6773-9_16
- Aizenshtat A. Ya. The defining relations of the endomorphism semigroup of a finite linearly ordered set. Sibirskii Matematicheskii Zhurnal, 1962, vol. 3, iss. 2, pp. 161–169 (in Russian).
- 316 просмотров