# Evolutionary Approach to the Euclidean Steiner Tree Problem in n-Space
## 3 Results
### Results of the Basic Version of the Algorithm  
In this section, the results of the basic version of the proposed algorithm are presented; i.e., no method of preliminary sorting of points from set \(P\) is applied. During the population initialization, points from \(P\) are attached to the generated FST in a random order, the same for each run of the algorithm. The first set of problems consists of problems each containing 17 terminal points. This is due to the desire to compare the results obtained by the genetic algorithm with those achieved by [PERSON]'s algorithm, which uses a branch-and-bound approach to search for the optimal solution to the Steiner problem by examining all FSTs, eliminating the need to check some of them. The details of this approach are described in the paper [10]. The size of 17 is the maximum size for which solutions could be found for the 50 problems considered in an acceptable time. For this purpose, an implementation available on GitHub was used ([[https://github.com/[PERSON]/ESMT-Smith](https://github.com/[PERSON]/ESMT-Smith)]([https://github.com/[PERSON]/ESMT-Smith](https://github.com/[PERSON]/ESMT-Smith))). Table 1 presents the results obtained by the proposed genetic algorithm for 50 problems named 3d17-01 to 3d17-50. The table shows results for two crossover operators, single-point (1 point) and uniform (uniform). The respective columns show the minimum values of the sum of edge lengths in the best RMT obtained during 10 runs (min column). The worst values from 10 runs (max column) and the average values along with the standard deviation (mean (std) column) are also presented. The better result (compared to the alternative crossover operator) is highlighted in bold. \begin{table}
\begin{tabular}{l c c c c c c} \hline \hline
**Problem** & \multicolumn{3}{c}{**1 point**} & \multicolumn{3}{c}{**uniform**} \\ \hline  & **min** & **Mean (std)** & **max** & **min** & **Mean (std)** & **max** \\ \hline  
441 & 4.612 (0.096) & 4.777 & **4.373** & 4.578 (0.083) & 4.687 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Results of a basic version of genetic algorithm (initialization with random sorting) for 3d17 problems. The best result for a given problem is indicated in bold font. The results obtained suggest that the uniform crossover operator is better suited for this problem. The single-point operator found a better solution (min) in only 13 cases. The same applies to the worst solution found, which is also better for single-point crossover in 13 cases. The average results from ten runs are better in only five cases. However, these observations pertain to a relatively small problem size and will be verified in the case of more challenging problems. At this point, it is more interesting to compare the obtained results with those of [PERSON]'s algorithm, which is based on an exhaustive search. For this purpose, the results obtained by [PERSON]'s algorithm were compared with the best result for each problem achieved by the genetic algorithm with any crossover operator (the one that gave the better result for that problem). Figure 8 presents a histogram of the relative percentage error of the results obtained by the genetic algorithm compared to [PERSON]'s algorithm. The overwhelming majority of the \begin{table}
\begin{tabular}{l c c c c c c} \hline
**Problem** & \multicolumn{2}{c}{**1 point**} & \multicolumn{4}{c}{**uniform**} \\ \hline  & **min** & **Mean (std)** & **max** & **min** & **Mean (std)** & **max** \\ \hline  
*4.193 (0.035)** & **4.251** & **4.128** & 4.196 (0.050) & 4.270 \\ \hline \end{tabular}
\end{table} 
Table 1: _Cont._results have a percentage error less than 1%, with the worst not exceeding 2.5%. Therefore, it can be stated that the genetic algorithm indeed finds solutions close to the optimal one. Vectors describing the topologies found by both approaches, GA and [PERSON]'s algorithm, can also be compared. Figure 9 presents a histogram of the number of problems for which GA found topologies with the same value at a given number of positions.