cyberspaceФилософские проблемы информационных технологий и киберпространстваPhilosophical Problems of IT & Cyberspace (PhilIT&C)2305-3763Пятигорский государственный университет10.17726/philIT.2015.9.1.4.8cyberspace-181Research ArticleПРИКЛАДНЫЕ АСПЕКТЫ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙПрименение алгоритмов муравьиной колонии в решении задачи ШтейнераAPPLICATION OF ANT COLONY ALGORITHM FOR STEINER PROBLEMПолежаевП. Н.PolezhaevP. N.newblackpit@mail.ruМироновА. П.MironovA. P.tupodok@gmail.comПолякР. И.PolyakR. I.esandman56@yandex.ruОренбург, РоссияРоссияOrenburg State UniversityRussian Federation2015080720210196105Copyright © Полежаев П.Н., Миронов А.П., Поляк Р.И., 20212021Полежаев П.Н., Миронов А.П., Поляк Р.И.Polezhaev P.N., Mironov A.P., Polyak R.I.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://cyberspace.pgu.ru/jour/article/view/181

Статья посвящена анализу известной и актуальной NP-полной задачи Штейнера, зачастую решаемой с применением муравьиных алгоритмов. Актуальность данной задачи связана с бурным ростом компьютерных сетей, а также возможностью применения в других областях науки и техники, таких как прокладка силовых кабелей, проектирование СБИС, задачи логистики. В статье формализуется математическое описание задачи Штейнера. Рассматривается возможность применения различных эвристических «природных» алгоритмов для решения данной задачи. Проводится аналогия между поведением муравьиной колонии и работой алгоритма для решения NP-полной задачи Штейнера. Выделяются и описываются характерные особенности различных вариантов муравьиного алгоритма, разработанные другими авторами, приводятся результаты исследования их эффективности и сравнения с классической реализацией. Затрагиваются особенности реализации каждого из рассмотренных алгоритмов, включая структуру и другие параметры графов, на которых проводилось каждое из исследований. В статье приводятся ссылки на основные наборы данных, предназначенные для тестирования алгоритмов. Делается вывод об эффективности каждой из реализаций и возможности их применения на различных графах с учетом изменяющейся обстановки и характеристик графа

This article is devoted to the analysis of the well-known and relevant NP-complete Steiner problem, often solved by using ant algorithms. The relevance of this problem is related to the rapid growth of computer networks and the possibility of application in other fields of science and technology, such as the laying of power cables, VLSI design, logistics problems. Paper formalizes mathematical description of the Steiner problem. It considers the possibility of using different heuristics such as “natural” algorithms for solving this problem. In addition, it draws an analogy between the behavior of an ant colony and the work of the algorithm for solving NP-complete Steiner problem. Different variants of ant algorithms developed by other authors, the results of their effectiveness estimation and comparison with the classical implementation are described. Paper notes the implementation features of each considered algorithms, including their graph structure and its parameters. In addition, we provide links to major data sets for testing algorithms and conclude about the effectiveness of each algorithm implementations and their applicability to different graphs, including their dynamic changing.

задача Штейнераалгоритм муравьиной колонииэвристический алгоритмNP-полная задачаSteiner tree problemAnt colony optimizationNP-completeheuristic algorithmReferencesYing Wang, Jianying Xie. Ant colony optimization for multicast routing // Circuits and Systems, 2000. IEEE APCCAS 2000. The 2000 IEEE AsiaPacific Conference. DOI: 10.1109/APCCAS.2000.913404Ying Wang, Jianying Xie. Ant colony optimization for multicast routing // Circuits and Systems, 2000. IEEE APCCAS 2000. The 2000 IEEE AsiaPacific Conference. DOI: 10.1109/APCCAS.2000.913404Li Y. QoS Multicast Routing Algorithm Based on Crowding Ant Colony Algorithm. // Journal of Computers, North America. 2013. № 8. DOI: 10.4304/jcp.8.10.2711-2718.Li Y. QoS Multicast Routing Algorithm Based on Crowding Ant Colony Algorithm. // Journal of Computers, North America. 2013. № 8. DOI: 10.4304/jcp.8.10.2711-2718.Yu Hu, Tong Jing, Xianlong Hong, Zhe Feng, Xiaodong Hu, Guiyang Yan. An efficient rectilinear Steiner minimum tree algorithm based on ant colony optimization. // Communications, Circuits and Systems, 2004. ICCCAS 2004. 2004 International Conference. 2004. DOI: 10.1109/IC- CCAS.2004.1346406.Yu Hu, Tong Jing, Xianlong Hong, Zhe Feng, Xiaodong Hu, Guiyang Yan. An efficient rectilinear Steiner minimum tree algorithm based on ant colony optimization. // Communications, Circuits and Systems, 2004. ICCCAS 2004. 2004 International Conference. 2004. DOI: 10.1109/IC- CCAS.2004.1346406.GeoSteiner. Software for Computing Steiner Trees [Electronic resource]. Access mode: http://www.diku.dk/hjemmesider/ansatte/martinz/geosteiner.GeoSteiner. Software for Computing Steiner Trees [Electronic resource]. Access mode: http://www.diku.dk/hjemmesider/ansatte/martinz/geosteiner.Rabanal P., Rodríguez I., Rubio F. Studying the application of ant colony optimization and river formation dynamics to the Steiner tree problem // Evolutionary Intelligence. 2011. № 4(1). DOI: 10.1007/s12065-011- 0049-0.Rabanal P., Rodríguez I., Rubio F. Studying the application of ant colony optimization and river formation dynamics to the Steiner tree problem // Evolutionary Intelligence. 2011. № 4(1). DOI: 10.1007/s12065-011- 0049-0.Koch T. Steinlib testdata library. Technical report, Konrad-Zuse-Zentrum für Informationstechnik Berlin. http://steinlib.zib.de/steinlib.php.Koch T. Steinlib testdata library. Technical report, Konrad-Zuse-Zentrum für Informationstechnik Berlin. http://steinlib.zib.de/steinlib.php.Кажаров А.А. Построение минимального дерева Штейнера на основе муравьиных алгоритмов // Труды молодежной конференции «Интеллектуальные системы-2009». М.: Физматлит, 2009.Кажаров А.А. Построение минимального дерева Штейнера на основе муравьиных алгоритмов // Труды молодежной конференции «Интеллектуальные системы-2009». М.: Физматлит, 2009.Luyet L., Varone S., Zufferey N. An Ant Algorithm for the Steiner Tree Problem in Graphs // Applications of Evolutionary Computing. Springer Berlin Heidelberg. 2007. DOI: 10.1007/978-3-540-71805-5_5.Luyet L., Varone S., Zufferey N. An Ant Algorithm for the Steiner Tree Problem in Graphs // Applications of Evolutionary Computing. Springer Berlin Heidelberg. 2007. DOI: 10.1007/978-3-540-71805-5_5.Takahashi H., Matsuyama A. An approximate solution for the Steiner problem in graphs // Math. Japonica. 1980. № 24(6). P. 573-577.Takahashi H., Matsuyama A. An approximate solution for the Steiner problem in graphs // Math. Japonica. 1980. № 24(6). P. 573-577.OR-Library. Collection of test data sets for a variety of Operations Research (OR) problems. http://www.brunel.ac.uk/~mastjjb/jeb/info.html.OR-Library. Collection of test data sets for a variety of Operations Research (OR) problems. http://www.brunel.ac.uk/~mastjjb/jeb/info.html.Prossegger M., Bouchachia A. Ant colony optimization for Steiner tree problems. // In Proceedings of the 5th international conference on Soft computing as transdisciplinary science and technology (CSTST ‘08). ACM. New York, 2008. P. 331-336. DOI: 10.1145/1456223.1456292.Prossegger M., Bouchachia A. Ant colony optimization for Steiner tree problems. // In Proceedings of the 5th international conference on Soft computing as transdisciplinary science and technology (CSTST ‘08). ACM. New York, 2008. P. 331-336. DOI: 10.1145/1456223.1456292.Shen C.-C., Li K., Jaikaeo C., Sridhara V. Ant-based distributed constrained Steiner tree algorithm for jointly conserving energy and bounding delay in ad hoc multicast routing. // ACM Transactions on Autonomous and Adaptive Systems. 2008. Vol. 3. Issue 1. Article № 3. DOI: 10.1145/1342171.1342174.Shen C.-C., Li K., Jaikaeo C., Sridhara V. Ant-based distributed constrained Steiner tree algorithm for jointly conserving energy and bounding delay in ad hoc multicast routing. // ACM Transactions on Autonomous and Adaptive Systems. 2008. Vol. 3. Issue 1. Article № 3. DOI: 10.1145/1342171.1342174.Hua Wang, Zhao Shi, Jun Ma, Gang Wang. The Tree-Based Ant Colony Algorithm for Multi-Constraints Multicast Routing // Advanced Communication Technology, The 9th International Conference on. 2007. Vol. 3. P. 1544-1547. DOI: 10.1109/ICACT.2007.358661.Hua Wang, Zhao Shi, Jun Ma, Gang Wang. The Tree-Based Ant Colony Algorithm for Multi-Constraints Multicast Routing // Advanced Communication Technology, The 9th International Conference on. 2007. Vol. 3. P. 1544-1547. DOI: 10.1109/ICACT.2007.358661.Patel M.K., Kabat M.R., Tripathy C.R. A hybrid ACO/PSO based algorithm for QoS multicast routing problem // Ain Shams Engineering Journal. 2014. Vol. 5. Issue 1. P. 113-120. DOI: 10.1016/j.asej.2013.07.005.Patel M.K., Kabat M.R., Tripathy C.R. A hybrid ACO/PSO based algorithm for QoS multicast routing problem // Ain Shams Engineering Journal. 2014. Vol. 5. Issue 1. P. 113-120. DOI: 10.1016/j.asej.2013.07.005.

The authors declare that there are no conflicts of interest present.