5.4.3.1. GRASP for the FFMSP

GRASP is a multistart metaheuristic framework [FEO 89, FEO 95]. As introduced briefly in section 1.2.3, each GRASP iteration consists of a construction phase, where a solution is built adopting a greedy, randomized and adaptive strategy besides a local search phase which starts at the solution constructed and applies iterative improvement until a locally optimal solution is found. Repeated applications of the construction procedure yield diverse starting solutions for the local search, and the best overall local optimal solution is returned as the result. The reader can refer to [FES 02b, FES 09a, FES 09b] for annotated bibliographies of GRASP.

The construction phase iteratively builds a feasible solution, one element at a time. At each iteration, the choice of the element to be added next is determined by ordering all candidate elements (i.e. those that can be added to the solution) in a candidate list C with respect to a greedy criterion. The probabilistic component of a GRASP is characterized by randomly choosing one of the best candidates in the list, but not necessarily the top candidate. The list of best candidates is called the restricted candidate list (RCL). Algorithm 5.1 depicts the pseudo-code of the GRASP for the FFMSP proposed in [FER 13b]. The objective function to be maximized according to [5.17] is denoted by For each position j ∈ {1, … , m} and for each character c ∈ Σ, V_j(c) is the number of times c appears in position j in any of the strings in Ω. In line 2, the incumbent solution s_best is set to the empty solution with a corresponding objective function value f_t(s_best) equal to −∞. The for-loop in lines 3–6 computes and as the minimum and the maximum function value V_j(c) all over characters c ∈ Σ, respectively. Then, until the stopping criterion is no longer met, the while-loop in lines 7–13 computes a GRASP incumbent solution s_best which is returned as output in line 14.

Algorithm 5.2 shows a pseudo-code of the construction procedure that iteratively builds a sequence s = (s₁, … , s_m) ∈ Σ^m, selecting one character at time. The greedy function is related to the occurrence of each character in a given position. To define the construction mechanism for the RCL, once and are known, a cut-off value is computed in line 5, where α is a parameter such that 0 ≤ α ≤ 1 (line 4). Then, the RCL is made up of all characters whose greedy function value is less than or equal to μ (line 8). A character is then selected, uniformly at random, from the RCL (line 11).

The basic GRASP local search step consists of investigating all positions j ∈ {1, … , m} and changing the character in position j in the sequence s to another character in RCL_j. The current solution is replaced by the first improving neighbor and the search stops after all possible moves have been evaluated and no improving neighbor has been found, returning a locally optimal solution. The worst case computational complexity of the local search procedure is O(n · m · |Σ|). In fact, since the objective function value is at most n, the while-loop in lines 2–14 runs at most n times. Each iteration costs O(m · |Σ|), since for each j = 1, … , m, |RCL_j| ≤ |Σ| − 1.

5.4.3.2. The hybrid heuristic evaluation function

The objective function of any instance of the FFMSP is characterized by large plateaus, since there are |Σ|^m points in the search space with only n different objective values. To efficiently handle the numerous local maxima, Mousavi et al. [MOU 12a] proposed a new function to be used in the GRASP framework in conjunction with the objective function when evaluating neighbor solutions during the local search phase.

Given a candidate solution s ∈ Σ^m, the following further definitions and notations are needed:

• – Near(s) = {s^j ∈ Ω | d_H(s, s^j) ≤ t} is the subset of the input strings whose Hamming distance from s is at most t;
• – for each input string s^j ∈ Ω, its cost is defined as c(s^j, s) = t−d_H(s, s^j);
• – a L-walk, L ∈ , 1 ≤ L ≤ m, is a walk of length L in the solution space. A L-walk from s leads to the replacement of s with a solution so that
• – given a L-walk from s to a solution s and an input string s^j ∈ Ω, then
• – a L-walk from s is random if is equally likely to be any solution ŝ where d_H (s, ŝ) = L.

In the case of a random L-walk, Δ_j is a random variable and Pr_L(Δ_j ≤ k), k ∈ , denotes the probability of Δ_j ≤ k as a result of a random walk.

• – where s^j ∈ Near(s) and L = c(s^j, s), the potential gain g_j(s) of s^j with respect to s is defined as follows:
  
• – where s^j ∈ Near(s) and L = c(s^j, s):
  • - the potential gain g_j(s) of s^j with respect to s is defined as follows:
    
  • - the Gain-per-Cost GpC(s) of s is defined as the average of the gain per cost of the sequences in Near(s):

Computing the gain-per-cost of candidate solutions requires knowledge of the probability distribution function of Δ_k for all possible lengths of random walks and this task has high computational complexity. To reduce the computational effort, Mousavi et al. proposed to approximate all these probability distribution functions with the probability distribution function for a unique random variable Δ corresponding to a random string as a representative of all the strings in Ω. With respect to a random L-walk, Δ is defined as , where ŝ is a random string (and not an input string) and s and are the source and destination of the random L-walk, respectively. Once the probability distribution function for the random variable Δ is known, to evaluate candidate solutions based on their likelihood of leading to better solutions, Mousavi et al. define the as follows:

where s is a candidate solution, and is the estimated gain of s^j, with respect to s, defined as follows:

Then, they define a heuristic function which takes into account both the objective function and the estimated gain-per-cost function

Given two candidate solutions function must combin and in such a way that:

if and only if either and In other words, according to function the candidate solution is considered better than ŝ if it corresponds to a better objective function value or the objective function assumes the same value when evaluated in both solutions, but has a higher probability of leading to better solutions. Based on proven theoretical results, Mousavi et al. proposed the following heuristic function where s is a candidate solution:

Looking at the results of a few experiments conducted in [MOU 12a], it emerges that use of the hybrid heuristic evaluation function in place of the objective function in the GRASP local search proposed by Festa [FES 07] results in a reduction in the number of local maxima. Consequently the algorithm’s climb toward better solutions is sped up. On a large set of both real-world and randomly-generated test instances, Ferone et al. [FER 16] conducted a deeper experimental analysis to help determine whether the integration of the hybrid heuristic evaluation function of Mousavi et al. in a GRASP is beneficial. The following two sets of problems were used:

• – Set A: this is the set of benchmarks introduced in [FER 13b], consisting of 600 random instances of different sizes. The number n of input sequences in Ω is {100, 200, 300, 400} and the length m of each of the input sequences is {300, 600, 800}. In all cases, the alphabet consists of four letters, i.e. |Σ| = 4. For each combination of n and m, the set A consists of 100 random instances. The threshold parameter t varies from 0.75 m to 0.85 m.
• – Set B: this set of problems was used in [MOU 12a]. Some instances were randomly generated, while the remaining are real-world instances from biology (Hyaloperonospora parasitica V 6.0 sequence data). In both randomly-generated and real-world instances, the alphabet as four letters, i.e.|Σ| = 4, the number n of input sequences in Ω is {100, 200, 300} and the length m of each of the input sequence ranges from 100 to 1200. Finally, the threshold parameter t varies from 0.75 m to 0.95 m.

Looking at the results, Ferone et al. concluded that either the two algorithms find the optimal solution or the hybrid GRASP with the Mousavi et al. evaluation function finds better quality results. The further investigation performed by the authors that involves the study of the empirical distributions of the random variable time-to-target-solution-value (TTT-plots) considering the following instances is particulars interesting:

1. 1) random instance where n = 100, m = 600, t = 480 and target value = 0.68 × n (Figure 5.1);
2. 2) random instance where n = 200, m = 300, t = 255 and target value = 0.025 × n (Figure 5.2);
3. 3) real instance where n = 300, m = 1200, t = 1, 020 and target value = 0.22 × n (Figure 5.3).

Ferone et al. performed 100 independent runs of each heuristic using 100 different random number generator seeds and recorded the time taken to find a solution at least as good as the target value . As in [AIE 02], to plot the empirical distribution, a probability is associated with the i^th sorted running time (t_i) and the points z_i = (t_i, p_i), for i = 1, … , 100, are plotted. As shown in Figures 5.1–5.3, we can observe that the relative position of the curves implies that, given any fixed amount of run time, the hybrid GRASP with the Mousavi et al. evaluation function (grasp-h-ev) has a higher probability of finding a solution with an objective function value at least as good as the target objective function value than pure GRASP (grasp).

5.4.3.3. Path-relinking

Path-relinking is a heuristic proposed by Glover [GLO 96, GLO 00b] in 1996 as an intensification strategy exploring trajectories connecting elite solutions obtained by Tabu search or scatter search [GLO 00a, GLO 97, GLO 00b, RIB 12].

Starting from one or more elite solutions, paths in the solution space leading towards other guiding elite solutions are generated and explored in the search for better solutions. This is accomplished by selecting moves that introduce attributes contained in the guiding solutions. At each iteration, all moves that incorporate attributes of the guiding solution are analyzed and the move that best improves (or least deteriorates) the initial solution is chosen.

Algorithm 5.3 illustrates the pseudo-code of path-relinking for the FFMSP proposed by Ferone et al. in [FER 13b]. It is applied to a pair of sequences (s′ , ŝ). Their common elements are kept constant and the space spanned by this pair of solutions is searched with the objective of finding a better solution. This search is done by exploring a path in the space linking solution s′ to solution ŝ. s′ is called the initial solution and ŝ the guiding solution.

The procedure (line 3) computes the symmetric difference Δ(s′, ŝ) between the two solutions as the set of components for which the two solutions differ:

Note that, and represents the set of moves needed to reach ŝ from s′, where a move applied to the initial solution s′ consists of selecting a position and replacing with ŝ_i.

Path-relinking generates a path of solutions linking s′ and ŝ. The best solution s^* in this path is returned by the algorithm (line 13). The path of solutions is computed in the loop in lines 4 through 12. This is achieved by advancing one solution at a time in a greedy manner. At each iteration, the procedure examines all moves i ∈ Δ(s′, ŝ) from the current solution s′ and selects the one which results in the highest cost solution (line 5), i.e. the one which maximizes f_t(s′ ⊕ i), where s′ ⊕ i is the solution resulting from applying move i to solution s′. The best move i^* is made, producing solution s′ ⊕ i^* (line 7). The set of available moves is updated (line 6). If necessary, the best solution s^* is updated (lines 8–11). The algorithm stops when Δ(s′ , ŝ) = ∅.

Given two solutions s′ and ŝ, Ferone et al. adopted the following path-relinking strategies:

• – Forward PR: the path emanates from s′ , which is the worst solution between s′ and ŝ (Algorithm 5.3);
• – Backward PR: the path emanates from s′, which is the best solution between s′ and ŝ (Algorithm 5.3);
• – Mixed PR: two paths are generated, one emanating from s′ and the other emanating from ŝ. The process stops as soon as an intermediate common solution is met (Algorithm 5.4);
• – Greedy Randomized Adaptive Forward PR: the path emanates from the worst solution between s′ and ŝ. At each iteration a move is made towards an intermediate solution selected at random from among a subset of top-ranked solutions (Algorithm 5.5);
• – Evolutionary PR: a greedy randomized adaptive forward PR is performed at each iteration. At fixed intervals the elite pool is intensified. In fact, at each EvIterations iteration, the algorithm Evolution is invoked (Algorithm 5.6) that performs path-relinking between each pair of current elite set solutions with the aim of eventually improving the current elite set.

5.4.3.4. Hybridizations of GRASP with path-relinking

Ferone et al. [FER 16] integrated a path-relinking intensification procedure in the hybrid GRASP grasp-h-ev described in section 5.4.3.1. The idea behind this integration was to add memory to GRASP and was first proposed in 1999 by Laguna and Martí [LAG 99]. It was followed by several extensions, improvements and successful applications [CAN 01, FES 06, FES 02a, RIB 12].

In the hybrid GRASP with path-relinking for the FFMSP, path-relinking is applied at each GRASP iteration to pairs (s, ŝ) of solutions, where s is the locally optimal solution obtained by the GRASP local search and ŝ is randomly chosen from a pool with at most MaxElite high-quality solutions. The pseudo-code for the proposed hybrid GRASP with path-relinking is shown in Algorithm 5.7.

The pool of elite solutions E is empty (line 1) initially and, until E is no longer full, the current GRASP locally optimal solution s is inserted in E. As soon as the pool becomes full (|| = MaxElite), through the Choose-PR-Strategy procedure, the desired strategy for implementing path-relinking is chosen s and solution ŝ are randomly chosen from . The best solution found along the relinking trajectory is returned and considered as a candidate to be inserted into the pool. The AddToElite procedure evaluates its insertion into . If is better than the best elite solution, then replaces the worst elite solution. If the candidate is better than the worst elite solution, but not better than the best, it replaces the worst if it is sufficiently different from all elite solutions.

Path-relinking is also applied as post-optimization phase (lines 27–34): at the end of all GRASP iterations, for each different pair of solutions s′, s″ ∈ , if s′ and s″ are sufficiently different, path-relinking is performed between s′ and s″ by using the same strategy as the intensification phase.

With the same test instances described in section 5.4.3.2, Ferone et al. comprehensively analyzed of the computational experiments they conducted with the following hybrid GRASPs:

• – grasp-h-ev, the hybrid GRASP that integrates Mousavi et al.’s evaluation function into the local search;
• – grasp-h-ev_f, the hybrid GRASP approach that adds forward path-relinking to grasp-h-ev;
• – grasp-h-ev_b, the hybrid GRASP that adds backward path-relinking to grasp-h-ev;
• – grasp-h-ev_m, the hybrid GRASP approach that adds Mixed path-relinking to grasp-h-ev;
• – grasp-h-ev_grapr, the hybrid GRASP that adds greedy randomized adaptive forward path-relinking to grasp-h-ev;
• – grasp-h-ev_ev_pr, the hybrid GRASP that adds evolutionary path-relinking to grasp-h-ev.

For the best values to be assigned to several involved parameters, the authors proposed the following settings:

• – setting the maximum number MaxElite of elite solutions to 50;
• – inserting a candidate solution in the elite set . If is better than the best elite set solution or is better than the worst elite set solution but not better than the best and its Hamming distance to at least half of the solutions in the elite set is at least 0.75 m, solution replaces the worst solution in the elite set;
• – in the post-optimization phase, path-relinking is performed between s' and s'' if their Hamming distance is at least 0.75 m.

In terms of average objective function values and standard deviations, Ferone et al. concluded that grasp-h-ev_ev_pr finds slightly better quality solutions compared to the other variants when running for the same number of iterations, while grasp-h-ev_b finds better quality solutions within a fixed running time. To validate the good behavior of the backward strategy, in Figures 5.4 and 5.5, the empirical distributions of the time-to-target-solution-value random variable (TTT-plots) are plot, involving algorithms grasp-h-ev, grasp-h-ev_b and grasp-h-ev_ev_pr without performing path-relinking as post-optimization phase. The plots show that, given any fixed amount of computing time, grasp-h-ev_b has a higher probability than the other algorithms of finding a good quality target solution.

5.4.3.5. Ant colony optimization algorithms

ACO algorithms [DOR 04] are metaheuristics inspired by ant colonies and their shortest path-finding behavior. In 2014, Blum and Festa [BLU 14c] proposed a hybrid between ACO and a mathematical programming solver for the FFMSP. To describe this approach, the following additional notations are needed.

Given any valid solution s to the FFMSP (i.e. any s of length m over Σ is a valid solution) and a threshold value 0 ≤ t ≤ m, let P ^s ⊆ Ω be the set defined as follows:

The FFMSP can be equivalently stated as the problem that consists of finding a sequence s^* of length m over Σ such that P ^s* is of maximum size. In other words, the objective function can be equivalently evaluated as follows:

[5.22]

Moreover, for any given solution s set Q^s is defined as the set consisting of all sequences s′ ∈ Ω that have a Hamming distance at least t with respect to s. Formally, the following holds:

Note that where |P ^s| < n, set Q^s also contains the sequence ŝ ∈ Ω P ^s that has, among all sequences in Ω P ^s, the largest Hamming distance with respect to s. To better handle the drawback related to the large plateaus of objective function, the authors proposed slightly modifying the comparison criterion between solutions. Solution s is considered better than solution s (s >_lex s ) if and only if the following conditions hold in lexicographical order:

In other words, the comparison between s and s′ is done by considering first the corresponding objective function values and then, as a second criterion, the sum of the Hamming distances of the two solutions from the respective sets Q⁸ and Q^8′ . It is intuitive to assume that the solution for which this sum is greater is somehow closer to a solution with a higher objective function value.

The hybrid ACO (Algorithm 5.9) consists of two phases. After setting the incumbent solution (the best solution found so far) to the empty solution, the first phase (lines 4–12) accomplishes the ACO approach. After this first phase, the algorithm possibly applies a second phase in which hybridization with a mathematical programming solver takes place (lines 13–15). The ACO-phase stops as soon as either a fixed running time limit (tlim_ACO) has been reached or the number of consecutive unsuccessful iterations (with no improvement of the incumbent solution) has reached a fixed maximum number of iterations (runlim_ACO).

The ACO phase is pseudo-coded in Algorithm 5.10. The pheromone model used consists of a pheromone value τ_i,cj for each combination of a position i = 1, … , m in a solution sequence and a letter c_j ∈ Σ. Moreover, a greedy value, η_i,cj, to each of these combinations is assigned which measures the desirability in reverse proportion letter c_j to position i. Intuitively, value η_i,cj should be of assigning to the number of occurrences of letter, c_j, at position i in the |Ω| = n input sequences. Formally,

The incumbent solution, s^bs, is input as the function which sets all pheromone values of to 0.5. Then, it proceeds in iterations stopping as soon as the convergence factor value cf is greater than or equal to 0.99. At each iteration of the while-loop (lines 4–16), n_a = 10 solutions are constructed in the ConstructSolution() the function on basis of pheromone and greedy information. Starting from each of these solutions, a local search procedure (LocalSearch()) is applied producing a local optimal solution s^ib to which path-relinking is applied. Solution s^ib is also referred to as the iteration-best solution. Path-relinking is applied in the PathRelinking(s^ib, s^bs) function. Therefore, s^ib serves as the initial solution and the best-so-far solution s^bs serves as the guiding solution. After updating the best-so-far solution and the so-called restart-best solution, which is the best solution found so far during the current application of RunACO() (if necessary) the pheromone update is performed in function ApplyPheromoneUpdate(cf, ,s^ib,s^rb). At the end of each iteration, the new convergence factor value cf is computed in function ComputeConvergenceFactor().

ConstructSolution(T) is the function that in line 7 constructs a solution s on the basis of pheromone and greedy information. It proceeds in m iteration, and at each iteration it chooses the character to be inserted in the i^th position of s. For each letter c_j ∈ Σ, a probability p_i,cj position i will be chosen is calculated as follows:

[5.23]

Then, value z is chosen uniformly at random from [0.5, 1.0]. where z ≤ d_rate, the letter c ∈ Σ with the largest probability value is chosen for position i. Otherwise, a letter c ∈ Σ is chosen randomly with respect to the probability values. d_rate is a manually chosen parameter of the algorithm set to 0.8.

The local search and path-relinking procedures are those proposed by Ferone et al. [FER 13b] with solution s^ib playing the role of initial solution and solution s^bs that of the guiding solution.

The algorithm works with the following upper and lower bounds for them pheromone values: τ_max = 0.999 and τ_min = 0.001. Where pheromone values surpasses one of these limits, the value is set to the corresponding limit. This has the effect that complete convergence of the algorithm is avoided. Solutions s^ib and s^rb are used to update the pheromone values. The weight of each solution for the pheromone update is determined as a function of the convergence factor cf and the pheromone values τ_i,cj are updated as follows:

[5.24]

where

[5.25]

Function Δ(s, c_j) evaluates to 1 when character c_j is to be found at position i of solution s; otherwise it is given the value 0. Moreover, solution s^ib has weight κ_ib, while the weight of solution s^rb is κ_rb and it is required that κ_ib + κ_rb = 1. The weights that the authors have chosen are the standard ones shown in Table 5.1.

Finally, ComputeConvergenceFactor() function computes the value of the convergence factor as follows:

This implies that at the start of function RunACO(s^bs), cf has a value of zero. When all pheromone values are either at τ_min or at τ_max, cf has a value of one. In general, cf moves in [0, 1].

This hybrid ACO (tlim_ACO = 60s, tlim_CPLEX = 90s, runlim_ACO = 10) has been tested against the same set of benchmarks originally introduced in [FER 13b] and compared with a pure ACO (tlim_ACO = 90s, tlim_CPLEX = 0s, runlim_ACO = very large integer) and the GRASP hybridized with path-relinking in [FER 13b]. The mathematical model of the problem was solved with IBM ILOG CPLEX V12.1 and the same version of CPLEX was used within the hybrid ACO approach. The (total) computation time limit for each run was set to 90 CPU seconds. The three algorithms are referred to as ACO, HyACO and GRASP+PR, and the results are summarized in Table 5.2. Note that for each combination of n, m and t, the given values are averages of the results of 100 problems. In each case, the best results are shown with a gray background. For the analysis of the results, since the performance of the algorithms significantly changes from one case to another, the three cases resulting from t ∈ {0.75 m, 0.8 m, 0.85 m} are treated separately.

Looking at the results, it is evident that the most interesting case study is represented by those instances characterized by t = 0.85 m. In fact, it turns out that GRASP+PR, as proposed in [FER 13b], is not very effective and that HyACO consistently outperforms the pure ACO approach, which consistently outperforms CPLEX.