# Evolutionary Approach to the Euclidean Steiner Tree Problem in n-Space
## 2 Proposed Algorithm
### Population Initialization  
In describing the data structure used for encoding the solution, the aspect of the order in which terminals are connected, i.e., their permutations, was omitted. It was assumed that this order is random, and the next terminal is connected with an equal probability by any existing edge. Let us call this the default initialization method. However, a brief analysis of the characteristic features of the problem allows for the development of better initialization methods. Below, we propose two such methods.  
Firstly, it is worth noting that in an optimal SMT solution, it is more likely that a given terminal will be connected to another terminal (directly or via a Steiner point) if it is closer rather than farther away, using Euclidean distance. From this observation, a simple heuristic can be proposed for generating complete topologies in the initial population of FSTs. This heuristic involves, for each subsequent terminal added to the FST under construction, first finding a certain number of its nearest neighbors among the terminals already included in the FST. From these nearest neighbors, one is randomly selected, and its edge is used to connect the new terminal. In this work, we test the number of nearest neighbors at 2, 3, 4, and 5.  
The second proposed heuristic for generating initial FSTs utilizes the first but aims to rectify its shortcomings. It addresses the issue that if the order of terminals is still random, then the nearest neighbors of a given terminal, searched only among other terminals already included in the FST under construction, may not be its nearest neighbors when searched across the entire set \(P\). Therefore, as a second heuristic, we propose pre-sorting all terminals in \(P\) according to the order of their selection during the execution of [PERSON]'s algorithm, which finds the minimum spanning tree for points in \(P\). This procedure starts from a random initial point. This ordering is further motivated by the fact that the minimum spanning tree is a solution to the problem of minimal connections in the absence of the possibility of using Steiner points.  
The results of numerical experiments presented later in the paper indicate that the application of an appropriate initialization procedure is of great significance.  
Figure 6: Scheme of the data structure used as a chromosome. For \(p\) points (terminals), we generally have \(p-2\) potential Steiner points, each of which can be connected to the topology being generated in a number of ways depending on its index. (**A**) The first Steiner point \(s_{1}\) uniquely connects the first three terminal points. (**B**) Each subsequent Steiner point, from index 2 to \(p-2\), can be added in an increasing number of ways equal to \(2(k-1)+1\), where \(k\) is the index of the Steiner point \(s_{k}\). (**C**) A sample chromosome for the problem with \(p=8\) terminal points. Thus, the number of potential Steiner points is \(p-2=6\). The first of these does not require encoding in the chromosome, so the chromosome length is 5. Each position in the chromosome displays a random value from the allowable range.