Preview

Philosophical Problems of IT & Cyberspace (PhilIT&C)

Advanced search

APPLICATION OF ANT COLONY ALGORITHM FOR STEINER PROBLEM

https://doi.org/10.17726/philIT.2015.9.1.4.8

Abstract

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.

About the Authors

P. N. Polezhaev
Orenburg State University
Russian Federation


A. P. Mironov
Orenburg State University
Russian Federation


R. I. Polyak
Orenburg State University
Russian Federation


References

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.


Review

For citations:


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

Views: 194


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.


ISSN 2305-3763 (Online)