Evolutionary Approach to the Euclidean Steiner Tree Problem in n-Space
Source abstract
Abstract
This article presents the application of a genetic algorithm for solving the Euclidean Steiner problem in spaces of dimensionality greater than 2. The Euclidean Steiner problem involves finding the minimum spanning network that connects a given set of vertices, including the additional Steiner vertices, in a multi-dimensional space. The focus of this research is to compare several different settings of the method, including the crossover operators and sorting of the input data. The paper points out that significant improvement in results can be achieved through proper initialization of the initial population, which depends on the appropriate sorting of vertices. Two approaches were proposed, one based on the nearest neighbor method, and the other on the construction of a minimum spanning tree.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: VLSI and FPGA Design Techniques
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Computer Science, Cracow University of Technology, 31-155 Kraków, Poland
References (28)
Show source-provided references
1. An overview of exact algorithms for the Euclidean Steiner tree problem in n-space10.1111/itor.12207 ↗
2. Hwang, F.K., Richards, D.S., and Winter, P. (1992). The Steiner Tree Problem, Annals of Discrete Mathematics 53, Elsevier.
3. Kahng, A.B., and Robins, G. (1994). On Optimal Interconnections for VLSI, Springer Science & Business Media.10.1007/978-1-4757-2363-2 ↗
4. Phylogenetic analysis. Models and estimation procedures10.1111/j.1469-1809.1967.tb00024.x ↗
5. Cheng, X.Z., and Du, D.Z. (2002). Steiner Trees in Industry, Springer. Combinatorial Optimization.10.1007/978-1-4613-0255-1 ↗
6. The Steiner Traveling Salesman Problem and its extensions10.1016/j.ejor.2019.04.047 ↗
7. On the problem of Steiner10.4153/CMB-1961-016-2 ↗
8. Du, D.Z., Smith, J., and Rubinstein, J. (2000). Exact Algorithms for Plane Steiner Tree Problems: A Computational Study. Advances in Steiner Trees, Springer.10.1007/978-1-4757-3171-2 ↗
9. Steiner Minimal Trees10.1137/0116001 ↗
10. How to find Steiner Minimal Trees in euclideand-space10.1007/BF01758756 ↗
11. An improved algorithm for computing Steiner Minimal Trees in Euclidean d-space10.1016/j.disopt.2007.08.006 ↗
12. Fonseca, R., Brazil, M., Winter, P., and Zachariasen, M. (2014, January 4–5). Faster exact algorithms for computing Steiner trees in higher dimensional Euclidean spaces. Proceedings of the Workshop of the 11th Dimacs Implementation Challenge, Providence, RI, USA.
13. A specialized branch-and-bound algorithm for the Euclidean Steiner tree problem in n-space10.1007/s10589-016-9835-z ↗
14. Insight into the computation of Steiner Minimal Trees in Euclidean space of general dimension10.1016/j.dam.2019.03.015 ↗
15. Iterated Local Search algorithms for the Euclidean Steiner tree problem in n dimensions
16. Jones, J., and Harris, F.C.J. (1996, January 19–21). A Genetic Algorithm for the Steiner Minimal Tree Problem. Proceedings of the ISCA’s International Conference on Intelligent Systems, Reno, NV, USA.
17. Genetic Algorithm Approaches to Solve Various Steiner Tree Problems10.1007/978-1-4613-0255-1_2 ↗
18. Barreiros, J. (2003, January 11). A Hierarchic Genetic Algorithm for Computing (near) Optimal Euclidean Steiner Trees. Proceedings of the GECCO 2003: Proceedings of the Bird of a Feather Workshops, Genetic and Evolutionary Computation Conference, Chigaco, IL, USA.
19. A Genetic Algorithm for Solving the Euclidean Non-Uniform Steiner Tree Problem
20. Baldwin effect and Lamarckian evolution in a memetic algorithm for Euclidean Steiner Tree Problem10.1007/s12293-018-0256-7 ↗
21. Cao, S., Chen, J., and Gou, J. (2024, January 6–8). Binary Particle Swarm Optimization Algorithm for Euclidean Steiner Tree. Proceedings of the 2024 4th International Conference on Computer Science and Blockchain (CCSB), Shenzhen, China.10.1109/CCSB63463.2024.10735644 ↗
22. Monte Carlo Tree Search Algorithm for the Euclidean Steiner Tree Problem
23. Julstrom, B.A. (2002, January 12–17). A scalable genetic algorithm for the rectilinear Steiner problem. Proceedings of the 2002 Congress on Evolutionary Computation. CEC’02 (Cat. No.02TH8600), Honolulu, HI, USA.
24. Deb, K. (2004). Combining a Memetic Algorithm with Integer Programming to Solve the Prize-Collecting Steiner Tree Problem. Genetic and Evolutionary Computation—GECCO 2004, Springer.
25. A new heuristic for the Euclidean Steiner Tree Problem in Rn10.1007/s11750-022-00642-4 ↗
26. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms10.1016/j.swevo.2011.02.002 ↗
27. KEEL: A software tool to assess evolutionary algorithms for data mining problems
28. KEEL data-mining software tool: Data set repository, integration of algorithms and experimental analysis framework