Evolutionary Approach to the Euclidean Steiner Tree Problem in n-Space
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 verti...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-01-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/15/3/1413 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850199275658543104 |
|---|---|
| author | Michał Bereta |
| author_facet | Michał Bereta |
| author_sort | Michał Bereta |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-c289862f34ea4324a5ef57e7a63ea3f3 |
| institution | OA Journals |
| issn | 2076-3417 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj-art-c289862f34ea4324a5ef57e7a63ea3f32025-08-20T02:12:40ZengMDPI AGApplied Sciences2076-34172025-01-01153141310.3390/app15031413Evolutionary Approach to the Euclidean Steiner Tree Problem in n-SpaceMichał Bereta0Department of Computer Science, Cracow University of Technology, 31-155 Kraków, PolandThis 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.https://www.mdpi.com/2076-3417/15/3/1413Euclidean Steiner problemevolutionary optimizationgenetic algorithmheuristics |
| spellingShingle | Michał Bereta Evolutionary Approach to the Euclidean Steiner Tree Problem in n-Space Applied Sciences Euclidean Steiner problem evolutionary optimization genetic algorithm heuristics |
| title | Evolutionary Approach to the Euclidean Steiner Tree Problem in n-Space |
| title_full | Evolutionary Approach to the Euclidean Steiner Tree Problem in n-Space |
| title_fullStr | Evolutionary Approach to the Euclidean Steiner Tree Problem in n-Space |
| title_full_unstemmed | Evolutionary Approach to the Euclidean Steiner Tree Problem in n-Space |
| title_short | Evolutionary Approach to the Euclidean Steiner Tree Problem in n-Space |
| title_sort | evolutionary approach to the euclidean steiner tree problem in n space |
| topic | Euclidean Steiner problem evolutionary optimization genetic algorithm heuristics |
| url | https://www.mdpi.com/2076-3417/15/3/1413 |
| work_keys_str_mv | AT michałbereta evolutionaryapproachtotheeuclideansteinertreeprobleminnspace |