Solving the non-unicost set covering problem by using cuckoo search and black hole optimization

Abstract

The set covering problem is a classical optimization benchmark that finds application in several real-world domains, particularly in line balancing production, crew scheduling, and service installation. The problem consists in finding a subset of columns in a zero-one matrix such that they cover all the rows of the matrix at a minimum cost. In this paper, we present two new approaches for efficiently solving this problem, the first one based on cuckoo search and the second one on black hole optimization. Both are relatively modern bio-inspired metaheuristics that have attracted much attention due to their rapid convergence, easy implementation, and encouraging obtained results. We integrate to the core of both metaheuristics an effective pre-processing phase as well as multiple transfer functions and discretization methods. Pre-processing is employed for filtering the values from domains leading to infeasible solutions, while transfers function and discretization methods are used for efficiently handling the binary nature of the problem. We illustrate interesting experimental results where the two proposed approaches are able to obtain various global optimums for a set of well-known set covering problem instances, outperforming also several recently reported techniques.

1 Introduction

The set covering problem (SCP) is one of the well-known Karp’s 21 NP-complete problems. The goal of such a problem is to find a subset of columns in a zero-one matrix such that they cover all the rows of the matrix at a minimum cost. The non-unicost SCP is a slight variant of this problem where the cost of columns are different. Several applications of the non-unicost SCP can be seen in the real world, particularly related to line balancing production (Salveson 1955), crew scheduling (Baker et al. 1979; Bartholdi 1981; Rubin 1973), service installation (Toregas et al. 1971; Walker 1974), databases (Munagala et al. 2004), and Boolean expressions (Breuer 1970). The literature reports various algorithms to solve this problem which range from classical exact methods (Balas 1997; Beasley 1987; Yelbay et al. 2014; Avis 1980; Rushmeier and Nemhauser 1993) to very recent bio-inspired metaheuristics (Crawford et al. 2014; Karaboga 2005).

In this paper, we present two new approaches for efficiently solving different instances of the SCP: cuckoo search and black hole optimization. Both are relatively recent bio-inspired metaheuristics that have attracted much attention during the last years, both being succesfully used in different application domain, such as data clustering, image processing, data mining, and computervision (Kumar et al. 2015; Yang and Deb 2014). Important features that share these metaheuristics are the rapid convergence and the notably easy implementation in order to model and solve the problem at hand. We integrate to the core of both metaheuristics an effective pre-processing phase as well as multiple transfer functions and discretization methods. Pre-processing is used for eliminating those values that do not lead to any feasible solutions. The goal is to alleviate the work of the metaheuristic. Transfers function are used to map the real values generated by the movement operator of both metaheuristics to a [0, 1] real interval. This interval is then used by the discretization method to generate a binary value according to the nature of the SCP. We perform a large set of experiments involving 8 transfer functions and 3 discretization methods in order to select the best performing combination of them. Interesting experimental results are obtained, where the two proposed approaches are able to obtain various global optimums for a set of 65 well-known SCP instances, outperforming also several recently reported techniques.

The remainder of this paper is organized as follows: The related work is introduced in the next section. A brief description of the SCP and pre-processing phases are detailed in Sect. 3. Sect. 4 presents the metaheuristics employed in this work, followed by their corresponding binary representations. Sects. 6 and 7 illustrate the repair of infeasible solutions and the experimental results, respectively. Finally, we conclude and suggest some lines of future research.

2 Related work

The SCP has widely been explored in the optimization and mathematical programming sphere. Preliminary works relied on the proper use of branch-and-bound and branch-and-cut algorithms (Balas 1997) and (Beasley 1987), which are exact methods commonly unable to tackle large instances of the SCP. Greedy algorithms have also been proposed, however their deterministic nature hinders the generation of high quality solutions (Chvatal 1979). This problem may be improved by the incorporation of memory and random components as detailed in Lan and DePuy (2006). As noted in Ceria et al. (1998) and Caprara et al. (1999) Lagrangian relaxation-based heuristics are in general much more effective. A more detailed description of efficient exact methods and heuristics devoted to SCPs can be found in Caprara et al. (2000).

It is well-known that exact methods are in general unable to tackle large instances of NP-complete problems, consequently much research work has been devoted to the study of efficient metaheuristics to solve hard SCP instances in a bounded amount of time. For instance ant colony optimization (Crawford et al. 2011, 2013; Valenzuela et al. 2014), tabu search (Caserta 2007), simulated annealing (Brusco et al. 1999), and genetic algorithms (Yelbay et al. 2014) have extensively been proposed to tackle the classic SCP. More recent metaheuristics for solving this problem can also be found in the literature, such as firefly optimization (Crawford et al. 2014), cat swarm optimization (Crawford et al. 2015b, d), shuffled frog leaping (Crawford et al. 2015a, c), artificial bee colony (Karaboga 2005), electromagnetism-like (Birbil and Fang 2003), among others.

As top-level general search strategies, metaheuristics have also largely been applied to solve SCPs in recent years.

3 Problem description

In this section we provide the formal definition of the SCP (Gass and Fu 2013). Let A be an n-row and m-column incidence matrix, where $a_{i,j}$ denotes the value taken by position (i, j) of A, being $i = 1,\ldots,n$ and $j = 1,\ldots,m$. Let us note that a row i is covered by column j if $a_{ij} = 1$. Every column j hold a non-negative cost $c_{j}$, for the non-unicost SCP, $c_{j}$ vary for each column. The goal is to find a minimun cost such that each row i is covered by at least one column j. The corresponding mathematical is stated in the following:

$$\begin{aligned}&Minimize\,\,z = \sum ^{m}_{j=1} c_{j}x_{j} \end{aligned}$$

(1)

$$\begin{aligned}&\hbox {subject to} \nonumber \\&\sum ^{m}_{j=1} a_{ij}x_{j} \ge 1,\quad \forall i = 1,\ldots,n \end{aligned}$$

(2)

$$\begin{aligned}&x_{j} \in \{0,1\},\quad\forall j = 1,\ldots,m \end{aligned}$$

(3)

The idea is to minimize the summation of the costs of the columns, where $x_{j} = 1$ if column j belongs to the solution and $x_{j} = 0$ otherwise. The constraints of the SCP guarantee that every row i is covered by at least one column j.

For clarifying the problem, we present an example of a unicost SCP, therefore the cost vector $c_{j} = 1, \forall ~j = 1,\ldots,m$.

There are six cities ($city_{1}$ to $city_{6}$) in region R. The region must determine where to build fire stations. The region wants to build the minimum number of fire stations and ensure that at least one fire station is near 15 min of each city. The times (in minutes) required to drive between cities are illustrated in Table 1.

Table 1 Times required to drive between cities

To formulate the integer-programming model, we consider the following decision variable:

$$x_{j} = \left\{ \begin{array}{ll} 1, &\quad \text {if\;a\;fire\;station\;is\;built\;in}\,city_{i} \\ 0, &\quad \text {otherwise} \end{array} \right.$$

(4)

Objective function is given by minimum sum of the decision variables activated ($x_{j} = 1$).

$$\begin{aligned} Minimize\,z = \displaystyle \sum ^{6}_{j=1} x_{j} \end{aligned}$$

(5)

Constraints: A fire station within 15 min of each city. This can be seen in the following summary:

$$\begin{aligned} \begin{array}{cccc} city_{1} & \quad city_{1}, city_{2} & \quad \Rightarrow & \quad x_{1} + x_{2} \ge 1 \\ city_{2} & \quad city_{1}, city_{2}, city_{6} & \quad \Rightarrow & \quad x_{1} + x_{2} + x_{6} \ge 1 \\ city_{3} & \quad city_{3}, city_{4} & \quad \Rightarrow & \quad x_{3} + x_{4} \ge 1 \\ city_{4} & \quad city_{3}, city_{4}, city_{5} & \quad \Rightarrow & \quad x_{3} + x_{4} + x_{5} \ge 1 \\ city_{5} & \quad city_{4}, city_{5}, city_{6} & \quad \Rightarrow & \quad x_{4} + x_{5} + x_{6} \ge 1 \\ city_{6} & \quad city_{2}, city_{5}, city_{6} & \quad \Rightarrow & \quad x_{2} + x_{5} + x_{6} \ge 1 \\ \end{array} \end{aligned}$$

Thus, the integer-programming model is as follows:

$$\begin{aligned} \begin{array}{l} Minimize\,z = x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6}\\ \text {subject\,to:} \\ x_{1} + x_{2} \ge 1 \\ x_{1} + x_{2} + x_{6} \ge 1 \\ x_{3} + x_{4} \ge 1 \\ x_{3} + x_{4} + x_{5} \ge 1 \\ x_{4} + x_{5} + x_{6} \ge 1 \\ x_{2} + x_{5} + x_{6} \ge 1 \\ x_{j} \in \{0,1\}, \forall ~j = 1,\ldots,6 \end{array} \end{aligned}$$

(6)

Optimal solution is given by $(z,x_{1},x_{2},x_{3},x_{4},x_{5},x_{6})=(2,0,1,0,1,0,0)$ and it represented by the binary vector in Fig. 1: where each value $x_{j}$ is a component of the solution.

Fig. 1

Representation of binary unicost solution

The optimal solution represents the cities in which should be built the fire station (minimum), such that the distance between one city and one fire station is not greater than 15 min.

To transform this example in a non-unicost problem, is necessary to differentiate the installation cost of each fire station (cost vector $c_{j}$). In that case, the objective function is given by:

$$\begin{aligned} Minimize\;z = \displaystyle \sum ^{6}_{j=1} c_{j}x_{j} \end{aligned}$$

(7)

where $c_{j}$ is the cost vector associated to each $x_{j},~\forall ~j = 1,\ldots,6$. If we consider the cost for each fire station is started in Table 2.

Table 2 Costs required to build the fire stations in each city

The n-tuple $(z,x_{1},x_{2},x_{3},x_{4},x_{5},x_{6})=(120,1,0,1,0,0,1)$ is the vector that describes the new optimal solution and it depicted in Fig. 2.

Fig. 2

Representation of binary non-unicost solution

Finally, for applying correct way the proposed algorithms, we define $x_{i}$-binary vector-as the solution i of SCP and $x^{j}$ as a component part of solution, whose values can be 1, if this component is part of solution or 0 it is not.

4 Bio-inspired approaches

The bio-inspired algorithms, have been placed among the best algorithms for solving optimization problems. In this paper, we solve the SCP by using two bio-inspired approaches: cuckoo search and black hole optimization.

4.1 Cuckoo search algorithm

Cuckoo search algorithm (Fouladgar and Lotfi 2015; Yang and Deb 2009) is inspired from the obligate brood parasitism of some cuckoo species by laying their eggs in the nests of other bird species. For simplicity in describing the cuckoo search, here we use the following three idealized rules:

• 1. Each cuckoo lays one egg at a time and dumps it in a randomly chosen nest.

• 2. The best nests with high-quality eggs will be carried over to the next generations.

• 3. The number of available host nests is fixed, and the egg laid by a cuckoo is discovered by the host bird with a probability $p_{a} \in [0, 1]$. In this case, the host bird can either get rid of the egg or simply abandon the nest and build a completely new nest.

A new solution is generated by using Lévy flight (Yang and Deb 2009) and it is given via Eqs. 8 and 9.

$$\begin{aligned}&x^{d}_{i}(t + 1) = x^{d}_{i}(t) + \alpha \oplus \text {L}\acute{\hbox {e}}\text {vy}(\beta ) \nonumber \\&\quad \forall i \in \{1,\ldots,n\} \wedge ~ \forall d \in \{1,\ldots,m\} \end{aligned}$$

(8)

where $x^{d}_{i}(t)$ is the component d of a solution i at iteration t. Analogously, $x^{d}_{i}(t + 1)$ is the component d of a solution i at iteration $t + 1$. $\alpha \ge 0$ is the step size, which is associated to the range of values that the problem needs (scale value), being determined by upper and lower bounds.

$$\begin{aligned} \text {L}\acute{\hbox {e}}\text {vy} \sim u = t^{-\beta },~(1< \beta < 3) \end{aligned}$$

(9)

The Lévy flight represents a random trajectory and it is the length of the step obtained by means of a Lévy distribution which has infinite mean and variance. In this case, the consecutive steps of a cuckoo form a process of random walk that follows a distribution of powers law with double tail step length (Fouladgar and Lotfi 2015).

Algorithm 1 depicts the proposed procedure. At the beginning in Line 1, input data from SCP is processed and loaded. Then, at Lines 3–8, an initial population of n nests is randomly generated as a vector of m binary values that corresponds to one nest or one potential solution (Line 5). For each nest (potential solution), the fitness value is calculated by evaluating the objective function z (Line 7).

For generating new solutions, the while loop manages the actions which are self-explanatory, at Lines 11–32. As previously mentioned, the SCP is a minimization problem. This evaluation is handled in comparison presented at Line 13. If the new min value is lower than min global, the min global is changed by the new min value and the best solution is stored in $\hat{x}$.

Next for loop statement (Lines 17–23) allows to select worst solutions according to random a value $rand \in [0,1]$ greater than $p_{a}$.

Finally, the last for loop statement (Lines 24–31) generates new solutions according to Eq. (8), for each dimension j. This value belongs to a real domain and it must be brought to a binary domain, thus we used a T function that transform the real value to a binary one. In this paper, we test different binarization approaches described in Sect. 5.

4.2 Black hole optimization

Black hole optimization is a population-based method inspired on the black hole phenomenon (Hatamlou 2013; Kumar et al. 2015). A black hole is a region of space that has so much mass concentrated in it that there is no way for a nearby object to escape its gravitational pull. Anything falling into a black hole, including light, cannot escape.

Similar to other population-based algorithms, the black hole algorithm starts with an initial population of potential solutions to an optimization problem and an objective function that is calculated for them. At each iteration of the black hole algorithm, the best candidate is selected to be the black hole, which then starts pulling other candidates around it, called stars. If a star gets too close to the black hole, it will be swallowed and it is gone forever. In such a case, a new star (potential solution) is randomly generated and placed in the search space and starts a new search.

The black hole has the ability to absorb the stars that surround it. After initializing the black hole and stars, the black hole begins by absorbing the stars around it and all the stars start moving towards the black hole. The absorption of stars by the black hole is formulated as follows:

$$\begin{aligned} x^{d}_{i}(t + 1) = x^{d}_{i}(t) + r[x^{d}_{BH} - x^{d}_{i}(t)],~ \forall ~i \in \{1,\ldots,N\} \end{aligned}$$

(10)

where $x^{d}_{i}(t)$ and $x^{d}_{i}(t + 1)$ are the components of a solution i at iterations t and $(t + 1)$, respectively. $x^{d}_{BH}$ is the component of best solution (black hole) in the search space. r is a random number in the interval [0, 1]. N is the number of stars (potential solutions).

While moving towards the black hole, a star may reach a location with lower cost than the black hole. In such a case, the black hole moves to the location of that star and vice versa. Then the algorithm will continue with the black hole in the new location and then stars start moving towards this new location.

In addition, there is the probability of crossing the event horizon during moving stars towards the black hole. Every star (or potential solution) that crosses the event horizon of the black hole will be swallowed by the black hole. Every time a candidate is sucked in by the black hole, another potential solution (star) is born and distributed randomly in the search space and starts a new search. This is done to keep the number of potential solutions constant. The next iteration takes place after all the stars have been moved.

The radius of the event horizon in the black hole algorithm is calculated using the following equation:

$$\begin{aligned} R = \dfrac{f_{BH}}{\sum ^{N}_{i=1}f_{i}} \end{aligned}$$

(11)

where $f_{BH}$ is the fitness value of the black hole and $f_{i}$ is the fitness value of the i-th star. N is the number of stars (potential solutions).

When the distance between a star and the black hole (best candidate) is less than R, that candidate is collapsed and a new star is created and distributed randomly in the search space. Based on the above description the main steps in the black hole algorithm are detailed in Algorithm 2.

Similar to the Cuckoo Search Algorithm, the Black Hole optimization begins with the loading and processing phases. Then, at Lines 3–8, an initial population of n stars is randomly generated as a vector of m binary values that corresponds to one star or potential solution (Line 5). For each star, the fitness value is calculated by evaluating the objective function z (Line 7).

Then, while a termination criterion (a maximum number of iterations or a sufficiently good solution was not reached) is met, each fitness of a potential solution is evaluated (Lines 11–34). As previously mentioned, the SCP is a minimization problem. This evaluation is handled in comparison presented at Line 13. If the new min value is less than min global, the min global is changed by the new min value and the best solution is stored in $\hat{x}$ (black hole).

If a star crosses the event horizon of the black hole (calculated via Eq. 11), replace it with a new star in a random location in the search space. This process is described in the for loop statement at Lines 17–25.

Finally, the last for loop statement (Lines 26–33) generates new solutions according to Eq. (10), for each dimension d. As in the Cuckoo Search algorithm, this value belongs to real domain and it must be brought to a binary domain, thus a T function is used again to transform the real value in a binary one.

5 Binary approaches

The set covering is a problem whose domain is limited to binary values, namely, $x_{i}^{d} \in \{0,1\},~\forall ~j \in \{1, \ldots, m\}$. Due to this reason, we use a binary representation for the SCP solution as showed in Fig. 3, where:

$$\begin{aligned} x^{d}_{i} = \left\{ \begin{array}{ll} 1, \quad \text {if\;the\;dimension\;} d \text {\;belongs\;to\;the\;solution} \\ 0, \quad \text {otherwise} \end{array} \right. \end{aligned}$$

In this work, we use the standard forms in both algorithms; for the cuckoo search algorithm (Pereira et al. 2014), each nest holds only one egg and represents a potential solution and for the black hole optimization (Nemati et al. 2013), each star represent a potential solution.

Fig. 3

Binary solution representation

However, the approximate methods used for solving the SCP are designed to solve problems with real domains. This task is resolved by transforming domains, by applying binarization strategies, which are responsible for forcing elements to move in a binary space. The binarization strategy is composed of a transfer function and a discretization method. In this work, we tested 32 different binarization strategies.

We tested eight different functions (see Table 3), separated into two families (Mirjalili and Lewis 2013): $\mathcal {S}$-Shape and $\mathcal {V}$-Shape.

Table 3 Transfer functions

Once a transfer function is applied, the input real number is mapped to a real number belonging to a [0, 1] interval. Then, a discretization method is required to produce a binary value from the real one. For achieving this, we test four different methods:

• 1. Standard If condition is satisfied, standard method return 1, otherwise, return 0.

  $$\begin{aligned} x^{d}_{i}(t + 1) = \left\{ \begin{array}{ll} 1, \quad \text {if}\,rand\; \le T(x^{d}_{i}(t + 1)) \\ 0, \quad \text {otherwise} \end{array} \right. \end{aligned}$$

  (12)

• 2. Complement If condition is satisfied, standard method return the complement value.

  $$x^{d}_{i}(t + 1) = \left\{ \begin{array}{ll} \overline{x^{d}_{i}(t + 1)^\prime},& \text {if}\;rand \le T(x^{d}_{i}(t + 1)) \\ 0, & \text {otherwise} \end{array} \right.$$

  (13)

• 3. Static probability A probability is generated and it is evaluated with a transfer function.

  $$\begin{aligned} x^{d}_{i}(t + 1) = \left\{ \begin{array}{ll} 0, & \text {if}\;T(x^{d}_{i}(t + 1)) \le \alpha \\ x^{d}_{i}(t + 1){^\prime},\quad \text {if}\;\alpha & T(x^{d}_{i}(t + 1)) \le \frac{1}{2}(1 + \alpha )\\ 1, &\text {if}\;T(x^{d}_{i}(t + 1)) \ge \frac{1}{2}(1 + \alpha ) \end{array} \right. \end{aligned}$$

  (14)

• 4. Elitist Discretization method Elitist Roulette, also known as Monte Carlo, is to select randomly among the best individuals of the population, with a probability proportional to its fitness.

  $$\begin{aligned} x^{d}_{i}(t + 1) = \left\{ \begin{array}{ll} x^{d}_{i}(t + 1)^\prime, &\text {if}\;rand \le T(x^{d}_{i}(t + 1)) \\ 0, &\text {otherwise} \end{array} \right. \end{aligned}$$

  (15)

6 Heuristic feasibility operator

Bio-inspired algorithms may generate infeasible solutions. In the SCP, an infeasible solutions corresponding to those solutions that uncovered rows, clearly violates a subset of constraints. Due to this problem, we employed an additional heuristic operator that achieves the generation of feasible solutions, and additionally eliminates column redundancy.

For making all feasible solutions, we calculate a percentage based on the cost of column j over the sum of all the constraint matrix rows covered by a column j, as shown in Eq. (16).

$$\begin{aligned} \frac{cost(column_{j})}{coveredRows(column_{j})} \end{aligned}$$

(16)

A unfeasible solution is repaired by covering the columns of the solution that had the lower percentage. Then, the heuristic applies a local optimization step for removing the column redundancy. If a column is deleted and the feasibility of the solution is not affected, then the column is redundant.

Algorithm 3 starts with the initialization of variables from instance in Lines 1–5, The recognition of the rows that are not covered are in Lines 6 and 7. Between the statements 8 and 18 is “greedy” heuristic. On the one hand, between the instructions 8 and 12, the columns with lower ratio are added to the solution. On the other hand, between lines 13 and 18, the redundant columns with higher costs are deleted while the solution is feasible.

7 Experimental results

We have performed an experimental evaluation of the proposed approaches on a set of 65 different well-known instances, organized in 11 sets from the Beasley’s OR-library.¹ Table 4 describes instance set, number of rows or constraints (m), number of columns or variables (n), range of costs, density (percentage of non-zeroes in the matrix) and if the optimal solution is known or unknown.

Table 4 SCP instances from the Beasley’s OR-Library

In order to reduce the instance size of SCP, we have used a pre-processed instances set. Different pre-processing methods have particularly been proposed for the SCP (Fisher and Kedia 1990). We employ two of them, which have been proved to be the most effective ones:

• Column Domination The non-unicost SCP holds different column costs, then once a set of rows $I_{j}$ is covered by another column $j^\prime$ and $c_{j^\prime} < c_{j}$, we say that column j is dominated by $j^\prime$, then column j is removed from the solution.

• Column Inclusion If a row is covered by only one column after the above domination, means that there is no better column to cover those rows, consequently this column must be included in optimal solution.

The results are evaluated using the relative percentage deviation (RPD). RPD value quantifies the deviation of the objective value Z from $Z_{opt}$ that in our case is the best known value for each instance ($Z_{opt}$ in Table 4) and it is calculated as follows:

$$\begin{aligned} RPD = \left( \dfrac{Z - Z_{opt}}{Z_{opt}} \right) \times 100 \end{aligned}$$

(17)

The minimum (Min), maximum (Max) and average (Avg) of the solutions obtained were achieved running 30 executions over each one of the 65 SCP test instances. To calculate RPD value, we used $Z = Z_{min}$. We test all the combinations of transfer functions and discretization methods over all these instances. Binarization strategies that achieved the best results for the black hole algorithm and cuckoo search are stated in Table 5:

Table 5 Binarization strategies for cuckoo search and black hole optimization

Parameters tuning is known to be a complex task, being itself recognized as an optimization problem. To select these parameters, we performed a sampling test. In this pre-evaluation, both algorithms were executed 10 times, each one for the different population sizes: 1000, 100, 50, and 30 initial solutions and for the different number of generations; keeping all other parameters constant. To this end, we can see that when the population size (n) decreased and the number of generations (T) increased, the fitness value converges more quickly towards a minimum value. Table 6 show the parameter tuning achieved.

Table 6 Parameter tuning for black hole and cuckoo search algorithms

The implementation of both algorithms has been done in $Java^{TM}$ and experiments have been launched on a 3.0 GHz Quad Core with 8 GB RAM machine running MS Windows 7 Ultimate. We compare our binary cuckoo search (BCS) and binary black hole (BBH) algorithms with the global optimum—or best known—($Z_{opt}$) as well as with very recent approaches for solving SCPs based on modern bio-inspired metaheuristics, namely binary cat swarm optimization (BCSO) (Crawford et al. 2015b), binary firefly optimization (BFO) (Crawford et al. 2014), binary shuffled frog leaping algorithm (BSFLA) (Crawford et al. 2015c), binary artificial bee colony (BABC) (Cuesta et al. 2014) and binary electromagnetism-like algorithm (BELA) (Soto et al. 2015c). In order to compare and understand the results, we highlighted in bold the best result for each instance.

Table 7 illustrates the results obtained for instances from groups 4 and 5. Regarding instance set 4, BCSO, BSFLA, BELA and BABC are unable to achieve optimal values and BFO reaches only two. BCS and BBH exhibit the best performance for this data set reaching five and eight global optimums, respectively. Now considering instance set 5, once again BCSO and BELA are unable to optimally solve any instance. BABC is capable to find two optimal values, while BFO reach three and BSFLA four. Once again BCS and BBH prove to be better methods, reaching both eight optimal values. In terms of solving time (in ms) in 4 and 5 groups, we compare BCS and BBH and we can observe that a big difference can not be seen. In some instances BBH is faster than BCS and in others is the opposite.

Table 7 Computational results for instance set of groups 4 and 5

Table 8 Computational results for instances set of groups 6, A, B and C

Table 8 depicts the results for the instances set 6, A, B and C. Firstly, for set instance 6, BCS and BBH behave similar, three and four optimal values, respectively. In contrast, previous approaches reach less than 10% in average of optimal values. For the group A, BBH continues exhibiting a good performance compared to its competitors, achieving 3 of 5 optimal values. The best results for the proposed approaches can be seen when solving the instances set B, where both algorithms are capable to find the 100% of global optimums. Finally, for the C group, BBH again exhibits an efficient performance reaching 3 of 5 optimal values.

Now, comparing the results in terms of solving time, we can see that for smaller instances -group 6- BCS converges faster than BBH, but for bigger instances of groups A, B and C, BBH finds the best solution more fast than BCS.

Table 9 Computational results for instances set of groups D, E, F and G

Table 10 Computational results for intances of group H

Table 9 describes the results for groups D, E, F and G. For the D and E group. BCS and BBH perform similar again, finding in both cases between 60 and 40% of the optimum values. For the F and G groups, three $RPD=0$ are reached by the proposed algorithms. Previous approaches fail in general to find optimum values as the instance set becomes harder. Only BSFLA and BABC achieve one optimum for the instances belonging to sets F and G, while BBH and BCS reach three. Finally, for the most hard instance set (see Table 10), namely H, we observe that the RPD obtained by the proposed approaches outperform by far the performance of competitors, remaining very close to optimal values. Now, considering the time required to find a best solution, we can observe that BCS is dramatically more efficient than BBH, needing a less time for all instances of group A.

Table 11 Summary of reached optimal ($RPD = 0$)

Fig. 4

Summary of reached optimal ($RPD = 0$)

Table 11 and Fig. 4 summarizes the performance of compared approaches. BBH and BCS are the best performing approaches reaching 35 global optimums, outperforming by far its competitors, BSFLA taking the third place with 14 global optimums, followed by BSFLA, BFO, BCSO, and BELA with no global optimum reached.

7.1 Binary cuckoo search versus binary black hole

In this section we contrast the proposed approaches in order to determine which one performs better. To this end we compare convergence and we detailedly analyze the 30 executions performed for each instance through the Kolmogorov–Smirnov–Lilliefors (Lilliefors 1967) and Wilcoxon’s signed rank (Mann and Whitney 1947) statistical tests.

For instance group 4, 5, 6 and A, the convergence is achieved between 25 and 50 ms, BCS showing a small superiority. For more hard instance sets, such as B, C, and D, the solving time needed slightly increases, ranging from 50 to 100 ms. Finally, for E, F, G and H instance groups, the convergence is achieved between 700 and 1000 ms, showing that although these instances are known to be hard, both approaches are able to find a good solution in a reasonable amount of time. We have also observed that the optimization process applied after the repairing function greatly helps the convergence of BBH and BCS, being as well an important step to improve the cost value of each instance. The experimental results also exhibit the robustness of the approaches as the fitness average for each instance remains very near to the optimum global. However, as the results in terms of solving time obtained are not conclusive to assert which approach performs better, we have also performed a statistical analysis to the 30 executions of each instance.

We firtly employ the Kolmogorov-Smirnov-Lilliefors test to determine the independence of samples and then we statistically compare them through the Wilcoxon’s signed rank. For both tests, we consider a hypothesis evaluation, which is analyzed assuming a significance level of 0.05, i.e., smaller values that 0.05 determine that the corresponding hypothesis cannot be assumed. Both test were conducted using GNU Octave ².

The first test allows us to analyze the independence of samples by determining whether the fitness values obtained from the 30 executions come from a normal distribution or they are independent. To proceed we consider two hypothesis: $H_{0}$ and $H_{1}$. $H_{0}$ states that fitness values follow a normal distribution and $H_{1}$ otherwise. The conducted test has yielded pvalues lower than 0.05, therefore we cannot assume $H_{0}$.

Then, as samples are independent and do not follow a normal distribution, it is not feasible to use the central limit theorem to approximate the distribution of the sample mean as Gaussian. Therefore, we assume the use of a non-parametric test for evaluating the heterogeneity of samples. Under this assumption, we can use the Wilcoxon’s signed rank test for matched pairs. This is a paired test that compare the medians of two distributions. To proceed, we consider again two hypothesis. $H_{0}: \tilde{X}_{BBH} \le \tilde{X}_{BCS}$, where $\tilde{X}$ corresponds to the arithmetic median of fitness values achieved; and $H_{1}: \tilde{X}_{BCS} < \tilde{X}_{BBH}$.

Tables 12, 13, 14 and 15 compare the algorithms for all tested instances via the Wilcoxon’s signed rank test. As the significance level is also established to 0.05, smaller values that 0.05 defines that $H_{0}$ cannot be assumed. Bold font is used for a winner value of the metaheuristic stated in the column of the table, e.g. for instance 4.1, BCS is better than BHH as its value is lower than 0.05, then $H_{0}$ cannot be assumed.

According to results, p values lower than 0.05 are equivalent for both metaheuristics (24 for each one) illustrating again a very similar performance for all tested instances. However we may note that BHH performs clearly better than BCS for the E group, which is the hardest one (Table 16).

Table 12 Exact p values obtained on instance of groups 4 and 5

Table 13 Exact p values obtained on instance of groups 6, A and B

Table 14 Exact p values obtained on instance of groups C, D and E

Table 15 Exact p values obtained on instance of groups F, G and H

Table 16 Summary of results obtained from the statistical tests

8 Conclusions and future work

In this paper, we have presented new BBH and BCS algorithms for solving SCPs. Both metaheuristics are quite simple to implement and can efficiently be adapted to binary domains by using transfer functions and discretization methods. We have integrated to the core of both metaheuristics an effective pre-processing phase as well as multiple transfer functions and discretization methods. Pre-processing serves as a filtering phase to discard values leading to unfeasible solutions, while transfers function and discretization methods are used for efficiently handling the binary nature of the problem. We have tested 65 non-unicost instances from the Beasley’s OR-Library where several global optimum values were reached by both approaches, remaining very close to optimal values when was not possible to reach them, particularly for the hardest instances. We have also compared both approaches by using statistical tests yielding very similar results in terms of performance.

As future work, we plan to experiment with additional modern metaheuristics and to provide a larger comparison of recent bio-inspired techniques to solve SCPs. The integration of autonomous search to the presented approach would be another direction of research to follow as well, for instance to dynamically select the best binarization strategy during solving according to performance indicators as analogously studied in (Soto et al. 2013, 2015b, d).