Keywords

1 Introduction

In the last several decades there has been an extensive research effort on developing different metaheuristics for finding near optimal solutions for hard optimization problems. Most metaheuristic approaches focus on how to balance the global search (exploration) and local search (exploitation) in examining the solution space. There have been several directions in this research. Early methods include simulated annealing [23] and tabu search [15, 16] where the search is focused near the best found solution and on mechanisms of escaping local optima. In later stages population based methods have proven to be very powerful. The general approach in such methods is generating a large number of solutions and including different types of learning mechanisms. In case of genetic algorithms [27] and differential evolution [28] the main idea is in combining different high quality solutions with the addition of a certain level of randomization. Particle swarm optimization [1, 2] explores the solution space through generating new solutions based on the positions of the globally and locally best found solution. This basic idea has been incorporated in a wide range of similar methods like cuckoo search [14], artificial bee colony algorithm [22] and many others. (The reader should note that we are fully aware about the controversial discussion with respect to some of these or similar approaches; see [31].) The ant colony optimization [10, 20] uses a population based method to add a learning mechanism to greedy algorithms.

One of the most common methods for improving population based metaheuristics is by combining them with local searches. The variable neighborhood search [17] metaheuristic focuses on the efficient use of local searches. The performance of the original metaheuristics is often improved by different types of enhancements or by creating hybridized methods that combine one or more of such metaheuristic methods [5, 25, 34]. The main problems with such methods is the increased complexity of implementation. This problem is most evident if we observe publications in fields other than operations research and applied mathematics. In the vast majority of them only the original, simple to implement, method is used to solve the problem of interest.

Model-based heuristics are generally based upon the identification of a set of parameters, defining a model that, in turn, well captures some features of the search space [6]. These algorithms heavily rely on a set of update schemes used to progressively modify the model itself such that the possibility of obtaining higher quality solutions under the new model is increased. Recently, more and more emphasis is put on the application of learning mechanisms. In this phase, modifications are applied to the model and/or its parameters to reflect insights collected and generated during the search phase.

Well-known paradigms that can be interpreted under the philosophy of model-based heuristics are mostly from the area of Swarm Intelligence, but also focus on semi-greedy heuristics, including the greedy randomized adaptive search procedure (GRASP) [12, 18], where the greedy function that guides the selection of the best candidates might incorporate some sort of stochastic model. Semi-greedy heuristics and GRASP exemplify of how simplicity is important. Although it generally has a worse performance than combining one of the more complex methods with a local search it is extensively used. The advantage of more complex metaheuristics often occurs only for very large problem instances; some examples in case of ACO can be seen in [19, 21]. Because of this, it is reasonable to attempt to increase the size of problems that GRASP can solve, but in a way that there is no or only a small increase in complexity of the original method.

In this paper we focus on developing this type of method through adding a simple learning mechanism to GRASP. Some examples of such methods are GRASP with path relinking [13] and the dynamic convexized method [37]. Both of these methods produce a significant level of improvement. Note that both use the standard concept of intensifying the search of the solution space based on the location of globally and locally best found solutions. The basic concept of the proposed fixed set search method (FSS) is to avoid focusing on specific high quality solutions but on parts or elements that such solutions have. This idea of exploiting elements that belong to high quality solutions is used in ACO, were the randomized greedy algorithm is directed to choose such elements. The concept of generating new solutions based on the frequency of elements appearing in high quality solutions is the basis of the cross-entropy method (CE) [9]. The main conceptual difference between FSS and these two methods is that the proposed methods use only elements that are a part of locally optimal solutions. In practice this produces a significant difference in performance since the CE and ACO tend to over popularize elements in the best solution and in small variations of it and the FSS does not.

The ideas for developing this method may be based on earlier notions of chunking [35, 36], vocabulary building and consistent chains [30] as they have been used, e.g., in relation to tabu search. In those notions one relates given solutions of an optimization problem as composed of parts (or chunks). Considering the traveling salesman problem (TSP), for instance, a part may be a set of nodes to be visited consecutively. Moreover, some parts may be closely related to some other parts so that a corresponding connection can be made between two parts. Similar ideas are even found in the POPMUSIC paradigm [33]. The general idea of the proposed approach is to fix a set of elements that exist in high quality solutions and dedicate computational effort on “filling in the gaps”. The idea of fixed sets has also been explored in the construct, merge, solve & adapt (CMSA) [4] matheuristic. In CMSA, which may also be interpreted as an implementation of POPMUSIC, a fixed set is used to decide which part of the solution space will be explored using an exact solver; later the newly generated solution is used to direct the next step of the search.

The concept of using fixed sets is illustrated on the symmetric TSP through adding a learning mechanism to GRASP. We should note that exact codes for the TSP are available [7]. Nevertheless, due to its widespread investigation it seems appropriate to use it for illustration purposes. As it will be seen in the following, this type of approach can easily be added to existing GRASP algorithms and produces a high level of improvement in the quality of found solutions and computational cost.

The paper is organized as follows. In the next section we give a brief description of GRASP for the TSP. Then we present the FSS and show how it is applied to the TSP. In Sect. 4, we discuss the performed computational experiments.

2 GRASP

In this section we provide a short outline of the GRASP used for solving the TSP. (A pseudocode for the general GRASP is given in Algorithm 1.) In the case of the TSP it is common to use a randomization of the nearest neighbor greedy algorithm with a restricted candidate list (RCL) based on the cardinality of nodes [3]. For the local search, the most commonly used ones are the 2-OPT [8] and 3-OPT [24] searches. In practice instead of the original versions of the two local searches it is common to use a RCL of edges that will be used for evaluating the proposed improvement.

figure a

3 Fixed Set Search

In this section we present the proposed fixed set search metaheuristic and show how it can be used in combination with GRASP. Before giving the details of the method we give the basic concepts on which it is constructed.

One of the main disadvantages of GRASP is the fact that it does not incorporate any learning mechanism. On the other hand, such an improvement should be designed in a way that it is simple to implement. In this paper we propose one such method called the fixed set search (FSS). In the following we will assume that a solution S of the problem of interest can be represented in the form of a set. In case of the TSP, the solution S can be viewed as a set of edges \(\{ e_1, e_2, \ldots , e_l\}\). The development of FSS is based on two simple premises:

  • A combinatorial optimization problem is generally substantially easier to solve if we fix some parts of the solution, and in this way lower the size of the solution space that is being explored.

  • There are some parts of high quality solutions that are “easy to recognize”. We say this in the sense that they appear in many good solutions. In general there is no need to dedicate a significant amount of computational effort to analyze them.

The general idea of FSS is to fix such “easy to recognize” parts of good solutions and dedicate computational effort in finding the optimal (or close to optimal) solution for the corresponding subset of the solution space. Informally, we take the common sections of good solutions, which we will call the fixed set, and try to “fill in the gaps”. In the following sections we will illustrate how this simple idea can be incorporated in the GRASP metaheuristic for the TSP. The proposed algorithm has three basic steps. The first one is finding a fixed set. The second is adapting the randomized greedy algorithm to be able to use a preselected set of elements. Finally, specify and apply the method which gains experience from previously generated solutions.

3.1 Fixed Set

As previously stated, to be able to implement the proposed method it is necessary that we can represent a solution of the problem in the form of a set S. In case of the TSP, a solution S corresponds to the set of edges that represent a Hamiltonian cycle. Let us use the notation \(\mathcal {P}\) for the set of all the generated solutions (population). In relation, let us define \(\mathcal {P}_n\) as the set of n best generated solutions based on the objective function, the path length. Further, let us use the notation F for a fixed set that will be used in the search. Note that the elements of F will be inside the newly generated solution. In the following we define a method for finding a fixed set F for a population of solutions \(\mathcal {P}\). The proposed method should satisfy the following requirements:

  • (R1) A generated fixed set F should consist of elements of high quality solutions.

  • (R2) The method should be able to generate many different random fixed sets that can be used to generate new high quality solutions.

  • (R3) A generated fixed set F can be used to generate a feasible solution. More precisely, there exists a feasible solution S such that \(F \subset S\)

  • (R4) Ability to control the size of the generated fixed set |F|.

The first two requirements can be achieved if we only use some randomly selected high quality solutions for generating the fixed sets. This can be achieved by simply selecting k random solutions from the set \(\mathcal {P}_n\). Let us define \(\mathcal {S}_{kn}\) as the set of selected solutions. The initial idea is to use the intersection of all the solutions in \(\mathcal {S}_{kn}\) for the fixed set F. The problem is that we have no control over the size of the intersection. A simple idea to control the size of F is, instead of using the intersection of \(\mathcal {S}_{kn}\), to select the elements (edges) that are part of the highest number of solutions. The problem with this approach is that such a selection can potentially contain edges that could not be used to generate a feasible solution.

Both of these issues can be avoided if a base solution \(B \in \mathcal {P}_m\) is used in generating a fixed set F. More precisely, we can select the elements of B that occur most frequently in \(\mathcal {S}_{kn}\). Let us define this procedure more formally. We will assume that we are finding a fixed set F with \(|F| = Size\) for a set of solutions \(\mathcal {S}_{kn} = \{S_1, .., S_k\}\) and base solution \(B = \{ e_1, \ldots e_l\}\). Let use define the function \(C(e_x, S)\) which is equal to 1 if \(e_x \in S\) and 0 otherwise. Using \(C(e_x, S)\) we can define a function that counts the number of times an edge \(e_x\) occurs in \(\mathcal {S}_{kn}\) as follows.

$$\begin{aligned} O(e_x, \mathcal {S}_{kn}) = \sum _{S \in \mathcal {S}_{kn}}C(e_x,S) \end{aligned}$$
(1)

Now, we can define \(F \subset B\) as the set of edges \(e_x\) that have the largest value of \(O(e_x, \mathcal {S}_{kn})\). In relation, let us define function \(F = Fix(B,\mathcal {S}_{kn}, Size)\) that corresponds to the fixed set generated for a base solution B, a set of solutions \(\mathcal {S}_{kn}\) having Size elements. An illustration of the method for generating a fixed set for the TSP can be seen in Fig. 1.

Fig. 1.
figure 1

Illustration of generating a fixed set. The input is \(\mathcal {S}_{kn}\) (top left), a set of four randomly selected solutions out of the six best ones, and a base solution B (left bottom). Values on an edge of B represent the number of occurrences of that edge in elements of \(\mathcal {S}_{kn}\). The edges on the right present the corresponding fixed set of size four.

Full size image

3.2 Randomized Greedy Algorithm with Preselected Elements

To be able to use the fixed set within a GRASP setting we need to adapt the greedy randomized algorithm. Let us first note that in case of the TSP, the fixed set F will consist of several paths (sequence of edges which connect a sequence of vertices) of graph G. This effects the greedy algorithm in two ways. First, the inside nodes of the path should be removed from the candidate list. Secondly, if a node that is a start or end node of a path in the fixed set, is added to the current partial solutions the whole path must be added in the proper direction. Pseudocode for the adapted greedy algorithm can be seen in Algorithm 2.

figure b

In relation, let us define the function \(S = RGF(F)\), for a fixed set F, as the solution acquired using this algorithm.

3.3 Learning Mechanism

In this section we present the FSS which is used as a learning mechanism for GRASP. Before presenting details of the proposed methods, let us first make a few observations. In the general case the early iterations of GRASP frequently manage to improve the quality of the best found solution. At later stages such improvements become significantly less frequent and the method becomes dependent on “lucky” hits. The idea is to use a fixed set F, for some promising region of the solution space, generate a solution \(S = RGF(F)\) and apply a local search to S. In this way we increase the probability that a higher quality solution will be found. An important aspect is how to select the size of the fixed set. In case it is small, it efficiently performs a global search but after a certain number of executions, as in the case of GRASP, it will to a large extend be dependent on “lucky” hits. On the other hand if F is large, it will only explore the parts of the solution space that are close to already generated solutions. As a consequence, there is a high risk of being trapped in locally optimal solutions.

This indicates that the size of the fixed set should be adapted during the execution of the algorithms. For simplicity, we can a priori define an array Sizes of fixed set sizes that will be tested, using the following formula:

$$\begin{aligned} Sizes[i] = |V| - \frac{|V|}{2^i} \end{aligned}$$
(2)

In (2), V represents the set of nodes of the graph on which the TSP is to be solved. The maximal value of an element in the array Sizes is chosen based on the problem being solved. Using this array let us give an outline of the FSS. We will first generate an initial population of solutions \(\mathcal {P}\) by executing GRASP for N iterations. This initial population will be used to find the fixed sets. We start from a small fixed set and generate solutions until stagnation, in the sense of not finding new best solutions for a large number of iterations, has occurred. When stagnation occurs, we increase the size of the fixed set (selecting the next element of Sizes) and repeat the procedure. In this way a more focused exploration of the search space is executed. This procedure is repeated until the largest element in Sizes is tested.

At this stage it is expected that the set \(\mathcal {P}_m\) of m best solutions has significantly changed and contains higher quality solutions than in the initial population. Because of this, there is a potential that even for smaller sized fixed sets, since they are now generated using better solutions, there is a higher probability of finding new quality solutions. So, we can repeat the same procedure from the smallest fixed set size. Let us note that after a large number of solutions is generated the new solutions acquired using small fixed sets are rarely new best ones. The importance of their revisit is in generating new types of high quality solutions. If the method does not manage to find a new solution among the best m ones for a large number of iterations for a specific fixed set size, this size can be excluded from the further search. This idea is better understood by observing the pseudocode for FSS given in Algorithm 3.

figure c

In the pseudocode for the FSS, the first step is initializing the sizes of fixed sets using (2). Next the initial population of solutions is generated performing N iterations of the basic GRASP algorithm. The current size of the fixed set Size is set to the smallest fixed set size. In the main loop, we first randomly generate a set of solutions \(\mathcal {S}_{kn}\) by selecting k elements from \(\mathcal {P}_n\). Next, we select a random solution B out of the set \(\mathcal {P}_m\). Using \(\mathcal {S}_{kn}\), B and Size we generate the fixed set F as described in the above. Using F we generate a solution \(S= RGF(F)\) using the randomized greedy algorithm with preselected elements. Next, we apply the local search to S and check if we have found a new best solution and add it to the set of generated solutions \(\mathcal {P}\). After a new solution is generated we check the two stagnation conditions. The first one checks if the search for the best solution has become stagnant. If so, we set the value of Size to the next value in Sizes. Let us note, that the next size is the next larger element of array Sizes. In case Size is already the largest size, we select the smallest element in Sizes. Before updating Size, we also check if stagnation has occurred in the search of high quality solutions (we have not found a solution which is among the best n or m ones). In case this is true the current Size is removed from Sizes. It is important to note, that this is only done if Size is equal to the smallest member of Sizes. This is due to the fact that if we have managed to find an improvement for a smaller fixed set than Size, it is expected that we have just been “unlucky” and there is no need to remove this value from the search. This procedure is repeated until the array Sizes is empty or some other termination criterion is satisfied.

4 Results

In this section we present the results of our computational experiments used to evaluate the performance of the proposed method. This has been done in a comparison with the GRASP algorithm presented in [26], the dynamic convexized method (DCTSP) from [37] and the ant colony optimization combined with a the 2-OPT local search (ACO-2OPT) [32]. The focus of the comparison is on the quality of found solutions.

The FSS and GRASP have been evaluated for both 2-OPT and 3-OPT as local searches. In case of the DCTSP a combination of 2-OPT and 3-OPT has been used as a local search. GRASP has been included to be able to evaluate the effect of the learning mechanism included in the FSS. DCTSP has been used in the comparison since it is a good representative of a metaheuristic whose search is focused on regions near the best solution. The comparison with ACO-2OPT is used to show the advantage of having a learning mechanism dependent on the local search, which is the case for FSS but not ACO-2OPT. In case of the FSS the randomized greedy algorithm used an RCL with 20 elements. In case of both local searches, 2-OPT and 3-OPT, the same size of RCL has been used. To increase the computational efficiency of the local searches we have used the standard approach of “don’t look bits” (DLBs) [3]. Note that when we apply the local search inside the main loop of FSS, some of the DLBs could be preset based on the fixed set which significantly decreased the computational cost. The parameters for FSS are the following; \(k=10\) random solutions are selected from the best \(n=500\) ones for the set of solutions \(\mathcal {S}_{kn}\). The base solution is selected from the \(m=100\) best solutions. The size of the initial population was 100. The stagnation criterion was that no new best or high quality solution has been found in the last \(Stag=100\) iterations for the current fixed set size. The FSS and GRASP with 2-OPT have been implemented in C# using Microsoft Visual Studio 2017. The calculations have been done on a machine with Intel(R) Core(TM) i7-2630 QM CPU 2.00 GHz, 4 GB of DDR3-1333 RAM, running on Microsoft Windows 7 Home Premium 64-bit.

The comparison of the methods has been done on the standard benchmark library TSPLIB [29]. The test instances are the same as in [37]. A total of 48 test instances with Euclidean distances are used, with the number of nodes ranging from 51 to 2392. Note that in FSS the fact that distances are Euclidean is not exploited. The termination criterion was that a maximal number of solutions has been generated. The limit was the same as in [37], more precisely in case of problem instances having less than 1000 nodes it was 100|V|, with V the set of nodes of the considered instance, and in case of larger instances it was 10|V|. For each of the instances a single run of each of the methods has been performed, as in [37]. The results of the computational experiments can be seen in Table 1. In it, the results for DCTSP are taken from [37] and for GRASP with 3-OPT are taken from [26]. Note that the results for GRASP-3OPT are very similar to the ones from [26] and slightly better than our implementation. In case of \(ACO-2OPT\), the results for the same number of generated solutions and applied local searches have been taken from [32]. Note that these results correspond to an average of ten independent runs.

Table 1. Comparison of the proposed algorithms with GRASP and DCTSP for different TSPLIB instances.
Full size table

From the results in Table 1, we can first observe that the GRASP-2OPT has a significantly worse performance than all other methods finding best known solutions for only four instances and having an average relative error of 2.73%. In case of FSS-2OPT, the improvement is very significant: 20 known best solutions are found and the average relative error is 0.40%. What is very interesting is that FSS-2OPT performs only slightly worse than GRASP-3OPT which finds 22 known best solutions and has an average relative error of 0.39%. This indicates that the use of the proposed method can be very beneficial in case of less powerful local searches. The FSS-2OPT has found a higher quality solution than ACO-2OPT for each of the test instances from [32]. The average relative error of FSS-2OPT, on these instances, is 0.36% compared to 1.65% of ACO-2OPT.

Although FSS-2OPT has an overall worse performance than DCTSP, it manages to find better solutions for five problem instances. From the results in Table 1, it is evident that FSS-3OPT has the best performance. It manages to find better solutions than all the other methods for all instances or equal in case methods have found best known solutions. It finds three more known optimal solutions than DCTSP and has a notable improvement in relative average error. It is important to note that FSS-3OPT never has an error greater than 0.40%.

The parameters selected for specifying FSS have been chosen empirically through extensive testing. Overall the FSS is not highly sensitive to these parameters. The parameter k used to specify the number of solutions selected for generating the set \(S_{kn}\) had the following effect. In case of small values, the selection would result in highly randomized fixed sets. The reason for this is that there are no clear “good elements”, especially in case of larger problem instances where there are not many common elements in all the solutions. In case of large values of k, the method would select very similar fixed sets. The parameter m used to specify the population from which the base solution would be selected has the following effect. In case of small values of m the convergence speed would initially be very fast but would quickly get trapped in locally optimal solutions. This is due to the fact that it becomes very hard to find new high quality solutions. Such values of m are useful in case we can only generate a small number of solutions. In case of high values of m, the convergence speed is much slower. The problem is that when the fixed set is generated for a lower quality solution B, although the method manages to find solutions of higher quality than B, it is unlikely that very high quality ones will be found. The effect of parameter n for specifying the size of the population used for generating \(S_{kn}\) had a similar effect but to a much lower extent. We found that the best choice of parameters for stagnation, both for finding best and high quality solutions, was the same as the number of iterations from which GRASP would rarely find new best solutions. In general, it is important to avoid very small values for this parameter because it results in prematurely stopping the evaluation of small fixed sets.

Fig. 2.
figure 2

Average relative error for multiple TSPLIB problem instances with normalized execution time

Full size image
Fig. 3.
figure 3

Average solution quality of ten independent runs of FSS and GRASP for the TSPLIB problem instances

Full size image

In Table 1 we did not include computational times, since they are highly dependent on structures used for implementing the local searches. The same information is excluded in the articles used for comparison. We would like to note that in case of our implementation of FSS and GRASP there was a significant decrease in computational time. This is due to the fact of a smaller candidate set for the greedy algorithm. The second reason is that the number of iterations needed to generate the solution was significantly lower. As it is well-known, the computational cost of 2-OPT and 3-OPT local searches is significantly higher than for generating the initial solution. An extensive analysis of the computational cost of 2-OPT can be found in [11]. In case of FSS, we exploit the fact that the fixed set is a subset of a locally optimal base solution B through DLBs. More precisely, the DLBs of all the inner points of paths in the fixed set can be preset. Note that the number of preset DLBs is close to the size of the fixed set. In practice this means instead of having the computational cost of the first iteration of 2-OPT being proportional to |V|C, were C is the size of the RCL, it is close to \((|V| -|F|) C\). Similar analysis can be done for the 3-OPT local search. In case of very large fixed sets, the time FSS generated a new solution and applied the local search was a fraction of the time needed to accomplishing the same task in GRASP. It is expected that a similar behavior would be present in applying FSS to other combinatorial problems.

This decrease in computational cost of the FSS compared to GRASP directly effects the convergence speed. In Fig. 2 we show the average relative error for instances having up to/above 1000 nodes for normalized time. The normalization has been done based on the maximal time needed for all the methods to find the best solutions for each instance. From these results it is evident that the use of FSS significantly increases the convergence speed. Another illustration of this behavior can be seen in Fig. 3 for representative problem instances. In each of the figures the convergence speed of the average solution length for ten independent runs of GRASP and FSS, with 2-OPT and 3-OPT used as local searches, are shown. It can be observed that there is a drastic increase in the convergence speed after the initial population is generated for the FSS.

5 Conclusion

In this paper we have presented a new metaheuristic called fixed set search that exploits the common elements of high quality solutions. The proposed metaheuristic represents a method of adding a learning mechanism to the GRASP metaheuristic. It is expected that FSS can be applied to a wide range of problems since the only requirement is that the solution can be represented in a set form. A very important aspect of FSS is the simplicity in which a GRASP algorithm can be adapted to it. This is done with two basic steps. Firstly, the randomized greedy algorithm, used in the GRASP, is adapted to a setting were some elements are preselected. We have shown that this can be trivially achieved in case of the TSP, and it is expected that this is the case for many other combinatorial problems. Secondly, the method for generating a fixed set needs to be implemented which consists in selecting several solutions and tracking the number of times their elements occur in a selected base solution.

We have illustrated the effectiveness of the proposed approach on the TSP. Our computational experiments have shown that the proposed method has a significantly better performance than the basic GRASP approach when both solution quality and convergence speed are considered. Further, we have shown that the approach has a considerably better performance than the dynamic convexized method applied to the TSP in case 3-OPT is used as a local search. The proposed method has proven very efficient in improving the performance of GRASP in case of a less powerful local search.

It is important to note that there is a wide range of potential improvements to the proposed method. Some examples are having a more intelligent method of selecting the solutions used in generating the fixed set, or adapting the computational effort used to solve the subproblem related to a specific fixed set. Our objective was to show that even in the most basic form the proposed method can produce a significant improvement. We would like to note that the concept of using a fixed set can potentially be used to hybridize other metaheuristics like ACO, genetic algorithms and similar, for solving large scale problems through focusing the search in some promising areas of the solution space. On the other hand the idea of fixing elements of a solution can easily be included in mixed integer programs so there is a potential of adapting FSS to a matheuristic setting.