Baldwin effect and Lamarckian evolution in a memetic algorithm for Euclidean Steiner tree problem

Exact and heuristic algorithms exist for solving ESTP. Examples of exact algorithms for ESTP are the algorithms of Melzak [2, 3], Trietsch and Hwang [4] or the well known Smith algorithm [5]. Smith also suggested a generalization of his algorithm to higher dimensions. There is still a need for new heuristics. Exact algorithms for ESTP are computationally demanding, which limits their use for bigger problems, i.e., for problems with a bigger number of terminals. Although a huge breakthrough has been made in the field [1], heuristic algorithms have also been proposed to solve ESTP.

A wide class of heuristic algorithms, which can also be applied to ESTP, are evolutionary algorithms. The general approach is to maintain a population of potential solutions, which are gradually improved by promoting more promising ones and applying differentiation operators to them (such as crossover or mutation) to create a new generation of potentially better solutions. Depending on the problem to be solved, the solutions are encoded using a proper data structure.

Several evolutionary approaches have already been proposed to address various types of Steiner problem, not only on Euclidean plane. Genetic algorithms (GA) have been the most popular among them; example approaches are [6, 7]. There were also some other approaches such as particle swarm optimization, ant colony optimization, an artificial immune algorithm or more recently physarum optimization [8, 9]. However, to the best of Author’s knowledge, this work is the first attempt to analyze the importance of the Baldwin effect and Lamarckian evolution in an evolutionary algorithm applied to ESTP. From all of the cited works, the most similar approach was presented in [7]. The algorithm for relocating Steiner points proposed in [7] is somehow akin to the correction procedure proposed in this work. However, the whole new design of the evolutionary algorithm with improvement procedure proposed here and the main goal of testing the Baldwin effect and Lamarckian evolution make this study unique.

There are several design decisions when an evolutionary algorithm is to be applied to the given problem. Two problems are particularly important in this work. The first one is that in some problems it is hard to generate even a feasible solution. Usually, an evolutionary algorithm starts with a population of randomly generated individuals. In case they are not feasible solutions, an additional repair procedure can be applied. It is possible in some problems to calculate the fitness function for such infeasible solutions in the hope that after several generations of evolutionary algorithm they will become not only feasible but also optimal. The second problem is that evolutionary algorithms are known to be good at estimating the promising areas in the search space relatively fast. However, the fine-tuning process of these solutions may take a long time. In the case of ESTP, when applying an evolutionary algorithm to solve it, both of the aforementioned problems are present and seem to be crucial. It is a straightforward procedure to generate a set of random points and encode it as an individual in an evolutionary algorithm. However, the probability that these points satisfy the conditions necessary to be a proper solution for the ESTP is slight.

In general, even if the solutions in the evolutionary algorithm are feasible, an additional procedure can be applied to each individual from the population to increase the convergence speed. This procedure can be in the form of a greedy optimization heuristic (local search procedure), and its introduction into the evolutionary framework brings the idea of a memetic algorithm (MA) and more general, memetic computation.

MAs [10] originate from pairing evolutionary framework and a set of local improvement procedures, often called local search, lifetime learning or individual learning. Local improvement method, considered on its own, often represents a greedy optimization which is usually not sufficient to find satisfactory solutions on its own. More generally, memes are essential units of knowledge about the problem being solved. When incorporated into the evolutionary algorithm they can speed up its convergence especially in the case of complex optimization problems.

The successful application of the concept of combining evolutionary search with memes representing problem specific knowledge brought enormous research in the area known as memetic computing. That led to algorithmic constructs far beyond the idea of simple improvement step as a part of the evolutionary algorithm. According to [10] current research in the field of memetic computing can be categorized into simple hybrids (with a MA as a representative), adaptive hybrids and a memetic automaton. Another, generational description of MA has been presented in [11]. The first generation of memetic computing include algorithms resulting from the mere pairing of global search algorithm (potentially evolutionary) with local search. MAs from the second and third generations include algorithms based on pairing global search with several local optimizers. The models become more and more complicated, and the ideas used to build new memetic computing paradigms include passing to offspring the choice of local optimizer (second generation) or self-organization and coevolution (third generation).

A detailed description of all the problems concerning the design of an algorithm based on memetic computation ideas is far beyond the scope of this introduction. Memetic computation is strongly connected with the problem being solved. The results depend primarily on the strategic choices concerning the level of hybridization (such as preprocessing schemes, solution representation, problem specific search operators), population diversity management, frequency and intensity of refinement and modes of inheritance (Baldwin effect and Lamarckian learning). In the case of adaptive memetic computation, the number of factors is even bigger.

Several works describe successful applications of MA to different hard optimization problems concerned with path planning or graph structures optimizations. Examples are path planning for mobile robots with bacterial MA [12], traveling car renter problem [13] or vertex coloring problem [14]. Other combinatorial optimization problems, such as job-shop scheduling problem [15] or knapsack problem [16], have also been successfully approached by MA. These examples show a great potential of memetic computing when dealing with hard optimization problems similar to ESTP.

In the case of the MA with a local search procedure, there are several approaches to how the corrected solutions should be used. One approach is to use the fitness function of the corrected solution to evaluate the original solution. However, the original solution is not replaced by the corrected one. This approach is described as Baldwin effect in the evolutionary process [17]. On the other hand, the corrected solution can replace the original one in the population. This approach constitutes what is called a Lamarckian evolution [17]. Both methods have their advantages but are also potentially problematic, and it is hard to assess which one is better for a given problem. For example, Lamarckian evolution can limit the population diversity very quickly, which is not desired in general. An intermediate approach is possible, in which only some percentage of the corrected solutions is accepted as the replacement of the original solutions. This method opens up many possibilities to fine tune the evolutionary algorithm.

Both, Baldwin effect and Lamarckian evolution, have been used in memetic computations. Lamarckian learning [18, 19] has been reported as a better approach to unimodal optimization problems and in problems in which the environment is static. On the other hand, Baldwin effect has been reported as the preferred method for problems in dynamic environments [20, 21]. There have also been some studies suggesting that a mixed Lamarckian–Baldwinian approach could be beneficial [22]. Thus, it is not possible to assess which approach is universally better, and the comparison between the Baldwin effect and Lamarckian evolution has to be performed in the context of the given problem. One of the goals of this paper is to study the usefulness of Baldwin effect and Lamarckian evolution in the context of the ESTP.

The algorithm proposed in this work can be classified as a simple hybrid type of MA. It is based on a GA framework with crossover operator and three mutation operators. It is observed that the GA on its own is not efficient in providing not only optimal but even feasible solutions of ESTP. For that reason, ESTP specific knowledge is introduced. The memes are represented as two local search procedures specifically designed for the ESTP. The main contribution of this study is to verify the usefulness of the proposed memes to improve the performance of the GA. The second contribution is the comparison of a spectrum of different modes of inheritance ranging from Baldwin effect to Lamarckian learning for the ESTP. As stated in the previous section, such comparisons strongly depend on the problem being solved. It is expected that the results presented in this study will be helpful in designing MA for ESTP especially concerning the choice between Baldwin effect and Lamarckian evolution. The straightforward application of the greedy heuristic is also included in the comparison.

The paper is organized as follows. In Sect. 2, the most important facts about ESTP are provided, which allow defining a correction procedure and a simple greedy heuristic to improve an existing candidate solution to ESTP. In Sect. 3, a MA for 2D ESTP including the repair and local search procedures is derived. In Sect. 4, the results of empirical studies on 2D ESTP problems of various sizes are presented together with a proper statistical analysis. Conclusions are drawn in Sect. 5.

The Fermat point of the triangle on the Euclidean plane is a point minimizing the total sum of distances of triangle vertices to that point. Thus, for any other point F’ on the plane, the condition (1) is satisfied.where F is a Fermat point, and A, B, and C are triangle’s vertices.

For a simple case of three points on the Euclidean plane, the SMT can be found easily with the help of the Fermat point. Two situations are possible. If the three points form a triangle in which all angles have less than \(120^{\circ }\), then the only Steiner point is located at the Fermat point of the triangle. The SMT is equivalent to the minimum spanning tree (MST) including three triangle points and the Fermat point. In the second case, if there is an angle equal to or greater than \(120^{\circ }\), the Steiner point is incident with the triangle vertex in which the two sides of the triangle meet at 120 or more degrees. The SMT is the MST spanned on the three triangle points.

The procedure to find Fermat point for three points is given as follows (Fig. 2).

Output: Fermat pointEnd of Procedure 1

In the subsequent part of this work only Fermat points which are not incident with the triangle point are useful in the proposed heuristic. For that reason, for the purpose of this work, such not useful Fermat points will be called not valid Fermat points.

A standard measure to compare solutions for ESTP is called Steiner ratio. It is given by (2):where L(.) is the total length of the edges of a given tree, MST is the minimum spanning tree for the terminals and ST is the Steiner tree calculated as the minimum spanning tree for the set of points consisting of the union of the terminals and a given set of Steiner points. It is worth to mention that although Steiner points have to satisfy the degree and angle conditions mentioned earlier in this section, the Steiner ratio measure can be used to compare solutions obtained for any given set of points used as Steiner points. This interpretation allows using the Steiner ratio as a fitness function in the proposed evolutionary algorithm.

Finding the Fermat point for a set of three terminals is a straightforward way to find an SMT for these three points. For a bigger number of terminals, the situation is not as simple. However, based on the simple procedure of finding the Fermat point, a simple heuristic can be formulated which iteratively generates candidate Steiner points as Fermat points for groups of selected three points from a given problem. If the addition of such candidate point improves the Steiner ratio, the Fermat point is accepted as a new Steiner point. This step can be repeated until a stopping criterion is satisfied. Procedures 2 and 3 describe the idea more in detail.

Input: \(Z=T\cup S\)—set of points (T—terminals; S - already added Steiner points), \({MST}_{Z}\) –minimum spanning tree for Z, nn—number of nearest neighbors to look for.

Output: true if a new Steiner point f has been found and S was modified, false otherwise.End of Procedure 2

The meaning of step 6 in Procedure 2 will be explained in the later part of this section.

Input: T—set of terminals, S—set of Steiner points, max_iters – maximum number of iterations, max_tries – maximum number of iterations without improvement, nn—the number of nearest neighbors to look for in procedure FindSteinerPoint.

Output: S—set of Steiner points.End of Procedure 3

In the second (or any further) iteration of procedure ImproveSolution, it is possible that after the addition of point f and calculating the new minimum spanning tree \({MST}_{Z^{\prime }}\) in step 5 of FindSteinerPoint, some of the other Steiner points may no longer satisfy the angle and/or degree condition. This is especially possible when f is connected with already existing Steiner points in \({MST}_{Z^{\prime }}\). In such cases, a correction procedure CorrectSolution can be applied.

Input: T—set of terminals, S—set of Steiner points (some of them potentially invalid), \(\upvarepsilon \)—maximum allowed violation of angle condition for Steiner points.

Output: S—set of valid Steiner pointsEnd of procedure correctsolution

As an example, in Fig. 3 two steps of the improvement procedure are presented. The first Steiner point has been added in (b) to the set of terminals from (a). This Steiner point satisfies the degree and angle conditions and the correction procedure introduces no changes. After adding the second Steiner point and recalculating the MST, the first one no longer satisfies the angle condition, but it is still a point of 3 degrees (c). In (d) the situation after the correction procedure is shown, where both Steiner points have been shifted into the correct locations and satisfy the degree and angle conditions.

It should be stressed out that procedure FindSteinerPoint can modify the set S by adding a new Steiner point but also by removing some of the already existing ones using the correction procedure. However, it is done only if it is beneficial, i.e., the overall Steiner ratio decreases, which means that a better solution is found.

The main purpose of introducing these simple heuristics for correcting and improving ESTP solutions is to use them as local search procedures in the MA described in Sect. 3. The proposed algorithm will be tested on the effects of the usage of these correction and improvement heuristics.

For a given set T of p terminals, the solution to ESTP is a set of Steiner points. Not only location of these points is not known but also the number of them. As described in Sect. 2, for ESTP with p points, at most p-2 Steiner points can exist in the optimal solution. For that reason, the data structure used to encode a single solution (Fig. 4) allows encoding a maximum number of \(p{-}2\) 2D points, however additional bits are used to indicate which “genes” are active. That allows modeling the problems in which the solution consists of a number of Steiner points smaller than \(p{-}2\). Still, the length of the chromosome is constant. However, the only candidate Steiner points that are used to calculate MST are the points with the activation bits set to true. The coordinates of the points are encoded as real values. The ith chromosome in the population can be described aswhere \(\left( {x_{ij},y_{ij} } \right) \in {\mathbb {R}}^{2}\) are the coordinates of j-th candidate Steiner point, \(b_{ij} \) is the corresponding activation bit and \(j=1,\ldots ,p-2\).

The main loop of the proposed algorithm is summarized in Fig. 5. Apart from the proposed MA, the GA is also presented. It is given to alleviate the understanding of the role of the local search in the proposed MA, which is designed on the basis of the GA from Fig. 5. In fact, the GA is also used in the numerical tests described in Sect. 4 (denoted as enorm).

The main difference between the GA and the MA is the evaluation step. In the case of the GA, the candidate Steiner points encoded by the active genes in the chromosome are combined with the terminal points of the ESTP being solved, and the Steiner ratio of this solution is calculated and used as the evaluation of the chromosome. In the case of the MA, after extracting of candidate Steiner points from active genes, there is an approach to correct/improve this set of candidate points using the local search procedure. The local search algorithm can be either the correction procedure (Procedure 4) or the improvement procedure (Procedure 3). Which one of them is used, is a parameter of the algorithm and it is set before the start of the algorithm. It does not change during the execution of the given run. The Steiner ratio of the corrected/improved solution is used as the evaluation of the original chromosome. Additionally, to compare the usefulness of the Baldwin effect and Lamarckian evolution, the corrected/improved genes can be accepted into the initial chromosome with a probability of prob_change, which is a parameter of the algorithm. By setting prob_change to 0, we only consider the Baldwin effect, while setting it to 1, the evolution is of Lamarckian type. However, intermediate values can also be considered. The results of the numerical experiments presented in Sect. 4 show the importance of the proper setting of prob_change.

The next section gives a detailed description of all of the steps of the proposed MA.

In what follows a detailed description of all the steps of the MA (Fig. 5) is provided. Most of the steps are the same for the GA, and the only difference is during the evaluation step.

First, during the initialization, the population of random solutions (chromosomes) is generated. For ith chromosome the coordinates of the candidate jth Steiner point are generated according to (4) and (5):where T is a set of terminals, and urand is a random value generated from a uniform distribution. The activation bits are set to true with probability abits_init_prob.

Then, until the termination condition is satisfied, the following steps are repeated.The crossover operator is a simple one-point crossover. First, a cutting point is generated, and the offspring is produced by interchanging the two resulting parts. The idea is presented in Fig. 6.

There are three mutation operators. This may seem to be too complicated, however, after some consideration each of these operators is justifiable. Switching the activation bits is crucial for the algorithm to adapt to the problems in which a different number of Steiner points are optimal. Mutating the positions of the candidate Steiner points is the most expected mutation type and does not seem to require additional justification. The last mutation operator, resetting the coordinates to the random ones, may help to escape the algorithm from local minima. However, it should be used with a small probability as it is much damaging to the chromosome. It should be noted that the second and third mutation operator is executed not depending on the value of the activation bits, i.e., the given gene in the chromosome may be inactive and still mutated by changing the coordinates or resetting them.

Let us now assume that during the local search step the improvement procedure removed one candidate point, corrected the coordinates of three and added two new Steiner points. The problem is now how to include the new Steiner points into the chromosome data structure. There are several options. After some preliminary numerical experiments, the approach used in this work is as follows. First, the improved Steiner points are put randomly at the positions of active genes in the chromosome. Then, in case there are still Steiner points to be placed into the data structure, inactive positions are selected randomly, set to these remaining Steiner points and their activation bits are set to true.

For the purpose of this study, three sets of random problems were generated on \([0,1]^{2}\). There are three groups of 20 problems, with 10, 20 and 50 terminals, respectively. Example problem with 50 terminals is presented in Fig. 7. All the problems and solutions are available upon request from Author.

Several versions of the algorithm have been tested. First, the local search method is selected, then the probability of acceptance of the modified solution. For the correction procedure chosen as the local method, there are algorithms abbreviated as cp0.0, cp0.2, cp0.4, cp0.6, cp0.8 and cp1.0, where the values after the letters “cp” indicate the values of prob_change. For example, cp0.8 means that a correction procedure is used as the local search method and the modified chromosome is accepted with the probability 0.8. For the improvement procedure selected as the local search method, there are algorithms abbreviated as ip0.0, ip0.2, ip0.4, ip0.6, ip0.8 and ip1.0, where the values after the letter “ip” indicate the values of prob_change. Note that in all cases the Steiner ratio of the corrected/improved chromosome is used as the fitness function even in the cases when the original chromosome is not replaced.

Additionally, the GA with no local search method is tested for comparison. It means that the steps 1b, 1c, and 1d from the description of the algorithm in Sect. 3 are replaced by simply calculating the Steiner ratio for the points with activation bits set to true, even though they may not satisfy the degree and angle conditions. This allows testing the importance of any of the local search methods. The algorithm is abbreviated as enorm.

The improvement procedure (Procedure 3) is also included in the comparison. It allows testing the capability of this heuristic when used outside the evolutionary framework. In this case, the improvement procedure starts with an empty set of Steiner points and adds new candidate Steiner points one by one in a greedy way. Due to the usage of the correction procedure as a part of this improvement procedure, some of the already existing Steiner points can be removed, and the resulting dynamics can be treated as an interesting greedy optimization approach to ESTP. Three versions of the improvement procedure are tested, with the parameter nn (the number of the nearest neighbors in Procedure 3) equal 3, 5 and -1, where \(nn=-1\) means that the three points used to calculate the Fermat point are randomly selected from among all available points.

Table 1 summarizes the algorithms tested together with the values of the parameters used. It should be observed that the improvement procedure is employed in the MA with \({max\_iters}=1\), which means that there is an attempt to insert only one new candidate Steiner point. Thus, the usage of this local search method is limited to prevent the premature convergence and preserve the population diversity. Still, the parameter \({max\_tries}=100\), which means that the improvement procedure actively searches for the new candidate Steiner point and stops only if it is not possible to generate new satisfying Fermat point (Procedure 2) for 100 attempts. On the other hand, algorithms nn3, nn5 and nn-1 look for multiple candidate Steiner points (parameter \({max\_iters}=3^*{\vert }T{\vert }-2\), where T is the set of terminals in a given ESTP). Although it is known that the maximum number of Steiner points can be at most \({\vert }T{\vert }-2\) in the optimal solution, it should be remembered that the correction procedure (used by the improvement procedure) may remove some of the Steiner points after introducing a new one. Due to this dynamic character of the improvement procedure when \({max\_iters}>1\), setting \({max\_iters}>{\vert }T{\vert }-2\) may be beneficial.

The parameters for the evolutionary part of the MA have been set after several trial runs and have been observed to work satisfactorily. They may not be optimal. However, the important thing here is that they are common to all versions of the MA and the main aim of this study is to measure the differences resulting from different local search procedures and varying levels of the probability of acceptance of the corrected/improved solution. The final best solution from each run of the MA is finally corrected with \(\upvarepsilon =1e{-}8\), although \(\upvarepsilon =1e{-}5\) was used during the evolution to speed up the computations. This is done for a fair comparison with the results of nn3, nn5, and nn-1 algorithms, in which \(\upvarepsilon =1e{-}8\) has been used.

In case of the evolutionary framework the following settings are used: population size 80, number of iterations 200, tournament size 3, \({abits\_init\_prob}=0.8\), \({prob\_cross}=0.7\), \({prob\_mut\_activation}=0.1\), \({prob\_mut\_coordinates}=0.1\), \({prob\_mut\_resest}=0.02\), \({mut\_range}=0.1\).

Each of the algorithms described in Sect. 4.2 has been run ten times for each ESTP considered. Here we report results for mean Steiner ratios of these ten runs for each problem. This is due to the statistical comparison framework that is used in this work. The main aim is to compare the average results of 16 algorithms over 20 ESTP problems in a given group of problems (10, 20 and 50 terminals). Friedman test with Shaffer’s post hoc procedure is used to compare the mean Steiner ratios of each algorithm over a set of 20 problems in the group.

Friedman test is a type of non-parametric statistical test with the aim to discover differences in the mean results of several algorithms over several problems at once. This approach is much better than running several pair-wise statistical tests such as the sign tests or Wilcoxon test. The reason is that the probability of Type I error (discover a difference when there is, in fact, no difference between algorithms considered) is much smaller when running Friedman test. In the case of Friedman test, all algorithms being compared and all problems are taken up at once, and the pair-wise comparisons are performed only in case there are differences among the algorithms discovered by Friedman test. The ranking of algorithms is provided by the Friedman test, and the post-hoc procedure is used to control the Family-Wise Error Rate (FWER) for pair-wise comparisons. FWER reflects the probability of making one or more false discovering while performing pair-wise comparisons. For a much more detailed description of the Friedman test and the statistical comparison framework, the reader is referred to [23]. The results of Friedman test and Shaffer’s post hoc procedure presented in this work are calculated by Keel software package [24].

It should be mentioned here, that one of the requirements for Friedman test is that the number of algorithms being compared should be smaller than the number of problems. Since in this work there are 16 algorithms and 20 problems in a group, this requirement is satisfied.

The Friedman’s ranks achieved by each of the 16 algorithms for the 20 problems with ten terminals are presented in Table 2. These ranks are based on the average performance of the algorithms.

The first significant finding is that the idea of combining the evolutionary approach with local search procedures is justified. The “pure” evolutionary algorithm (enorm) and the greedy local search algorithms (nn3, nn5, nn-1) are performing poorly and have been assigned the worst ranks. On the other hand, the best performing algorithm is ip1.0, i.e., the MA with the improvement procedure as the local search method. It is interesting that its prob_change equals 1.0, which means that it is always beneficial to accept the improved solution. Algorithm ip1.0 is followed by several versions of evolutionary algorithms with the correction procedure as the local search method. In this case, it seems to be beneficial to use the Steiner ratio of the corrected solution as the fitness value of the original solution without changing it. What is more, from Table 3 it can be observed that the post hoc procedure is not able to detect significant (with significant level \(\upalpha =0.05\)) differences between the best performing algorithm (ip1.0) and algorithms cp0.2, cp0.0, cp0.4, cp0.6, cp0.8, and cp1.0. The p–values which indicate significant differences (less than \(\upalpha =0.05\)) are marked bold. Additionally, there is no difference detected between the best ip1.0 and algorithms ip0.8 and ip0.6. From this it can be concluded that the correction procedure can be used with Baldwin effect, Lamarckian evolution and any intermediate approach with no significant difference in averaged performance compared to the best performing one. On the other hand, when the improvement procedure is used, Lamarckian evolution is preferred. This can be explained by the observation that the improvement procedure modifies the solution (in a random way) much more than the correction procedure and using the Steiner ratio of the improved solution as the fitness value of the original solution is misleading to the evolutionary process. The correction procedure is better in estimating the potential of the unchanged solution and works better with low values of change_prob.

It should be kept in mind that these preliminary observations are based on relatively simple ESTPs with just ten terminals. A similar analysis in the next subsections based on ESTP with 20 and 50 terminals show which of these conclusions can also be supported in case of more difficult ESTPs.

For the sake of completeness, in Table 4 it is summarized for each algorithm, in how many ESTPs it was able to find the best-known solution (obtained by any of the algorithms considered). There are only minor differences among the best performing (in average) algorithms already mentioned. However, it could be surprising that for example, algorithm nn5 was able to find the best-known solutions in 18 ESTPs. Still, its average performance it significantly worse than that of ip1.0.

The Friedman’s ranks achieved by each of the 16 algorithms for the 20 problems with 20 terminals are presented in Table 5. These ranks are based on the average performance of the algorithms.

Similarly to the results for ESTPs with ten terminals, the best performing algorithm is ip1.0. However, based on the post hoc analysis (Table 6) its averaged performance is not significantly different (with the significance level \(\upalpha =0.05\)) than that of algorithms ip0.8, cp0.0, ip0.6, ip0.4, and cp0.2. Again, the correction procedure seems to work better with Baldwin effect (small values of change_prob) and the improvement procedure works better with high values of change_prob (Lamarckian evolution).

In this set of ESTPs with 20 terminals, it is even more evident that the simple evolutionary algorithm enorm is not able to solve the problems. Based on the post hoc analysis (Table 6), it can be observed that enorm is significantly worse than any of the hybrid methods. On the other hand, only algorithms ip1.0, ip0.8, cp0.0, ip0.6, ip0.4 are significantly better than algorithm nn5. However, algorithm nn5 by itself is found to be significantly better than none of the considered ones.

Table 7 shows the number of best solutions found by each of the algorithms. Again, there is a remarkable ability of the nn5 algorithm to find the best solutions at least once compared to its poor averaged performance. Taking into account the average performance and the number of best solutions found, it can be concluded from this set of experiments that the evolutionary algorithm with improvement procedure and Lamarckian evolution should be preferred.

The Friedman’s ranks achieved by each of the 16 algorithms for the 20 problems with 50 terminals are presented in Table 8. These ranks are based on the average performance of the algorithms.

In the case of ESTPs with 50 terminals, it is evident that the evolutionary algorithms with improvement procedure and Lamarckian evolution performs best on average. It can be observed (Table 8) that ip1.0, ip0.8, ip0.6, ip0.4 and ip0.2 have the best ranks from among all algorithms. Algorithm ip1.0 is assigned the highest rank, however, a significant difference (Table 9) between ip1.0 and algorithms ip0.8, ip0.6, ip0.4 and ip0.2 cannot be discovered. Accepting the improved solution is highly beneficial as even the small values of change_prob (such as in ip0.2) make the evolutionary algorithm with improvement procedure significantly better than ip0.0. On the other hand, the usefulness of using the correction procedure as the local search method in the evolutionary algorithm is no longer proved when compared to the best performing ip1.0 and ip0.8 algorithms: according to Shaffer’s post hoc procedure, any of the algorithms cp0.0–cp1.0 are performing significantly worse than ip1.0 and ip0.8. On the other hand, the correction procedure in MA with any change_prob value improves the performance of simple evolutionary algorithm enorm significantly. Taking into account that the correction procedure is much less computationally expensive than the improvement procedure, it might still be of use in difficult problems with many terminals.

Similarly to the previous set of experiments the relatively high rank of nn5 heuristic should be noticed. Again, based on the results, there is not enough evidence that its averaged behavior is better than any of the evolutionary algorithms with improvement or even correction procedures. The high rank of the nn5 algorithm might be explained based on the results presented in Table 10, where the numbers of best solutions found by each of the algorithms are presented. It is interesting to note that the clear winner here is nn5 heuristic. It can be deduced that the poor average performance of nn5 is somehow compensated by its ability to find the best solutions in only limited number of the considered ten runs per problem.

In order to assess the ability of the proposed approach to provide optimal or near optimal solutions, ESTPs from OR–Library have been used [25]. In this section we compare the results of the proposed algorithm with the best performing settings (ip1.0) with the optimal solutions for the problems provided in the OR-Library files estein10, estein20, estein30, estein40, estein50, estein60, estein70, estein80, estein90 and estein100. Those files have been obtained from http://​people.​brunel.​ac.​uk/​~mastjjb/​jeb/​orlib/​esteininfo.​html. Each file contains 15 EST problems with the number of terminals corresponding to the number in the name of the file. For example, in the file estein80, there are 15 problems, each with 80 terminals (points on 2D plane).

The algorithm ip1.0 with the same settings as in the previous subsection has been run ten times for each problem. The mean and the best Steiner ratios have been calculated for each problem over the ten results. Next, for each group of problems of a given size, the average, minimum and maximum Steiner ratio have been found in the 15 problems. Next, these values have been compared with the Steiner ratios of the known optimal solutions taken from the library file. The results are summarized in Figs. 8 and  9. The presented values are the quotient of the mean, minimum and maximum values of the quotient for each group of problems. The value of the quotient equal 1 indicates that the optimal solution has been found. The bigger the values, the worse the solution (bigger Steiner ratio).

From the results presented in Figs. 8 and  9, it can be seen that the proposed algorithm can provide stable performance and find near-optimal solutions. From Fig. 9 it can be seen that the Steiner ratios of the best solutions are never worse more than 1% than the Steiner ratios of the optimal solutions from OR-Library. The mean Steiner ratios are worse slightly more than 1% than the optimal ones only for a few problems with 90 and 100 terminals (Fig. 8).

The results presented in this section indicate that the proposed algorithm scales well with the size of the problems. Perfect solutions have been found for all problems with 10 and 20 terminals and near optimal solutions for the rest. No significant fall in the quality of the results can be observed when the number of terminals grows.