Применение алгоритмов муравьиной колонии в решении задачи Штейнера
https://doi.org/10.17726/philIT.2015.9.1.4.8
Аннотация
Статья посвящена анализу известной и актуальной NP-полной задачи Штейнера, зачастую решаемой с применением муравьиных алгоритмов. Актуальность данной задачи связана с бурным ростом компьютерных сетей, а также возможностью применения в других областях науки и техники, таких как прокладка силовых кабелей, проектирование СБИС, задачи логистики. В статье формализуется математическое описание задачи Штейнера. Рассматривается возможность применения различных эвристических «природных» алгоритмов для решения данной задачи. Проводится аналогия между поведением муравьиной колонии и работой алгоритма для решения NP-полной задачи Штейнера. Выделяются и описываются характерные особенности различных вариантов муравьиного алгоритма, разработанные другими авторами, приводятся результаты исследования их эффективности и сравнения с классической реализацией. Затрагиваются особенности реализации каждого из рассмотренных алгоритмов, включая структуру и другие параметры графов, на которых проводилось каждое из исследований. В статье приводятся ссылки на основные наборы данных, предназначенные для тестирования алгоритмов. Делается вывод об эффективности каждой из реализаций и возможности их применения на различных графах с учетом изменяющейся обстановки и характеристик графа
Об авторах
П. Н. Полежаев
Оренбург, Россия
Россия
Россия
А. П. Миронов
Оренбург, Россия
Россия
Россия
Р. И. Поляк
Оренбург, Россия
Россия
Россия
Список литературы
1. Ying 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.913404
2. 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.
3. 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.
4. GeoSteiner. Software for Computing Steiner Trees [Electronic resource]. Access mode: http://www.diku.dk/hjemmesider/ansatte/martinz/geosteiner.
5. 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.
6. Koch T. Steinlib testdata library. Technical report, Konrad-Zuse-Zentrum für Informationstechnik Berlin. http://steinlib.zib.de/steinlib.php.
7. Кажаров А.А. Построение минимального дерева Штейнера на основе муравьиных алгоритмов // Труды молодежной конференции «Интеллектуальные системы-2009». М.: Физматлит, 2009.
8. 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.
9. Takahashi H., Matsuyama A. An approximate solution for the Steiner problem in graphs // Math. Japonica. 1980. № 24(6). P. 573-577.
10. OR-Library. Collection of test data sets for a variety of Operations Research (OR) problems. http://www.brunel.ac.uk/~mastjjb/jeb/info.html.
11. 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.
12. 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.
13. 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.
14. 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.
Рецензия
Для цитирования:
Полежаев П.Н., Миронов А.П., Поляк Р.И. Применение алгоритмов муравьиной колонии в решении задачи Штейнера. Философские проблемы информационных технологий и киберпространства. 2015;(1):96-105. https://doi.org/10.17726/philIT.2015.9.1.4.8
For citation:
Polezhaev P.N., Mironov A.P., Polyak R.I. APPLICATION OF ANT COLONY ALGORITHM FOR STEINER PROBLEM. Philosophical Problems of IT & Cyberspace (PhilIT&C). 2015;(1):96-105. (In Russ.) https://doi.org/10.17726/philIT.2015.9.1.4.8
Просмотров:
191
Послать статью по эл. почте 