# Evolutionary Approach to the Euclidean Steiner Tree Problem in n-Space
## 1 Introduction
### Related Work  
The Steiner Minimal Tree problem has diverse applications in several technological and scientific domains. One of the primary applications of the Steiner Tree Problem is in network design, where it helps in minimizing the total length of networks, such as telecommunications and computer networks. This has practical implications for reducing costs and increasing the efficiency of network infrastructure. [2] provides a comprehensive overview of the SMT problem in various contexts, including network design. In the realm of electronics, the SMT Problem is crucial for optimizing the layout of circuits in VLSI (Very Large-Scale Integration) designs [3]. The objective is to minimize the total wire length, which is critical for enhancing the performance and reducing the power consumption. In biology, the SMT is used in phylogenetics to infer the shortest evolutionary tree. This application involves finding the most parsimonious tree connecting different species based on genetic markers [4]. Robotics applications can use Steiner trees for path planning, especially in the context of navigating complex environments where paths need to be as efficient as possible. A good overview of industrial applications of the Steiner problem is provided in [5]. The Steiner problem formulation also appears in other optimization problems that can be termed hybrid, such as the Steiner Traveling Salesman Problem in [6]. For the ESTP in two dimensions, an exact and efficient algorithm was proposed by [7]. The GeoSteiner program [8] is a successful implementation of this algorithm, which was based on the efficient enumeration of all topologies. However, the methods used in this two-dimensional approach cannot be directly translated to higher dimensions. In [9], a solution to the ESTP in \(\mathbb{R}^{d}\) for \(d\geq 3\) was proposed through the enumeration of all topologies, yet this approach is inefficient. One of the most important approaches to solving the ESTP accurately in \(\mathbb{R}^{d}\) is the branch and bound method presented by [PERSON] in [10]. However, the practical usefulness of this method largely depends on how well the lower bound can be estimated at the nodes of the search tree. Other studies have tried to introduce improvements to [PERSON]'s algorithm, for example, [11]. However, the results presented in this study were for problems with 18 terminal points and thus relatively small-scale problems. Another work proposing improvements to [PERSON]'s algorithm is [12]. In [13], the ESTP in \(\mathbb{R}^{d}\) was formulated as a convex mixed-integer nonlinear programming (MINLP), and results were presented for problems with 10 terminal points. A good overview of algorithms for finding exact solutions to the ESTP is provided in [1]. An excellent and up-to-date introduction to the issues related to the Euclidean Steiner problem and the challenges in higher-dimensional spaces is presented in [14]. Figure 4: Construction of full Steiner topologies (terminal points presented as gray and Steiner points as white circles). **Top**: a unique full Steiner topology for three terminals \(t_{1}-t_{3}\) with just one Steiner point \(s_{1}\). **Bottom**: three full Steiner topologies for four terminals \(t_{1}-t_{4}\). The new terminal \(t_{4}\) is attached through a new Steiner point \(s_{2}\), which is connected to edge 1 **(left)**, edge 2 **(middle)**, or edge 3 **(right)**. The Iterated Local Search algorithm was proposed in [15] as an example of a heuristic approach. The genetic algorithm has been applied to the ESTP in two-dimensional space, as demonstrated in [16; 17; 18; 19]. Other evolutionary algorithms, such as memetic algorithms, have also been developed for \(\mathbb{R}^{2}\)[20]. Another example is an application of particle swarm optimization algorithm to optimize the network connecting cities in China [21]. Additional heuristics, like Monte Carlo Tree Search, were also explored in [22].