# Adaptive Black Hole Algorithm for Solving the Set Covering Problem

Authors: Ricardo Soto; Broderick Crawford; Rodrigo Olivares; Carla Taramasco; Ignacio Figueroa; Álvaro Gómez; Carlos Castro; Fernando Paredes
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

Evolutionary algorithms have been used to solve several optimization problems, showing an efficient performance. Nevertheless, when these algorithms are applied they present the difficulty to decide on the appropriate values of their parameters. Typically, parameters are specified before the algorithm is run and include population size, selection rate, and operator probabilities. This process is known as offline control and is even considered as an optimization problem in itself. On the other hand, parameter settings or control online is a variation of the algorithm original version. The main idea is to vary the parameters so that the algorithm of interest can provide the best convergence rate and thus may achieve the best performance. In this paper, we propose an adaptive black hole algorithm able to dynamically adapt its population according to solving performance. For that, we use autonomous search which appeared as a new technique that enables the problem solver to control and adapt its own parameters and heuristics during solving in order to be more efficient without the knowledge of an expert user. In order to test this approach, we resolve the set covering problem which is a classical optimization benchmark with many industrial applications such as line balancing production, crew scheduling, service installation, and databases, among several others. We illustrate encouraging experimental results, where the proposed approach is able to reach various global optimums for a well-known instance set from Beasley’s OR-Library, while improving various modern metaheuristics.


---

## Body

## 1. Introduction

Nature inspired algorithms are inspired by natural phenomena and behaviours that are met in nature. These algorithms are a subcategory of evolutionary algorithms, which are algorithmic schemes that evolve the solution in each iteration of the algorithm [1]. Evolutionary algorithms use the intelligence of the previous solution for the new one to be generated [2]. In innumerable works, the efficiency of these techniques has been tested. However, it is well known that the performance of metaheuristics depends largely on their correct parameter settings. In fact, finding the appropriate values for the parameters of an algorithm is considered to be a nontrivial task. Previous research has addressed this task that can be classified into two major forms of parameter setting (see Figure 1):  parameter tuning and parameter control. Parameter tuning is known as the process of finding good parameter values before the run of the solver—by using, for instance, training instances—, and then launching the algorithm using these values, which remain static during solving. On the contrary, parameter control launches the algorithm with initial parameter values which are updated during solving time. Now, parameter control is divided into three branches according to the degree of autonomy of the strategies. The control is deterministic when the parameter value is modified by some fixed, predetermined rule using no information from the search. The control is called adaptive, when feedback from the search is employed to determine the variation of a given parameter value, for instance, the population size. Finally, self-adaptive is known as when the parameters are encoded into individuals in order to evolve conjointly with the other variables of the problem. This applies to some metaheuristics; for instance, in evolutionary algorithms the better values of these encoded parameters may lead to better individuals, which in turn have more chances to propagate these good configurations to next generations.Figure 1
Classification of parameter setting.This paper proposes an adaptive approach for parameter control by using autonomous search which is a particular case of adaptive systems that improve their solving performance by modifying and adjusting themselves to the problem at hand, either by adaptation or supervised adaptation [3]. Autonomous Search is applied on the black hole algorithm that is a population-based metaheuristic inspired by the black hole phenomenon. The behaviour of this algorithm is principally controlled by two elements: number of solutions and event horizon. The main idea is to automatically adapt the population according to performance exhibited by the algorithm; this population variation indirectly influences on the event horizon.To evaluate the adaptive approach on the black hole algorithm, we test the set covering problem which is one of the well-known Karp's 21 NP-complete problems. Interesting experimental results are obtained, where the proposed approach is able to obtain various global optimums for a set of 65 well-known set covering problem 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 set covering problem is presented in Section3. Section 4 details the metaheuristic employed in this work, including their adaptive variation, the binary representation, and the repair of unfeasible solutions. Section 5 illustrate the experimental results, and finally, we conclude and suggest some lines of future research in Section 6.


## 2. Related Work

In the evolutionary computing field, many optimization problems have widely been treated by using evolutionary algorithms, such as [4–6] and also [7–9]. In this research line, the parameter setting approach [10] is one of the most studied challenges [11–17]. However, a more reduced work can be observed in the literature when other metaheuristics are involved. For instance, a parameter adaptation study on ant colony optimization is reported in [18], a firefly algorithm for solving the optimal capacitor placement problem is described [19], in [20] a self-adaptive artificial bee colony for constrained numerical optimization is presented, and a modified cuckoo search algorithm for solving engineering problems can be encountered in [21, 22]. Now, considering more similar works, we find a variation of genetic algorithm that adjusts its population size in [23]. The basic idea is to adapt the actual population size depending on the difficulty of the algorithm in its ultimate goal to generate new child chromosomes that outperform their parents. Similarly, [24] presents a version of cuckoo search algorithm that adapts their parameter pa reflecting the probability whether the nest will be abandoned or updated. In both cases, the adaptive approach depends of quality solution. Finally, in [25] we can observe a variation of the artificial bee colony that consists in controlling the perturbation frequency.On the other hand, the set covering problem has widely been explored in the optimization and mathematical programming sphere [26]. First works have used exact techniques, for instance branch-and-bound and branch-and-cut algorithms [27–30]. Greedy algorithms have been proposed as a real alternative for solving the set covering problem; nevertheless their deterministic nature hinders the generation of high quality solutions [31]. Under this line, 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 instances of the set covering problem in an amount of bounded time. For instance, ant colony optimization [32–35], simulated annealing [36], tabu search [37], and genetic algorithms [38] have extensively been proposed to tackle the classic set covering problem. In recent years, research has been driven towards solving this problem by using recent bioinspired algorithms, such as teaching-learning based optimization [39] firefly optimization [40], cat swarm optimization [41], shuffled frog leaping [42], artificial bee colony [43], cuckoo search [44], and black hole algorithm [44], among others.Finally, we can say that an adaptive approach for bioinspired algorithms to solve the set covering problem—or other optimization problem—is an interesting research line that has not yet been highly exploited.


## 3. Set Covering Problem

In this section we present the set covering problem. The set covering problem consists in finding a set of solutions at the lowest possible cost to cover a set of needs. Line balancing production [45], crew scheduling [46–48], service installation [49, 50], databases [51], production flow-lines optimization [52], and Boolean expressions [53] are some practical examples of set covering problem. Formally, we define the problem as follows: Let A=(aij) be a binary matrix with M-rows  ×  N-columns, and let C=(cj) be a vector representing the cost of each column j, assuming that cj>0,∀j∈N. Then, we can observe that column (j∈N) cover a row i that exists in M, if aij=1. The corresponding mathematical is stated in the following:(1)minimize∑j=1Ncjxjsubject to(2)∑j=1Naijxj≥1,∀i=1,…,M(3)xj∈0,1,∀j=1,…,NThe aim is to minimize the summation of column costs, where xj=1 if component j is part of the solution and xj=0 otherwise. The constraints of the set covering problem guarantee that every row i is covered by at least one column j.


## 4. Black Hole Algorithm

The black hole algorithm is a population-based algorithm inspired on the black hole phenomenon [54, 55]. A black hole is a zone of space that has so much mass concentrated in it that there is no way for a nearby object to escape its gravitational force. Anything falling into a black hole, including light, cannot escape.Similar to other population-based algorithms, the black hole algorithm begins with an initial population of potential solutions, called “stars". At each iteration of the black hole algorithm, the best solution is chosen to be the black hole, which then starts atractting other candidates around it. If the fitness of a star crosses the event horizon of the black hole (Eq. (5)), it will be swallowed and it is gone forever. In such 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:(4)xijt+1=xijt+rxBHj-xijt,∀i∈1,…,popSizewhere xij(t) and xij(t+1) are the components of a solution i at iterations t and (t+1), respectively. xBHj is the component of best solution (black hole) in the search space. r is a random number in the interval [0,1]. Finally, popSize represents 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 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:(5)R=fBH∑i=1popSizefiwhere fBH is the fitness value of the black hole, fi is the fitness value of the i-th star, and popSize is the number of stars (potential solutions).When the distance between a star and the black hole (best candidate) is less thanR, 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 described in detail in Algorithm 1.Algorithm 1:Black hole algorithm.
Require: Problem input data, popSize,T Ensure: The best solution that resolves the set covering problem 1: {N,cj}←loadProblemData() 2: Produce the first generation of popSize stars 3: for all star xi,(∀i=1,…,popSize)  do 4:for all dimension j,(∀j=1,…,N)  do 5:xij←Random{0,1} 6:end for 7:fi←cost(xi) 8: end for 9: globalfit←+∞ 10:Produce T-generations of popSize stars 11:while  t<T  do 12:{minfit,minindex}←min(f) 13:if  minfit<globalfit  then 14:globalfit←minfit 15:for all dimension j,(∀j=1,…,N)  do 16:x^j(t)←xminindexj(t) 17:end for 18:end if 19:for all star xi,(∀i=1,…,popSize)  do 20:Calculate the event horizon through Eq. (5) and distance between the current solution with respect to the best solution 21:R←fBH∑i=1popSizecost(xi) 22:rand←Random[0,1] 23:if  R>rand  then 24:for all dimension j,(∀j=1,…,N)  do 25:xij(t)←Random{0,1} 26:end for 27:end if 28:end for 29:for all star xi,(∀i=1,…,popSize)  do 30:for all dimension j,(∀j=1,…,N)  do 31:Generate new solutions through Eq. (4) 32:xij(t+1)=xij(t)+r[xBHj-xij(t)] 33:In previous step, the value generated belongs to the real domain and it must be brought to a binary domain 34:xij(t+1)←g(xij(t+1)) 35:end for 36:end for 37:end while 38:return Postprocess results and visualization;The black hole algorithm begins with the loading and processing phases. Then, at Lines 3-8, an initial population ofpopSize stars is randomly generated as a vector of N 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 cost (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-37). As previously mentioned, the set covering problem is a minimization problem. This evaluation is handled in comparison presented at Line 13. If the new minimum value is less than minimum global, the minimum global is changed by the new minimum value and the best solution is stored inx^ (black hole).If the fitness of a star crosses the event horizon of the black hole, 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 19-28.Finally, the last for loop statement (Lines 29-36) generates new solutions according to Equation (4), for each dimension j. 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.


### 4.1. Adaptive Black Hole Algorithm

The basic version of the black hole algorithm has not control parameters. If we observe the parameterpopSize, we can see that the population size is valuated before the run of the metaheuristic. At each iteration of the algorithm, the solutions are altered updating their position or when they are absorbed by the black hole, in which case a new random solution—or star—is created. However, the total number of solutions is preserved. The second part of the metaheuristic uses an absorption process, called event horizon that is a stochastic procedure and it is influenced by the best solution, discarding bad solutions that seem to lead to poor results. This is not necessarily a correct idea, since often a bad solution can be drive the search to an optimal one.These concerns are very important for the performance of the algorithm, reason why we have decided to take the event horizon logic to calculate the value of the population size parameter in autonomous way. For that, we use autonomous search which is a particular case of adaptive systems that improve their solving performance by modifying and adjusting themselves to the problem at hand, either by adaptation or supervised adaptation (please see [3, 56] for details). This approach has been successfully applied in constraint programming using bioinspired algorithms for controlling the process resolution of solver tools [57, 58]. The objective of autonomous search is to allow the metaheuristic to self-adapt the value of the parameter popSize during the run, according to the algorithm convergence.The literature presents several works illustrating how to improve evolutionary algorithms by dynamically controlling parameters during solving time [13–17, 22]. We have decided to modify the original black hole algorithm considering the autonomous search principles for building a procedure that adaptively vary the number of solutions (population size parameter), according to the performance exhibited during search.We are inspired by this approach to improve the local search process of black hole algorithm. The main objective is to give the algorithm the ability to adjust its population size. When algorithm is stagnant some solutions are improved according to the best solution. In opposition, if solutions are far away from the best solution, the worst stars are eliminated and new ones are randomly generated.We vary only the population parameter since is the only one available to be modified during solving time, this make the implementation easier and the solving process improved. We believe this approach also provide know-how for future experiments involving adaptive population. The procedure is described in Algorithm2.Algorithm 2:Adaptive approach for the population size parameter (popSize).
Require: Population size popSize, current iteration t, number of stagnation ls, and size of instance N. Ensure: New value for the parameter popSize. 1: if  t achieves ls  then 2:prob←|cost(xbh)-cost(xwrong)|∑i=1popSize‍cost(xi) 3:rand←Random[0,1] 4:if  rand>prob  then 5:b←roundup(popSize×prob) 6:rand←Random[0,1] 7:if  rand>prob  then 8:for all star xi,(∀i=1,…,b)  do 9:xn+i←xbh 10:end for 11:else 12:for all star xi,(∀i=1,…,b)  do 13:for all dimension j,(∀j=1,…,N)  do 14:xpopSize+ij←Random{0,1} 15:end for 16:end for 17:end if 18:popSize←popSize+b 19:else 20:w←roundup(popSize×prob) 21:if  popSize≥w  then 22:Remove w worst solutions 23:popSize←popSize-w 24:end if 25:end if 26:end ifInputs of the procedure are the value of population sizepopSize, current iteration t, and number of stagnation ls that represents the number of iterations where the best solution does not improve, commonly called “local search”.Reached this point, we calculate the distance between best and worst solutions according to cost of each one and then it divides by sum of all costs (Line 2). This value describes the percentage of maximum separation between solutions. A low percentage value indicates that solutions are homogeneous skewed to the best solution, in which case the procedure creates new solutions (Lines 5-18). To create these solutions, we reuse the percentage to determinate if they are cloned from best solution (Lines 8-10) or they are randomly generated (Lines 12-16). On the other hand, ifprob>rand means that solutions are heterogeneous; thus the procedure remove the worst solutions (Lines 20-22).In both cases, the percentages calculated can also be seen as a mechanism to support the exploration and exploitation phases. If solution are homogeneous, this procedure allows to explore towards new solutions, while if solutions are heterogeneous, the procedure converges towards a set of similar solutions itself.For computational experiments we usepopSize=20 potential solution and T=5000 number of generations. Although the approach proposed is adaptive, it is necessary to define an initial value for popSize.


### 4.2. Binary Approaches

It is known that variables of the set covering problem are limited to binary values, namely,xij∈0,1,∀j∈{1,…,N}: for this reason, we use a binary representation for each solution given by the black hole algorithm, as shown in Figure 2, where(6)xij=1,if  the  dimensionjis  part  of  the  solution0,otherwiseFigure 2
Binary solution representation.In this paper, we use the standard black hole algorithm [59], where each star represent a candidate solution.However, the standard version of the black hole algorithm is 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 domain. The binarization strategy is composed of a transfer function and a discretization method. In this work, we tested 32 different binarization strategies.We evaluate different functions, separated into two families [60, 61]: S-Shape and V-Shape (see Table 1).Table 1
S-Shape and V-Shape transfer functions.
S -Shape V -Shape S 1 :   g x i j = 1 1 + e - 2 x i j V 1 :   g x i j = erf ⁡ π 2 x i j   S 2 :   g x i j = 1 1 + e - x i j V 2 :  g x i j = tanh ⁡ x i j   S 3 :   g x i j = 1 1 + e - x i j / 2 V 3 :   g x i j = x i j 1 + x i j 2   S 4 :   g x i j = 1 1 + e - x i j / 3 V 4 :   g x i j = 2 π arctan ⁡ π 2 x i jOnce a transfer function is applied, the input real number is mapped to a real number belonging to[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 returns 1; otherwise, return 0.(7)xij=1,ifrand≤gxij0,otherwise(2)
Complement: if condition is satisfied, standard method returns the complement value.(8)xij=xij¯,ifrand≤gxij0,otherwise(3)
Static probability: a probability is generated and it is evaluated with a transfer function.(9)xij=0,ifgxij≤αxij,ifα<gxij≤121+α1,ifgxij≥121+α(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.(10)xij=xij,ifrand≤gxij0,otherwise


### 4.3. Heuristic Feasibility Operator

Generally, metaheuristics may provide solutions that violate the constraints of the problem. For instance, a new set covering problem solution owning uncovered rows, clearly violates a subset of constraints. In order to provide feasible solutions the algorithm needs additional operators. To this end, we employ a 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 columnj over the sum of all the constraint matrix rows covered by a column j, as shown in (11)costcolumnjcoveredRowscolumnjThe unfeasible solutions are repaired by covering the columns of the solution that had the lower ratio. After this, a local optimization step is applied, where column redundancy is eliminated. A column is redundant when it can be deleted and the feasibility of the solution is not affected.Algorithm3 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.Algorithm 3:Heuristic feasibility operator.
1: αi← The set of columns that cover row i, i∈M 2: βj← The set of rows covered by column j, j∈N 3: S← The set of columns in a solution 4: wi← The number of columns that cover row i, i∈M. For this, wi←|S∩αi|,  ∀i∈M 5: U← The set of uncovered rows. For this, U={i∣wi=0,∀i∈M} 6: for all row i∈U (in increasing order of i) do 7:Find the first column j in increasing order of j∈αi that minimizes cj/|U∩bj| 8:Add j to S and set wi←wi+1,∀i∈bj 9:Set U←U-bj 10:end for 11:for all column j∈S (in decreasing order of j) do 12:if  wi≥2  then 13:S←S-j 14:wi←wi-1,∀i∈βj 15:end if 16:end for 17:return  S is now a feasible solution for the set covering problem that contains no redundant columns;


## 4.1. Adaptive Black Hole Algorithm

The basic version of the black hole algorithm has not control parameters. If we observe the parameterpopSize, we can see that the population size is valuated before the run of the metaheuristic. At each iteration of the algorithm, the solutions are altered updating their position or when they are absorbed by the black hole, in which case a new random solution—or star—is created. However, the total number of solutions is preserved. The second part of the metaheuristic uses an absorption process, called event horizon that is a stochastic procedure and it is influenced by the best solution, discarding bad solutions that seem to lead to poor results. This is not necessarily a correct idea, since often a bad solution can be drive the search to an optimal one.These concerns are very important for the performance of the algorithm, reason why we have decided to take the event horizon logic to calculate the value of the population size parameter in autonomous way. For that, we use autonomous search which is a particular case of adaptive systems that improve their solving performance by modifying and adjusting themselves to the problem at hand, either by adaptation or supervised adaptation (please see [3, 56] for details). This approach has been successfully applied in constraint programming using bioinspired algorithms for controlling the process resolution of solver tools [57, 58]. The objective of autonomous search is to allow the metaheuristic to self-adapt the value of the parameter popSize during the run, according to the algorithm convergence.The literature presents several works illustrating how to improve evolutionary algorithms by dynamically controlling parameters during solving time [13–17, 22]. We have decided to modify the original black hole algorithm considering the autonomous search principles for building a procedure that adaptively vary the number of solutions (population size parameter), according to the performance exhibited during search.We are inspired by this approach to improve the local search process of black hole algorithm. The main objective is to give the algorithm the ability to adjust its population size. When algorithm is stagnant some solutions are improved according to the best solution. In opposition, if solutions are far away from the best solution, the worst stars are eliminated and new ones are randomly generated.We vary only the population parameter since is the only one available to be modified during solving time, this make the implementation easier and the solving process improved. We believe this approach also provide know-how for future experiments involving adaptive population. The procedure is described in Algorithm2.Algorithm 2:Adaptive approach for the population size parameter (popSize).
Require: Population size popSize, current iteration t, number of stagnation ls, and size of instance N. Ensure: New value for the parameter popSize. 1: if  t achieves ls  then 2:prob←|cost(xbh)-cost(xwrong)|∑i=1popSize‍cost(xi) 3:rand←Random[0,1] 4:if  rand>prob  then 5:b←roundup(popSize×prob) 6:rand←Random[0,1] 7:if  rand>prob  then 8:for all star xi,(∀i=1,…,b)  do 9:xn+i←xbh 10:end for 11:else 12:for all star xi,(∀i=1,…,b)  do 13:for all dimension j,(∀j=1,…,N)  do 14:xpopSize+ij←Random{0,1} 15:end for 16:end for 17:end if 18:popSize←popSize+b 19:else 20:w←roundup(popSize×prob) 21:if  popSize≥w  then 22:Remove w worst solutions 23:popSize←popSize-w 24:end if 25:end if 26:end ifInputs of the procedure are the value of population sizepopSize, current iteration t, and number of stagnation ls that represents the number of iterations where the best solution does not improve, commonly called “local search”.Reached this point, we calculate the distance between best and worst solutions according to cost of each one and then it divides by sum of all costs (Line 2). This value describes the percentage of maximum separation between solutions. A low percentage value indicates that solutions are homogeneous skewed to the best solution, in which case the procedure creates new solutions (Lines 5-18). To create these solutions, we reuse the percentage to determinate if they are cloned from best solution (Lines 8-10) or they are randomly generated (Lines 12-16). On the other hand, ifprob>rand means that solutions are heterogeneous; thus the procedure remove the worst solutions (Lines 20-22).In both cases, the percentages calculated can also be seen as a mechanism to support the exploration and exploitation phases. If solution are homogeneous, this procedure allows to explore towards new solutions, while if solutions are heterogeneous, the procedure converges towards a set of similar solutions itself.For computational experiments we usepopSize=20 potential solution and T=5000 number of generations. Although the approach proposed is adaptive, it is necessary to define an initial value for popSize.


## 4.2. Binary Approaches

It is known that variables of the set covering problem are limited to binary values, namely,xij∈0,1,∀j∈{1,…,N}: for this reason, we use a binary representation for each solution given by the black hole algorithm, as shown in Figure 2, where(6)xij=1,if  the  dimensionjis  part  of  the  solution0,otherwiseFigure 2
Binary solution representation.In this paper, we use the standard black hole algorithm [59], where each star represent a candidate solution.However, the standard version of the black hole algorithm is 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 domain. The binarization strategy is composed of a transfer function and a discretization method. In this work, we tested 32 different binarization strategies.We evaluate different functions, separated into two families [60, 61]: S-Shape and V-Shape (see Table 1).Table 1
S-Shape and V-Shape transfer functions.
S -Shape V -Shape S 1 :   g x i j = 1 1 + e - 2 x i j V 1 :   g x i j = erf ⁡ π 2 x i j   S 2 :   g x i j = 1 1 + e - x i j V 2 :  g x i j = tanh ⁡ x i j   S 3 :   g x i j = 1 1 + e - x i j / 2 V 3 :   g x i j = x i j 1 + x i j 2   S 4 :   g x i j = 1 1 + e - x i j / 3 V 4 :   g x i j = 2 π arctan ⁡ π 2 x i jOnce a transfer function is applied, the input real number is mapped to a real number belonging to[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 returns 1; otherwise, return 0.(7)xij=1,ifrand≤gxij0,otherwise(2)
Complement: if condition is satisfied, standard method returns the complement value.(8)xij=xij¯,ifrand≤gxij0,otherwise(3)
Static probability: a probability is generated and it is evaluated with a transfer function.(9)xij=0,ifgxij≤αxij,ifα<gxij≤121+α1,ifgxij≥121+α(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.(10)xij=xij,ifrand≤gxij0,otherwise


## 4.3. Heuristic Feasibility Operator

Generally, metaheuristics may provide solutions that violate the constraints of the problem. For instance, a new set covering problem solution owning uncovered rows, clearly violates a subset of constraints. In order to provide feasible solutions the algorithm needs additional operators. To this end, we employ a 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 columnj over the sum of all the constraint matrix rows covered by a column j, as shown in (11)costcolumnjcoveredRowscolumnjThe unfeasible solutions are repaired by covering the columns of the solution that had the lower ratio. After this, a local optimization step is applied, where column redundancy is eliminated. A column is redundant when it can be deleted and the feasibility of the solution is not affected.Algorithm3 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.Algorithm 3:Heuristic feasibility operator.
1: αi← The set of columns that cover row i, i∈M 2: βj← The set of rows covered by column j, j∈N 3: S← The set of columns in a solution 4: wi← The number of columns that cover row i, i∈M. For this, wi←|S∩αi|,  ∀i∈M 5: U← The set of uncovered rows. For this, U={i∣wi=0,∀i∈M} 6: for all row i∈U (in increasing order of i) do 7:Find the first column j in increasing order of j∈αi that minimizes cj/|U∩bj| 8:Add j to S and set wi←wi+1,∀i∈bj 9:Set U←U-bj 10:end for 11:for all column j∈S (in decreasing order of j) do 12:if  wi≥2  then 13:S←S-j 14:wi←wi-1,∀i∈βj 15:end if 16:end for 17:return  S is now a feasible solution for the set covering problem that contains no redundant columns;


## 5. Experimental Results

After to apply the adaptive approach, we have analyzed the time complexity of the basic algorithm to illustrate that our proposal does not affect its performance. If we observe each flow control, statements and expressions from the basic black hole algorithm, we can determine that time complexity is given byO(T×popSize×N), where T is a constant representing the maximum of iterations and it is avoided, popSize value is the number of solutions, and N is the dimension of each solution. In worst case, the basic algorithm is upper bounded by O(kn2).Now, evaluating time complexity about our adaptive approaches, we determine that the upper bound is given byO(b×N), where b is the new number of solutions and N is the dimension of each solution. This procedures are activated when the number of iterations achieve the local search criterials, therefore they are independent of the main algorithm and as a consequence its performance and complexity time are not altered.With respect to space analysis about our approach, we considerate the space used in principal memory. In this context, every time that the adaptive algorithms are lunched, we observe that the usage of the principal memory is not outperformed to 8%. The basic algorithm use a similar percentage of principal memory.The performance of the adaptive black hole algorithm is experimentally evaluated by using 65 instances of the set covering problem organized in 11 sets taken from the Beasley's OR-library [62]. Table 2 describes instance set, number of rows or constraints M, number of columns or variables (dimension) N, range of costs, and density (percentage of nonzeroes in the matrix).Table 2
Instances from Beasley’s OR-Library.
Instance group M N Cost range Density ( % ) 4 200 1000 [1,100] 2  5 200 2000 [1,100] 2  6 200 1000 [1,100] 5  A 300 3000 [1,100] 2  B 300 3000 [1,100] 5  C 400 4000 [1,100] 2  D 400 4000 [1,100] 5  E 500 5000 [1,100] 10  F 500 5000 [1,100] 20  G 1000 10000 [1,100] 2  H 1000 10000 [1,100] 5In order to reduce the instance size of set covering problem, we have used a preprocessed instances set. Different preprocessing methods have particularly been proposed in [63]. We employ two of them, which have been proved to be the most effective ones:(i)
Column Domination. The nonunicost set covering problem holds different column costs, then once a set of rows Ij is covered by another column j′ and cj′<cj, we say that column j is dominated by j′, then column j is removed from the solution.(ii)
Column Inclusion. If a row is covered by only one column after the above domination, it 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). The RPD value quantifies the deviation of the objective value Zmin from Zopt that in our case is the best known value for each instance and it is calculated as follows:(12)RPD=Zmin-ZoptZoptThe minimum (Min), maximum (Max), and average (Avg) of the solutions obtained were achieved running 30 runs over each one of set the 65 test instances. We test all the combinations of transfer functions and discretization methods over all these instances. Before to test all instances, we perform a sampling phase to evaluate which binarization strategy would show the best performance. In appendix section we include preliminary results in the sampling phase (see Tables9 and 10 and Figures 7 and 8). The binarization strategy that achieved the best results for the black hole algorithm is S4+Elitist.


### 5.1. Black Hole Algorithms Comparison

In this Section, we compare the proposed adaptive black hole algorithm with the basic black hole one. To the best of our knowledge, no autonomous search implementation on top of black hole has been proposed yet to include in the comparison.The algorithm implementation has been done using Java SE 7 and the experiments have been launched on a 2.3 Ghz Intel Core i3 with 4 GB RAM machine running Windows 7 (available athttps://goo.gl/AEYXJq). The initial parameter setting used is as follows: a population size of 40, 4000 iterations, a local search of 40 and 30 executions for each instance. Bold font and underlined row are used to present when the adaptive black hole algorithm outperforms their basic version.Table3 illustrates the results obtained for all instances from groups 4, 5, 6, A, B, C, and D. Regarding instance sets 4 and 6, the proposed adaptive approach in this work (BH-AS) improves dramatically the results in 50%, reaching 4 global optimums. Considering instance sets 5 and 6, we can observe that the basic black hole algorithm exhibits great performance achieving 80% of the optimal values. However, the adaptive process of the population size parameter improves results obtaining 2 more optimal values. Now, if we analyze instances from groups A, B, C, and D, we can see that again the basic black hole algorithm shows an outstanding efficiency to solve the set covering problem, solving to optimally 15 of 20 instances. Nevertheless, the adaptive approach shows that it can improve even more, finding one more optimal value for the instance C.1.Table 3
Computational results of groups 4, 5, 6, A, B, C, and D.
Instance Z o p t Black Hole Algorithm Basic BH-AS Z m i n RPD times (ms) Z m i n RPD times (ms) 4.1 429 430 0.002 1011.3 430 0.002 1181.2 4.2 512 512 0.000 1867.0 512 0.000 1926.0 4.3 516 516 0.000 2007.5 516 0.000 1957.1 4.4 494 495 0.002 1998.2 494 0.000 2108.1 4.5 512 514 0.004 2010.1 512 0.000 1992.3 4.6 560 560 0.000 2021.3 560 0.000 2102.2 4.7 430 430 0.000 2014.5 430 0.000 2032.2 4.8 492 494 0.004 2311.0 492 0.000 2202.6 4.9 641 644 0.005 2099.1 643 0.003 2109.9 4.10 514 515 0.002 1981.7 514 0.000 2017.1  5.1 253 253 0.000 2171.9 253 0.000 2001.7 5.2 302 305 0.010 1992.4 302 0.000 2071.2 5.3 226 228 0.000 2221.8 228 0.000 2221.8 5.4 242 242 0.000 2008.1 242 0.000 2191.2 5.5 211 211 0.000 2001.4 211 0.000 2127.4 5.6 213 213 0.000 2091.1 213 0.000 2222.1 5.7 293 293 0.000 2132.3 293 0.000 2332.1 5.8 288 288 0.000 2199.7 288 0.000 2339.2 5.9 279 279 0.000 2351.6 279 0.000 2271.2 5.10 265 265 0.000 1989.4 265 0.000 2057.7  6.1 138 140 0.014 2915.7 138 0.000 2915.7 6.2 146 147 0.007 2910.1 147 0.007 2791.6 6.3 145 145 0.000 2717.1 145 0.000 2751.7 6.4 131 131 0.000 2981.3 131 0.000 3003.7 6.5 161 161 0.000 3081.2 161 0.000 3038.3  A.1 253 253 0.000 3009.5 253 0.000 2967.1 A.2 252 253 0.004 3033.2 253 0.004 2983.2 A.3 232 233 0.004 2991.9 233 0.004 3104.9 A.4 234 234 0.000 3091.2 234 0.000 3111.1 A.5 236 236 0.000 3001.4 236 0.000 3012.3  B.1 69 69 0.000 3223.5 69 0.000 3122.1 B.2 76 76 0.000 3011.3 76 0.000 3183.6 B.3 80 80 0.000 3253.3 80 0.000 3452.0 B.4 79 79 0.000 3212.1 79 0.000 3419.1 B.5 72 72 0.000 3433.3 72 0.000 3501.0  C.1 227 229 0.009 3271.1 227 0.000 3397.9 C.2 219 219 0.000 3090.4 219 0.000 3291.1 C.3 243 245 0.008 3194.6 245 0.008 3229.2 C.4 219 219 0.000 3230.2 219 0.000 3323.1 C.5 215 215 0.000 2979.6 215 0.000 3111.8  D.1 60 60 0.000 5821.3 60 0.000 6021.0 D.2 66 67 0.015 6010.2 67 0.015 6094.1 D.3 72 73 0.014 6071.2 73 0.014 6147.7 D.4 62 62 0.000 6313.4 62 0.000 6511.6 D.5 61 61 0.000 6831.4 61 0.000 6712.2Table4 presents the results obtained for instances from groups NRE, NRF, NRG, and NRH. If we consider that the basic black hole algorithm reaches 3 optimal values from 20, there is a wide margin to improve. Taking into account the fact that the autoadaptive methods outperform the basic BH algorithm in 11 of 17 possible instances and 2 of them are global optima, we can say that BH-AS performs significantly better than the basic version.Table 4
Computational results of groups NRE, NRF, NRG, and NRH.
Instance Z o p t Black Hole Algorithm Basic BH-AS Z m i n RPD times (ms) Z m i n RPD times (ms) NRE.1 29 30 0.034 6200.0 29 0.000 6135.0 NRE.2 30 31 0.033 6235.4 31 0.033 6115.1 NRE.3 27 28 0.037 5988.3 28 0.037 5991.9 NRE.4 28 29 0.036 6875.2 28 0.000 7081.0 NRE.5 28 28 0.000 7298.1 28 0.000 7191.1  NRF.1 14 14 0.000 6788.4 14 0.000 7118.5 NRF.2 15 15 0.000 8313.4 15 0.000 8212.1 NRF.3 14 17 0.214 8934.4 16 0.143 9293.8 NRF.4 14 16 0.143 7746.3 14 0.000 8023.3 NRF.5 13 14 0.077 7021.1 14 0.077 7220.2  NRG.1 176 182 0.034 7143.5 179 0.017 7644.8 NRG.2 154 160 0.039 7948.0 158 0.026 8584.5 NRG.3 166 170 0.024 8771.8 169 0.018 9874.0 NRG.4 168 170 0.012 8123.7 170 0.012 8919.2 NRG.5 168 170 0.012 9013.4 168 0.000 9921.2  NRH.1 63 66 0.048 15114.6 65 0.032 17911.2 NRH.2 63 67 0.063 16343.4 67 0.063 19733.4 NRH.3 59 64 0.085 19243.7 64 0.085 21840.3 NRH.4 58 64 0.103 18241.6 63 0.086 21421.7 NRH.5 55 63 0.145 24442.6 62 0.127 22242.5Figure3 illustrates convergence charts for the hardest instances of each instance group. Here, we observe that for the 4 group the convergence of the BH-AS is clearly faster than the basic algorithm. For the group 5, the BH-AS begins with a bad quality solution but at the middle of the process improves its performance outperforming the basic BHA similar behaviour can be seen for the NRE and NRH group. The performance of instances from groups 6, A, B, C, and D is similar keeping all of them an early convergence. Finally, for benchmarks from groups NRF and NRG, the behaviour of BH-AS is clearly earlier than its competitor.Figure 3
Convergence charts for the hardest instances of each instance group.Now, if we regard solving times required for reaching the solutions, we may observe that times are very similar for the two algorithms. However, we must consider that BH-AS need the computation of the adaptive process and is able to outperform the basic BH in terms of optimum values reached. We can observe also a small difference in terms of solving times in favor of the BH-AS with respect to BH.


### 5.2. BH-AS v/s Original Approach

After to analyze the exhibited efficiency for BH-AS and the basic algorithm for solving the set covering problem, we have observed that the variation is minimal. It is not possible to state which technique is the best. However, in order to show a significant difference between the adaptive approach and the original black hole algorithm, we perform a contrast statistical test for each instance through theKolmogorov-Smirnov-Lilliefors to determine the independence of samples [64] andWilcoxon's signed rank [65] to compare statistically the results.For both tests, we consider a hypothesis evaluation, which is analyzed assuming ap_value of 0.05—accuracy—i.e., smaller values than 0.05, determines that the corresponding hypothesis cannot be assumed. Both tests were conducted usingGNU Octave  (available at http://goo.gl/jtHn8i).The first test allows us to analyze the independence of samples. For that, we run the algorithm 30 times for each instance and then, we apply the test. According to obtained values, we can decide if samples follow a normal distribution or they are independent. To proceed, we propose the following hypotheses:(i)
H0 states that Zmin follows a normal distribution.(ii)
H1 states the opposite.The conducted test has yieldedp_value lower than 0.05; therefore H0 cannot be assumed.Then, as samples are independent and cannot be assumed that 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 nonparametric test for evaluating the heterogeneity of samples. For that we use theWilcoxon’s signed rank test. This is a paired test that compare the medians of two distributions. To proceed, we propose the following new hypotheses:(i)
H0: Z~min achieved by basic black hole algorithm <Z~min achieved by BH-AS.(ii)
H1 states the opposite.Table5 compares the approaches for all tested instances via theWilcoxon’s signed rank test. As the significance level is also established to 0.05, smaller values that 0.05 defines that H0 cannot be assumed. Again, bold font and underlined row are used for a winner value of the metaheuristic stated in the column of the table, e.g., for instance 4.1, BH-AS is better than basic algorithm as its value is lower than 0.05, then H0 cannot be assumed.Table 5
Statistical test.
Instance 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10  Basic – – 0.01 – – – 0.02 – – –  BH-AS 0.01 – – 0.01 0.01 – – 0.04 0.01 0.01  Instance 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 5.10  Basic – – 0.01 – – – – – – 0.04  BH-AS – 0.02 – – 0.03 0.01 0.05 – – –  Instance 6.1 6.2 6.3 6.4 6.5 A.1 A.2 A.3 A.4 A.5  Basic – – – – – 0.02 0.05 – – –  BH-AS 0.01 – 0.01 – 0.01 – – 0.01 0.01 0.01  Instance B.1 B.2 B.3 B.4 B.5 C.1 C.2 C.3 C.4 C.5  Basic – – – 0.03 0.02 – – – 0.01 –  BH-AS – 0.01 0.01 – – – 0.05 0.01 – 0.04  Instance D.1 D.2 D.3 D.4 D.5 NRE.1 NRE.2 NRE.3 NRE.4 NRE.5  Basic – – – – – – 0.03 – – 0.01  BH-AS 0.02 – – 0.01 0.03 0.01 – 0.01 0.04 –  Instance NRF.1 NRF.2 NRF.3 NRF.4 NRF.5 NRG.1 NRG.2 NRG.3 NRG.4 NRG.5  Basic – 0.01 – – – – – – – –  BH-AS 0.03 – 0.03 0.01 0.03 0.01 0.03 0.01 0.01 0.02  Instance NRH.1 NRH.2 NRH.3 NRH.4 NRH.5  Basic – – – – –  BH-AS 0.03 – 0.01 0.03 0.05According to results, forp_values lower than 0.05 for black hole optimization are 12 and for BH-AS are 40. The rest does not provide significant information. This results illustrating that the performance of BH-AS is better than the original approach.


### 5.3. BH-AS v/s Other Optimization Techniques

To evidence the performance of our adaptive approach, we perform a comparison with different approximation techniques: binary cat swarm optimization (BCSO) [41], binary firefly optimization (BFO) [40], binary shuffled frog leaping algorithm (BSFLA) [42], binary artificial bee colony (BABC) [43], and binary electromagnetism-like algorithm (BELA) [66].We additionally incorporate a comparative by using Mixed Integer Linear Programming (MIP) as exact solving method implemented on MiniZinc G12 MIP. With the solver, the instances are solved to a maximum time of 8 hours. If no solution is found at this point the problem is set to t.o. (time-out).Tables6, 7, and 8 illustrate that the proposed approach is able to reach competitive results in contrast to those modern optimization techniques.Table 6
Comparison results for instance set of groups 4, 5, 6, and A.
Instance 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10  Z o p t 429 512 516 494 512 560 430 492 641 514  BH-AS Z m i n 430 512 516 494 512 560 430 492 643 514 Z a v g 430 512 516 501 519 562 432 495 648 517 R P D 0.002 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.003 0.000 T i m e   ( m s ) 1811.2 1926.0 1957.1 2108.1 1992.3 2102.2 2032.2 2202.6 2109.9 2017.1  BCSO Z m i n 459 570 590 547 545 637 462 546 711 537 Z a v g 480 594 607 578 554 650 467 567 725 552 R P D 7 11.3 14.3 10.7 6.4 13.8 7.4 11 10.9 4.5  BFO Z m i n 429 517 519 495 514 563 430 497 655 519 Z a v g 430 517 522 497 515 565 430 499 658 523 R P D 0 0.97 0.58 0.2 0.39 0.53 0 1.01 2.18 0.97  BSFLA Z m i n 430 516 520 501 514 563 431 497 656 518 Z a v g 430 518 520 504 514 563 432 499 656 519 R P D 0.23 0.78 0.78 1.42 0.39 0.54 0.23 1.02 2.34 0.78  BELA Z m i n 447 559 537 527 527 607 448 509 682 571 Z a v g 448 559 539 530 529 608 449 512 682 571 R P D 4.20 9.18 4.07 6.68 2.93 8.39 4.19 3.46 6.40 11.09  BABC Z m i n 430 513 519 495 514 561 431 493 649 517 Z a v g 430 513 521 496 517 565 434 494 651 519 R P D 0.23 0.20 0.58 0.20 0.39 0.18 0.23 0.20 0.93 0.58  MIP Z m i n 429 512 516 494 512 560 430 492 641 514 T i m e   ( m s ) 705 912 788 934 654 701 693 712 917 868  Instance 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 5.10  Z o p t 253 302 226 242 211 213 293 288 279 265  BH-AS Z m i n 253 302 226 242 211 213 293 288 279 265 Z a v g 253 302 226 242 211 213 293 288 279 265 R P D 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 T i m e   ( m s ) 2001.7 2071.2 2221.8 2191.2 2127.4 2222.1 2332.1 2339.2 2271.2 2057.7  BCSO Z m i n 279 339 247 251 230 232 332 320 295 285 Z a v g 287 340 251 253 230 243 338 330 297 287 R P D 10.3 12.3 9.3 3.7 9 8.9 13.3 11.1 5.7 7.5  BFO Z m i n 257 309 229 242 211 213 298 291 284 268 Z a v g 260 311 233 242 213 213 301 292 284 270 R P D 1.58 2.31 1.32 0 0 0 1.7 1.04 1.79 1.13  BSFLA Z m i n 254 307 228 242 211 213 297 291 281 265 Z a v g 255 307 230 242 213 214 299 293 283 266 R P D 0.4 1.66 0.88 0 0 0 1.37 1.04 0.72 0  BELA Z m i n 280 318 242 251 225 247 316 315 314 280 Z a v g 281 321 240 252 227 248 317 317 315 282 R P D 10.67 5.30 7.08 3.72 6.64 15.96 7.85 9.38 12.54 5.66  BABC Z m i n 254 309 229 242 211 214 298 289 280 267 Z a v g 255 309 233 245 212 214 301 291 281 270 R P D 0.40 2.32 1.33 0 0 0.47 1.71 0.35 0.36 0.75  MIP Z m i n 253 302 226 242 211 213 293 288 279 265 T i m e   ( m s ) 4776 3882 4332 4899 4771 4329 3887 5191 4659 4879  Instance 6.1 6.2 6.3 6.4 6.5 A.1 A.2 A.3 A.4 A.5  Z o p t 138 146 145 131 161 253 252 232 234 236   BH-AS Z m i n 138 147 145 131 161 253 253 233 234 236 Z a v g 142 150 147 131 161 234 253 234 234 236 R P D 0.000 0.007 0.000 0.000 0.000 0.000 0.004 0.000 0.000 0.000 T i m e   ( m s ) 2915.7 2791.6 2751.7 3003.7 3038.3 2967.1 2983.2 3104.9 3111.1 3012.3  BCSO Z m i n 151 152 160 138 169 286 274 257 248 244 Z a v g 160 157 164 142 173 287 276 263 251 244 R P D 9.4 4.1 10.3 5.3 5 13 8.7 10.8 6 3  BFO Z m i n 138 147 147 131 164 255 259 238 235 236 Z a v g 140 149 150 131 164 256 261 240 237 237 R P D 0 0.68 1.37 0 1.86 0.79 2.77 2.58 0.42 0  BSFLA Z m i n 140 147 147 131 166 255 260 237 235 236 Z a v g 141 147 148 133 169 258 260 239 238 239 R P D 1.45 0.68 1.38 0 3.11 0.79 3.17 2.16 0.43 0  BELA Z m i n 152 160 160 140 184 261 279 252 250 241 Z a v g 152 161 163 142 187 264 281 253 252 243 R P D 10.14 9.59 10.34 6.87 14.29 3.16 10.71 8.62 6.84 2.12  BABC Z m i n 142 147 148 131 165 254 257 235 236 236 Z a v g 143 150 149 133 167 254 259 238 237 238 R P D 2.90 0.68 2.07 0 2.48 0.40 1.98 1.29 0.85 0  MIP Z m i n 138 146 145 131 161 – – – – – T i m e   ( m s ) 1445 2236 1885 2385 2187 t.o. t.o. t.o. t.o. t.o.Table 7
Computational results for instances set of groups B, C, D, NRE, NRF, and NRG.
Instance B.1 B.2 B.3 B.4 B.5 C.1 C.2 C.3 C.4 C.5  Z o p t 69 76 80 79 72 227 219 243 219 215  BH-AS Z m i n 69 76 80 79 72 227 219 245 219 215 Z a v g 70 77 81 81 73 231 220 246 219 216 R P D 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.008 0.000 0.000 T i m e 3122.1 3183.6 3452.0 3419.1 3501.0 3397.9 3291.1 3229.2 3323.1 3111.8  BCSO Z m i n 79 86 85 89 73 242 240 277 250 243 Z a v g 79 89 85 89 73 242 241 278 250 244 R P D 14.5 13.2 6.3 12.7 1.4 6.6 9.6 14 12.3 13  BFO Z m i n 71 78 80 80 72 230 223 253 225 217 Z a v g 72 78 80 81 73 232 224 254 227 219 R P D 2.89 2.63 0 1.26 0 1.32 1.82 4.11 2.73 0.93  BSFLA Z m i n 70 76 80 79 72 229 223 253 227 217 Z a v g 70 77 80 80 73 231 225 253 228 218 R P D 1.45 0 0 0 0 0.88 1.83 4.12 3.65 0.93  BELA Z m i n 86 88 85 84 78 237 237 271 246 224 Z a v g 87 88 87 88 81 238 239 271 248 225 R P D 24.64 15.79 6.25 6.33 8.33 4.41 8.22 11.52 12.33 4.19  BABC Z m i n 70 78 80 80 72 231 222 254 231 216 Z a v g 70 79 80 81 74 233 223 255 233 217 R P D 1.45 2.63 0 1.27 0 1.76 1.37 4.53 5.48 0.47  MIP Z m i n – – – – – – – – – – T i m e   ( m s ) t.o. t.o. t.o. t.o. t.o. t.o. t.o. t.o. t.o. t.o.  Instance D.1 D.2 D.3 D.4 D.5 NRE.1 NRE.2 NRE.3 NRE.4 NRE.5  Z o p t 60 66 72 62 61 29 30 27 28 28  BH-AS Z m i n 60 67 73 62 61 29 31 28 29 28 Z a v g 60 67 73 62 61 29 31 28 28 28 R P D 0.000 0.015 0.014 0.000 0.000 0.000 0.033 0.037 0.000 0.000 T i m e 6021.0 6094.1 6147.7 6511.6 6712.2 6200.0 6115.1 5991.9 7081.0 7191.1  BCSO Z m i n 65 70 79 64 65 29 34 31 32 30 Z a v g 66 70 81 67 66 30 34 32 33 30 R P D 8.3 6.1 9.7 3.2 6.6 0 13.3 14.8 14.3 7.1  BFO Z m i n 60 68 75 62 63 29 32 29 29 29 Z a v g 61 68 77 62 63 31 32 30 31 29 R P D 0 3.03 4.16 0 3.27 0 6.66 7.4 3.57 3.57  BSFLA Z m i n 60 67 75 63 63 29 31 28 29 28 Z a v g 62 68 77 65 66 29 32 28 30 31 R P D 0 1.52 4.17 1.61 3.28 0 3.33 3.7 3.57 0  BELA Z m i n 62 73 79 67 66 30 35 34 33 30 Z a v g 62 74 81 69 67 31 35 34 34 31 R P D 3.33 10.61 9.72 8.06 8.20 3.45 16.67 25.93 17.86 7.14  BABC Z m i n 60 68 76 63 63 29 32 29 29 29 Z a v g 61 68 77 65 66 33 32 31 30 32 R P D 0 3.03 5.56 1.61 3.28 0 6.67 7.41 3.57 3.57  MIP Z m i n – – – – – – – – – – T i m e   ( m s ) t.o. t.o. t.o. t.o. t.o. t.o. t.o. t.o. t.o. t.o.  Instance NRF.1 NRF.2 NRF.3 NRF.4 NRF.5 NRG.1 NRG.2 NRG.3 NRG.4 NRG.5  Z o p t 14 15 14 14 13 176 154 166 168 168   BH-AS Z m i n 14 15 16 14 14 179 158 169 170 168 Z a v g 15 16 16 16 15 181 160 169 171 169 R P D 0.000 0.000 0.143 0.000 0.077 0.017 0.026 0.018 0.012 0.000 T i m e 7118.5 8212.1 9293.8 8023.3 7220.2 7494.4 8584.5 9874.0 8919.2 9921.2  BCSO Z m i n 17 18 17 17 15 190 165 187 179 181 Z a v g 17 18 17 17 16 193 166 188 183 184 R P D 21.4 20 21.4 21.4 15.4 8 7.1 20.6 6.5 7.7  BFO Z m i n 15 16 16 15 15 185 161 175 176 177 Z a v g 17 16 17 18 19 191 163 177 176 181 R P D 7.14 6.66 14.28 7.14 15.38 5.11 4.54 5.42 4.76 5.35  BSFLA Z m i n 15 15 16 15 15 182 161 173 173 174 Z a v g 15 15 17 16 17 183 161 174 177 174 R P D 7.14 0 14.29 7.14 15.38 3.41 4.55 4.22 2.98 3.57  BELA Z m i n 17 18 17 17 16 194 176 184 196 198 Z a v g 17 18 18 19 17 196 176 185 197 199 R P D 21.43 20 21.43 21.43 23.08 10.23 14.29 10.84 16.67 17.86  BABC Z m i n 14 16 16 15 15 183 162 174 175 179 Z a v g 15 16 17 17 16 184 163 175 177 181 R P D 0 6.67 14.29 7.14 15.38 3.98 5.19 4.82 4.17 6.55  MIP Z m i n – – – – – – – – – – T i m e   ( m s ) t.o. t.o. t.o. t.o. t.o. t.o. t.o. t.o. t.o. t.o.Table 8
Computational results for instances of group NRH.
Instance NRH.1 NRH.2 NRH.3 NRH.4 NRH.5  Z o p t 63 63 59 58 55  BH-AS Z m i n 65 67 64 63 62 Z a v g 67 68 65 64 62 R P D 0.032 0.063 0.085 0.086 0.127 T i m e 17911.2 19733.4 21840.3 21421.7 22242.5  BCSO Z m i n 70 67 68 66 61 Z a v g 71 67 70 67 62 R P D 11.1 6.3 15.3 13.8 10.9  BFO Z m i n 69 66 65 63 59 Z a v g 70 66 67 65 60 R P D 9.52 4.76 10.16 6.77 7.27  BSFLA Z m i n 68 66 62 63 59 Z a v g 69 66 63 64 61 R P D 7.94 4.76 5.08 8.62 7.27  BELA Z m i n 70 71 68 70 69 Z a v g 71 71 70 72 69 R P D 11.11 12.70 15.25 20.69 25.45  BABC Z m i n 70 69 66 64 60 Z a v g 71 72 67 64 61 R P D 11.11 9.52 11.86 10.34 9.09  MIP Z m i n – – – – – T i m e   ( m s ) t.o. t.o. t.o. t.o. t.o.Table 9
Sampling phase: hardest instances for groups 4, 5, 6, A, and B.
Hardest instances Transfer functions Discretization methods ID Optimum values Standard Complement Static probability Elitist 4.10 514 S 1 515 514 516 515 S 2 516 515 515 517 S 3 516 516 517 514 S 4 515 515 515 514 V 1 515 516 517 516 V 2 514 517 515 515 V 3 516 517 516 515 V 4 514 515 516 515  5.10 265 S 1 265 267 266 266 S 2 265 267 266 266 S 3 266 266 265 265 S 4 265 266 265 265 V 1 265 267 265 268 V 2 265 265 267 268 V 3 265 268 265 266 V 4 265 267 267 266  6.5 161 S 1 164 163 162 162 S 2 162 163 163 164 S 3 162 163 161 164 S 4 164 161 162 163 V 1 161 164 163 161 V 2 161 162 163 163 V 3 162 163 161 163 V 4 162 162 161 163  A.5 236 S 1 239 238 239 238 S 2 238 236 238 237 S 3 239 237 237 237 S 4 236 238 236 237 V 1 239 236 237 239 V 2 236 239 237 238 V 3 236 237 239 237 V 4 238 239 239 237Table 10
Sampling phase: hardest instances for groups C, D, NRE, NRF, BRG, and NRH.
Hardest instances Transfer functions Discretization methods ID Optimum values Standard Complement Static probability Elitist B.5 72 S 1 75 75 73 74 S 2 73 74 75 72 S 3 75 74 74 73 S 4 75 73 72 74 V 1 73 73 74 75 V 2 74 72 72 74 V 3 74 74 72 75 V 4 75 74 72 75  C.5 215 S 1 217 215 216 216 S 2 217 217 218 218 S 3 216 216 218 217 S 4 215 218 217 217 V 1 216 216 218 217 V 2 215 216 217 216 V 3 216 217 215 216 V 4 216 218 215 217  D.5 61 S 1 61 61 61 63 S 2 62 61 63 64 S 3 64 63 64 63 S 4 64 61 63 62 V 1 61 61 61 64 V 2 63 62 64 64 V 3 61 63 62 62 V 4 62 63 62 62  NRE.5 28 S 1 30 29 31 30 S 2 29 31 28 31 S 3 31 28 30 28 S 4 28 31 28 28 V 1 30 31 31 29 V 2 29 29 29 28 V 3 29 30 28 28 V 4 31 30 30 28  NRF.5 13 S 1 14 15 15 14 S 2 15 16 14 14 S 3 16 13 14 15 S 4 14 16 14 15 V 1 16 14 16 16 V 2 15 16 15 14 V 3 13 16 14 14 V 4 13 14 15 13  NRG.5 168 S 1 170 171 169 171 S 2 170 171 171 171 S 3 169 168 168 169 S 4 170 171 171 169 V 1 168 169 171 169 V 2 170 169 170 171 V 3 170 171 171 168 V 4 171 169 170 169   NRH.5 55 S 1 58 57 58 56 S 2 56 58 58 55 S 3 58 56 57 57 S 4 57 57 55 57 V 1 58 57 58 55 V 2 55 55 56 57 V 3 55 58 56 58 V 4 56 56 56 56For group 4, the adaptive approach shows outstanding behaviour reaching 80% of the total optimum values, while BFO is the only one finding optimum values. However, if we compare the adaptive black hole with MIP, results illustrate the exact method is more efficient than the adapted algorithm in terms of solving time.Considering groups 5 and 6, we can observe the adaptive black hole algorithm is able of find all optimum values, in reduce solving times. Comparing results with others metaheuristics, we can state that our approach is better than them, outperforming the MIP in terms of solving time.Finally, for biggest instances—from group A to group NRH—the exact method MIP becomes incapable to find the solution (time-out). Figures4, 5, and 6 illustrate the comparative among the adaptive approach and approximate algorithms when they are solving hardest instances of each group.Figure 4
Algorithm comparisons for instances 4.10, 5.10, and 6.5.Figure 5
Algorithm comparisons for instances A.5, B.5, C.5, and D.5.Figure 6
Algorithm comparisons for instances NRE.5, NRF.5, NRG.5, and NRH.5.Figure 7
Sampling phase. Hardest instances for groups 4, 5, 6, A, B, and C.Figure 8
Sampling phase. Hardest instances for groups D, NRE, NRF, NRG, and NRH.If we observe instances 4.10 and 6.5, we can see the BH-AS is better than BCSO and BELA. Now, for instance D.5, BH-AS is better than all studied approximates techniques. Now, to solve NRG.5 results indicate that the BH-AS method is the best alternative. Last, if we compare BH-AS v/s MIP, we can say that our approach overcomes the exact method due to this is not able to solve the hardest groups.


## 5.1. Black Hole Algorithms Comparison

In this Section, we compare the proposed adaptive black hole algorithm with the basic black hole one. To the best of our knowledge, no autonomous search implementation on top of black hole has been proposed yet to include in the comparison.The algorithm implementation has been done using Java SE 7 and the experiments have been launched on a 2.3 Ghz Intel Core i3 with 4 GB RAM machine running Windows 7 (available athttps://goo.gl/AEYXJq). The initial parameter setting used is as follows: a population size of 40, 4000 iterations, a local search of 40 and 30 executions for each instance. Bold font and underlined row are used to present when the adaptive black hole algorithm outperforms their basic version.Table3 illustrates the results obtained for all instances from groups 4, 5, 6, A, B, C, and D. Regarding instance sets 4 and 6, the proposed adaptive approach in this work (BH-AS) improves dramatically the results in 50%, reaching 4 global optimums. Considering instance sets 5 and 6, we can observe that the basic black hole algorithm exhibits great performance achieving 80% of the optimal values. However, the adaptive process of the population size parameter improves results obtaining 2 more optimal values. Now, if we analyze instances from groups A, B, C, and D, we can see that again the basic black hole algorithm shows an outstanding efficiency to solve the set covering problem, solving to optimally 15 of 20 instances. Nevertheless, the adaptive approach shows that it can improve even more, finding one more optimal value for the instance C.1.Table 3
Computational results of groups 4, 5, 6, A, B, C, and D.
Instance Z o p t Black Hole Algorithm Basic BH-AS Z m i n RPD times (ms) Z m i n RPD times (ms) 4.1 429 430 0.002 1011.3 430 0.002 1181.2 4.2 512 512 0.000 1867.0 512 0.000 1926.0 4.3 516 516 0.000 2007.5 516 0.000 1957.1 4.4 494 495 0.002 1998.2 494 0.000 2108.1 4.5 512 514 0.004 2010.1 512 0.000 1992.3 4.6 560 560 0.000 2021.3 560 0.000 2102.2 4.7 430 430 0.000 2014.5 430 0.000 2032.2 4.8 492 494 0.004 2311.0 492 0.000 2202.6 4.9 641 644 0.005 2099.1 643 0.003 2109.9 4.10 514 515 0.002 1981.7 514 0.000 2017.1  5.1 253 253 0.000 2171.9 253 0.000 2001.7 5.2 302 305 0.010 1992.4 302 0.000 2071.2 5.3 226 228 0.000 2221.8 228 0.000 2221.8 5.4 242 242 0.000 2008.1 242 0.000 2191.2 5.5 211 211 0.000 2001.4 211 0.000 2127.4 5.6 213 213 0.000 2091.1 213 0.000 2222.1 5.7 293 293 0.000 2132.3 293 0.000 2332.1 5.8 288 288 0.000 2199.7 288 0.000 2339.2 5.9 279 279 0.000 2351.6 279 0.000 2271.2 5.10 265 265 0.000 1989.4 265 0.000 2057.7  6.1 138 140 0.014 2915.7 138 0.000 2915.7 6.2 146 147 0.007 2910.1 147 0.007 2791.6 6.3 145 145 0.000 2717.1 145 0.000 2751.7 6.4 131 131 0.000 2981.3 131 0.000 3003.7 6.5 161 161 0.000 3081.2 161 0.000 3038.3  A.1 253 253 0.000 3009.5 253 0.000 2967.1 A.2 252 253 0.004 3033.2 253 0.004 2983.2 A.3 232 233 0.004 2991.9 233 0.004 3104.9 A.4 234 234 0.000 3091.2 234 0.000 3111.1 A.5 236 236 0.000 3001.4 236 0.000 3012.3  B.1 69 69 0.000 3223.5 69 0.000 3122.1 B.2 76 76 0.000 3011.3 76 0.000 3183.6 B.3 80 80 0.000 3253.3 80 0.000 3452.0 B.4 79 79 0.000 3212.1 79 0.000 3419.1 B.5 72 72 0.000 3433.3 72 0.000 3501.0  C.1 227 229 0.009 3271.1 227 0.000 3397.9 C.2 219 219 0.000 3090.4 219 0.000 3291.1 C.3 243 245 0.008 3194.6 245 0.008 3229.2 C.4 219 219 0.000 3230.2 219 0.000 3323.1 C.5 215 215 0.000 2979.6 215 0.000 3111.8  D.1 60 60 0.000 5821.3 60 0.000 6021.0 D.2 66 67 0.015 6010.2 67 0.015 6094.1 D.3 72 73 0.014 6071.2 73 0.014 6147.7 D.4 62 62 0.000 6313.4 62 0.000 6511.6 D.5 61 61 0.000 6831.4 61 0.000 6712.2Table4 presents the results obtained for instances from groups NRE, NRF, NRG, and NRH. If we consider that the basic black hole algorithm reaches 3 optimal values from 20, there is a wide margin to improve. Taking into account the fact that the autoadaptive methods outperform the basic BH algorithm in 11 of 17 possible instances and 2 of them are global optima, we can say that BH-AS performs significantly better than the basic version.Table 4
Computational results of groups NRE, NRF, NRG, and NRH.
Instance Z o p t Black Hole Algorithm Basic BH-AS Z m i n RPD times (ms) Z m i n RPD times (ms) NRE.1 29 30 0.034 6200.0 29 0.000 6135.0 NRE.2 30 31 0.033 6235.4 31 0.033 6115.1 NRE.3 27 28 0.037 5988.3 28 0.037 5991.9 NRE.4 28 29 0.036 6875.2 28 0.000 7081.0 NRE.5 28 28 0.000 7298.1 28 0.000 7191.1  NRF.1 14 14 0.000 6788.4 14 0.000 7118.5 NRF.2 15 15 0.000 8313.4 15 0.000 8212.1 NRF.3 14 17 0.214 8934.4 16 0.143 9293.8 NRF.4 14 16 0.143 7746.3 14 0.000 8023.3 NRF.5 13 14 0.077 7021.1 14 0.077 7220.2  NRG.1 176 182 0.034 7143.5 179 0.017 7644.8 NRG.2 154 160 0.039 7948.0 158 0.026 8584.5 NRG.3 166 170 0.024 8771.8 169 0.018 9874.0 NRG.4 168 170 0.012 8123.7 170 0.012 8919.2 NRG.5 168 170 0.012 9013.4 168 0.000 9921.2  NRH.1 63 66 0.048 15114.6 65 0.032 17911.2 NRH.2 63 67 0.063 16343.4 67 0.063 19733.4 NRH.3 59 64 0.085 19243.7 64 0.085 21840.3 NRH.4 58 64 0.103 18241.6 63 0.086 21421.7 NRH.5 55 63 0.145 24442.6 62 0.127 22242.5Figure3 illustrates convergence charts for the hardest instances of each instance group. Here, we observe that for the 4 group the convergence of the BH-AS is clearly faster than the basic algorithm. For the group 5, the BH-AS begins with a bad quality solution but at the middle of the process improves its performance outperforming the basic BHA similar behaviour can be seen for the NRE and NRH group. The performance of instances from groups 6, A, B, C, and D is similar keeping all of them an early convergence. Finally, for benchmarks from groups NRF and NRG, the behaviour of BH-AS is clearly earlier than its competitor.Figure 3
Convergence charts for the hardest instances of each instance group.Now, if we regard solving times required for reaching the solutions, we may observe that times are very similar for the two algorithms. However, we must consider that BH-AS need the computation of the adaptive process and is able to outperform the basic BH in terms of optimum values reached. We can observe also a small difference in terms of solving times in favor of the BH-AS with respect to BH.


## 5.2. BH-AS v/s Original Approach

After to analyze the exhibited efficiency for BH-AS and the basic algorithm for solving the set covering problem, we have observed that the variation is minimal. It is not possible to state which technique is the best. However, in order to show a significant difference between the adaptive approach and the original black hole algorithm, we perform a contrast statistical test for each instance through theKolmogorov-Smirnov-Lilliefors to determine the independence of samples [64] andWilcoxon's signed rank [65] to compare statistically the results.For both tests, we consider a hypothesis evaluation, which is analyzed assuming ap_value of 0.05—accuracy—i.e., smaller values than 0.05, determines that the corresponding hypothesis cannot be assumed. Both tests were conducted usingGNU Octave  (available at http://goo.gl/jtHn8i).The first test allows us to analyze the independence of samples. For that, we run the algorithm 30 times for each instance and then, we apply the test. According to obtained values, we can decide if samples follow a normal distribution or they are independent. To proceed, we propose the following hypotheses:(i)
H0 states that Zmin follows a normal distribution.(ii)
H1 states the opposite.The conducted test has yieldedp_value lower than 0.05; therefore H0 cannot be assumed.Then, as samples are independent and cannot be assumed that 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 nonparametric test for evaluating the heterogeneity of samples. For that we use theWilcoxon’s signed rank test. This is a paired test that compare the medians of two distributions. To proceed, we propose the following new hypotheses:(i)
H0: Z~min achieved by basic black hole algorithm <Z~min achieved by BH-AS.(ii)
H1 states the opposite.Table5 compares the approaches for all tested instances via theWilcoxon’s signed rank test. As the significance level is also established to 0.05, smaller values that 0.05 defines that H0 cannot be assumed. Again, bold font and underlined row are used for a winner value of the metaheuristic stated in the column of the table, e.g., for instance 4.1, BH-AS is better than basic algorithm as its value is lower than 0.05, then H0 cannot be assumed.Table 5
Statistical test.
Instance 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10  Basic – – 0.01 – – – 0.02 – – –  BH-AS 0.01 – – 0.01 0.01 – – 0.04 0.01 0.01  Instance 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 5.10  Basic – – 0.01 – – – – – – 0.04  BH-AS – 0.02 – – 0.03 0.01 0.05 – – –  Instance 6.1 6.2 6.3 6.4 6.5 A.1 A.2 A.3 A.4 A.5  Basic – – – – – 0.02 0.05 – – –  BH-AS 0.01 – 0.01 – 0.01 – – 0.01 0.01 0.01  Instance B.1 B.2 B.3 B.4 B.5 C.1 C.2 C.3 C.4 C.5  Basic – – – 0.03 0.02 – – – 0.01 –  BH-AS – 0.01 0.01 – – – 0.05 0.01 – 0.04  Instance D.1 D.2 D.3 D.4 D.5 NRE.1 NRE.2 NRE.3 NRE.4 NRE.5  Basic – – – – – – 0.03 – – 0.01  BH-AS 0.02 – – 0.01 0.03 0.01 – 0.01 0.04 –  Instance NRF.1 NRF.2 NRF.3 NRF.4 NRF.5 NRG.1 NRG.2 NRG.3 NRG.4 NRG.5  Basic – 0.01 – – – – – – – –  BH-AS 0.03 – 0.03 0.01 0.03 0.01 0.03 0.01 0.01 0.02  Instance NRH.1 NRH.2 NRH.3 NRH.4 NRH.5  Basic – – – – –  BH-AS 0.03 – 0.01 0.03 0.05According to results, forp_values lower than 0.05 for black hole optimization are 12 and for BH-AS are 40. The rest does not provide significant information. This results illustrating that the performance of BH-AS is better than the original approach.


## 5.3. BH-AS v/s Other Optimization Techniques

To evidence the performance of our adaptive approach, we perform a comparison with different approximation techniques: binary cat swarm optimization (BCSO) [41], binary firefly optimization (BFO) [40], binary shuffled frog leaping algorithm (BSFLA) [42], binary artificial bee colony (BABC) [43], and binary electromagnetism-like algorithm (BELA) [66].We additionally incorporate a comparative by using Mixed Integer Linear Programming (MIP) as exact solving method implemented on MiniZinc G12 MIP. With the solver, the instances are solved to a maximum time of 8 hours. If no solution is found at this point the problem is set to t.o. (time-out).Tables6, 7, and 8 illustrate that the proposed approach is able to reach competitive results in contrast to those modern optimization techniques.Table 6
Comparison results for instance set of groups 4, 5, 6, and A.
Instance 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10  Z o p t 429 512 516 494 512 560 430 492 641 514  BH-AS Z m i n 430 512 516 494 512 560 430 492 643 514 Z a v g 430 512 516 501 519 562 432 495 648 517 R P D 0.002 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.003 0.000 T i m e   ( m s ) 1811.2 1926.0 1957.1 2108.1 1992.3 2102.2 2032.2 2202.6 2109.9 2017.1  BCSO Z m i n 459 570 590 547 545 637 462 546 711 537 Z a v g 480 594 607 578 554 650 467 567 725 552 R P D 7 11.3 14.3 10.7 6.4 13.8 7.4 11 10.9 4.5  BFO Z m i n 429 517 519 495 514 563 430 497 655 519 Z a v g 430 517 522 497 515 565 430 499 658 523 R P D 0 0.97 0.58 0.2 0.39 0.53 0 1.01 2.18 0.97  BSFLA Z m i n 430 516 520 501 514 563 431 497 656 518 Z a v g 430 518 520 504 514 563 432 499 656 519 R P D 0.23 0.78 0.78 1.42 0.39 0.54 0.23 1.02 2.34 0.78  BELA Z m i n 447 559 537 527 527 607 448 509 682 571 Z a v g 448 559 539 530 529 608 449 512 682 571 R P D 4.20 9.18 4.07 6.68 2.93 8.39 4.19 3.46 6.40 11.09  BABC Z m i n 430 513 519 495 514 561 431 493 649 517 Z a v g 430 513 521 496 517 565 434 494 651 519 R P D 0.23 0.20 0.58 0.20 0.39 0.18 0.23 0.20 0.93 0.58  MIP Z m i n 429 512 516 494 512 560 430 492 641 514 T i m e   ( m s ) 705 912 788 934 654 701 693 712 917 868  Instance 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 5.10  Z o p t 253 302 226 242 211 213 293 288 279 265  BH-AS Z m i n 253 302 226 242 211 213 293 288 279 265 Z a v g 253 302 226 242 211 213 293 288 279 265 R P D 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 T i m e   ( m s ) 2001.7 2071.2 2221.8 2191.2 2127.4 2222.1 2332.1 2339.2 2271.2 2057.7  BCSO Z m i n 279 339 247 251 230 232 332 320 295 285 Z a v g 287 340 251 253 230 243 338 330 297 287 R P D 10.3 12.3 9.3 3.7 9 8.9 13.3 11.1 5.7 7.5  BFO Z m i n 257 309 229 242 211 213 298 291 284 268 Z a v g 260 311 233 242 213 213 301 292 284 270 R P D 1.58 2.31 1.32 0 0 0 1.7 1.04 1.79 1.13  BSFLA Z m i n 254 307 228 242 211 213 297 291 281 265 Z a v g 255 307 230 242 213 214 299 293 283 266 R P D 0.4 1.66 0.88 0 0 0 1.37 1.04 0.72 0  BELA Z m i n 280 318 242 251 225 247 316 315 314 280 Z a v g 281 321 240 252 227 248 317 317 315 282 R P D 10.67 5.30 7.08 3.72 6.64 15.96 7.85 9.38 12.54 5.66  BABC Z m i n 254 309 229 242 211 214 298 289 280 267 Z a v g 255 309 233 245 212 214 301 291 281 270 R P D 0.40 2.32 1.33 0 0 0.47 1.71 0.35 0.36 0.75  MIP Z m i n 253 302 226 242 211 213 293 288 279 265 T i m e   ( m s ) 4776 3882 4332 4899 4771 4329 3887 5191 4659 4879  Instance 6.1 6.2 6.3 6.4 6.5 A.1 A.2 A.3 A.4 A.5  Z o p t 138 146 145 131 161 253 252 232 234 236   BH-AS Z m i n 138 147 145 131 161 253 253 233 234 236 Z a v g 142 150 147 131 161 234 253 234 234 236 R P D 0.000 0.007 0.000 0.000 0.000 0.000 0.004 0.000 0.000 0.000 T i m e   ( m s ) 2915.7 2791.6 2751.7 3003.7 3038.3 2967.1 2983.2 3104.9 3111.1 3012.3  BCSO Z m i n 151 152 160 138 169 286 274 257 248 244 Z a v g 160 157 164 142 173 287 276 263 251 244 R P D 9.4 4.1 10.3 5.3 5 13 8.7 10.8 6 3  BFO Z m i n 138 147 147 131 164 255 259 238 235 236 Z a v g 140 149 150 131 164 256 261 240 237 237 R P D 0 0.68 1.37 0 1.86 0.79 2.77 2.58 0.42 0  BSFLA Z m i n 140 147 147 131 166 255 260 237 235 236 Z a v g 141 147 148 133 169 258 260 239 238 239 R P D 1.45 0.68 1.38 0 3.11 0.79 3.17 2.16 0.43 0  BELA Z m i n 152 160 160 140 184 261 279 252 250 241 Z a v g 152 161 163 142 187 264 281 253 252 243 R P D 10.14 9.59 10.34 6.87 14.29 3.16 10.71 8.62 6.84 2.12  BABC Z m i n 142 147 148 131 165 254 257 235 236 236 Z a v g 143 150 149 133 167 254 259 238 237 238 R P D 2.90 0.68 2.07 0 2.48 0.40 1.98 1.29 0.85 0  MIP Z m i n 138 146 145 131 161 – – – – – T i m e   ( m s ) 1445 2236 1885 2385 2187 t.o. t.o. t.o. t.o. t.o.Table 7
Computational results for instances set of groups B, C, D, NRE, NRF, and NRG.
Instance B.1 B.2 B.3 B.4 B.5 C.1 C.2 C.3 C.4 C.5  Z o p t 69 76 80 79 72 227 219 243 219 215  BH-AS Z m i n 69 76 80 79 72 227 219 245 219 215 Z a v g 70 77 81 81 73 231 220 246 219 216 R P D 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.008 0.000 0.000 T i m e 3122.1 3183.6 3452.0 3419.1 3501.0 3397.9 3291.1 3229.2 3323.1 3111.8  BCSO Z m i n 79 86 85 89 73 242 240 277 250 243 Z a v g 79 89 85 89 73 242 241 278 250 244 R P D 14.5 13.2 6.3 12.7 1.4 6.6 9.6 14 12.3 13  BFO Z m i n 71 78 80 80 72 230 223 253 225 217 Z a v g 72 78 80 81 73 232 224 254 227 219 R P D 2.89 2.63 0 1.26 0 1.32 1.82 4.11 2.73 0.93  BSFLA Z m i n 70 76 80 79 72 229 223 253 227 217 Z a v g 70 77 80 80 73 231 225 253 228 218 R P D 1.45 0 0 0 0 0.88 1.83 4.12 3.65 0.93  BELA Z m i n 86 88 85 84 78 237 237 271 246 224 Z a v g 87 88 87 88 81 238 239 271 248 225 R P D 24.64 15.79 6.25 6.33 8.33 4.41 8.22 11.52 12.33 4.19  BABC Z m i n 70 78 80 80 72 231 222 254 231 216 Z a v g 70 79 80 81 74 233 223 255 233 217 R P D 1.45 2.63 0 1.27 0 1.76 1.37 4.53 5.48 0.47  MIP Z m i n – – – – – – – – – – T i m e   ( m s ) t.o. t.o. t.o. t.o. t.o. t.o. t.o. t.o. t.o. t.o.  Instance D.1 D.2 D.3 D.4 D.5 NRE.1 NRE.2 NRE.3 NRE.4 NRE.5  Z o p t 60 66 72 62 61 29 30 27 28 28  BH-AS Z m i n 60 67 73 62 61 29 31 28 29 28 Z a v g 60 67 73 62 61 29 31 28 28 28 R P D 0.000 0.015 0.014 0.000 0.000 0.000 0.033 0.037 0.000 0.000 T i m e 6021.0 6094.1 6147.7 6511.6 6712.2 6200.0 6115.1 5991.9 7081.0 7191.1  BCSO Z m i n 65 70 79 64 65 29 34 31 32 30 Z a v g 66 70 81 67 66 30 34 32 33 30 R P D 8.3 6.1 9.7 3.2 6.6 0 13.3 14.8 14.3 7.1  BFO Z m i n 60 68 75 62 63 29 32 29 29 29 Z a v g 61 68 77 62 63 31 32 30 31 29 R P D 0 3.03 4.16 0 3.27 0 6.66 7.4 3.57 3.57  BSFLA Z m i n 60 67 75 63 63 29 31 28 29 28 Z a v g 62 68 77 65 66 29 32 28 30 31 R P D 0 1.52 4.17 1.61 3.28 0 3.33 3.7 3.57 0  BELA Z m i n 62 73 79 67 66 30 35 34 33 30 Z a v g 62 74 81 69 67 31 35 34 34 31 R P D 3.33 10.61 9.72 8.06 8.20 3.45 16.67 25.93 17.86 7.14  BABC Z m i n 60 68 76 63 63 29 32 29 29 29 Z a v g 61 68 77 65 66 33 32 31 30 32 R P D 0 3.03 5.56 1.61 3.28 0 6.67 7.41 3.57 3.57  MIP Z m i n – – – – – – – – – – T i m e   ( m s ) t.o. t.o. t.o. t.o. t.o. t.o. t.o. t.o. t.o. t.o.  Instance NRF.1 NRF.2 NRF.3 NRF.4 NRF.5 NRG.1 NRG.2 NRG.3 NRG.4 NRG.5  Z o p t 14 15 14 14 13 176 154 166 168 168   BH-AS Z m i n 14 15 16 14 14 179 158 169 170 168 Z a v g 15 16 16 16 15 181 160 169 171 169 R P D 0.000 0.000 0.143 0.000 0.077 0.017 0.026 0.018 0.012 0.000 T i m e 7118.5 8212.1 9293.8 8023.3 7220.2 7494.4 8584.5 9874.0 8919.2 9921.2  BCSO Z m i n 17 18 17 17 15 190 165 187 179 181 Z a v g 17 18 17 17 16 193 166 188 183 184 R P D 21.4 20 21.4 21.4 15.4 8 7.1 20.6 6.5 7.7  BFO Z m i n 15 16 16 15 15 185 161 175 176 177 Z a v g 17 16 17 18 19 191 163 177 176 181 R P D 7.14 6.66 14.28 7.14 15.38 5.11 4.54 5.42 4.76 5.35  BSFLA Z m i n 15 15 16 15 15 182 161 173 173 174 Z a v g 15 15 17 16 17 183 161 174 177 174 R P D 7.14 0 14.29 7.14 15.38 3.41 4.55 4.22 2.98 3.57  BELA Z m i n 17 18 17 17 16 194 176 184 196 198 Z a v g 17 18 18 19 17 196 176 185 197 199 R P D 21.43 20 21.43 21.43 23.08 10.23 14.29 10.84 16.67 17.86  BABC Z m i n 14 16 16 15 15 183 162 174 175 179 Z a v g 15 16 17 17 16 184 163 175 177 181 R P D 0 6.67 14.29 7.14 15.38 3.98 5.19 4.82 4.17 6.55  MIP Z m i n – – – – – – – – – – T i m e   ( m s ) t.o. t.o. t.o. t.o. t.o. t.o. t.o. t.o. t.o. t.o.Table 8
Computational results for instances of group NRH.
Instance NRH.1 NRH.2 NRH.3 NRH.4 NRH.5  Z o p t 63 63 59 58 55  BH-AS Z m i n 65 67 64 63 62 Z a v g 67 68 65 64 62 R P D 0.032 0.063 0.085 0.086 0.127 T i m e 17911.2 19733.4 21840.3 21421.7 22242.5  BCSO Z m i n 70 67 68 66 61 Z a v g 71 67 70 67 62 R P D 11.1 6.3 15.3 13.8 10.9  BFO Z m i n 69 66 65 63 59 Z a v g 70 66 67 65 60 R P D 9.52 4.76 10.16 6.77 7.27  BSFLA Z m i n 68 66 62 63 59 Z a v g 69 66 63 64 61 R P D 7.94 4.76 5.08 8.62 7.27  BELA Z m i n 70 71 68 70 69 Z a v g 71 71 70 72 69 R P D 11.11 12.70 15.25 20.69 25.45  BABC Z m i n 70 69 66 64 60 Z a v g 71 72 67 64 61 R P D 11.11 9.52 11.86 10.34 9.09  MIP Z m i n – – – – – T i m e   ( m s ) t.o. t.o. t.o. t.o. t.o.Table 9
Sampling phase: hardest instances for groups 4, 5, 6, A, and B.
Hardest instances Transfer functions Discretization methods ID Optimum values Standard Complement Static probability Elitist 4.10 514 S 1 515 514 516 515 S 2 516 515 515 517 S 3 516 516 517 514 S 4 515 515 515 514 V 1 515 516 517 516 V 2 514 517 515 515 V 3 516 517 516 515 V 4 514 515 516 515  5.10 265 S 1 265 267 266 266 S 2 265 267 266 266 S 3 266 266 265 265 S 4 265 266 265 265 V 1 265 267 265 268 V 2 265 265 267 268 V 3 265 268 265 266 V 4 265 267 267 266  6.5 161 S 1 164 163 162 162 S 2 162 163 163 164 S 3 162 163 161 164 S 4 164 161 162 163 V 1 161 164 163 161 V 2 161 162 163 163 V 3 162 163 161 163 V 4 162 162 161 163  A.5 236 S 1 239 238 239 238 S 2 238 236 238 237 S 3 239 237 237 237 S 4 236 238 236 237 V 1 239 236 237 239 V 2 236 239 237 238 V 3 236 237 239 237 V 4 238 239 239 237Table 10
Sampling phase: hardest instances for groups C, D, NRE, NRF, BRG, and NRH.
Hardest instances Transfer functions Discretization methods ID Optimum values Standard Complement Static probability Elitist B.5 72 S 1 75 75 73 74 S 2 73 74 75 72 S 3 75 74 74 73 S 4 75 73 72 74 V 1 73 73 74 75 V 2 74 72 72 74 V 3 74 74 72 75 V 4 75 74 72 75  C.5 215 S 1 217 215 216 216 S 2 217 217 218 218 S 3 216 216 218 217 S 4 215 218 217 217 V 1 216 216 218 217 V 2 215 216 217 216 V 3 216 217 215 216 V 4 216 218 215 217  D.5 61 S 1 61 61 61 63 S 2 62 61 63 64 S 3 64 63 64 63 S 4 64 61 63 62 V 1 61 61 61 64 V 2 63 62 64 64 V 3 61 63 62 62 V 4 62 63 62 62  NRE.5 28 S 1 30 29 31 30 S 2 29 31 28 31 S 3 31 28 30 28 S 4 28 31 28 28 V 1 30 31 31 29 V 2 29 29 29 28 V 3 29 30 28 28 V 4 31 30 30 28  NRF.5 13 S 1 14 15 15 14 S 2 15 16 14 14 S 3 16 13 14 15 S 4 14 16 14 15 V 1 16 14 16 16 V 2 15 16 15 14 V 3 13 16 14 14 V 4 13 14 15 13  NRG.5 168 S 1 170 171 169 171 S 2 170 171 171 171 S 3 169 168 168 169 S 4 170 171 171 169 V 1 168 169 171 169 V 2 170 169 170 171 V 3 170 171 171 168 V 4 171 169 170 169   NRH.5 55 S 1 58 57 58 56 S 2 56 58 58 55 S 3 58 56 57 57 S 4 57 57 55 57 V 1 58 57 58 55 V 2 55 55 56 57 V 3 55 58 56 58 V 4 56 56 56 56For group 4, the adaptive approach shows outstanding behaviour reaching 80% of the total optimum values, while BFO is the only one finding optimum values. However, if we compare the adaptive black hole with MIP, results illustrate the exact method is more efficient than the adapted algorithm in terms of solving time.Considering groups 5 and 6, we can observe the adaptive black hole algorithm is able of find all optimum values, in reduce solving times. Comparing results with others metaheuristics, we can state that our approach is better than them, outperforming the MIP in terms of solving time.Finally, for biggest instances—from group A to group NRH—the exact method MIP becomes incapable to find the solution (time-out). Figures4, 5, and 6 illustrate the comparative among the adaptive approach and approximate algorithms when they are solving hardest instances of each group.Figure 4
Algorithm comparisons for instances 4.10, 5.10, and 6.5.Figure 5
Algorithm comparisons for instances A.5, B.5, C.5, and D.5.Figure 6
Algorithm comparisons for instances NRE.5, NRF.5, NRG.5, and NRH.5.Figure 7
Sampling phase. Hardest instances for groups 4, 5, 6, A, B, and C.Figure 8
Sampling phase. Hardest instances for groups D, NRE, NRF, NRG, and NRH.If we observe instances 4.10 and 6.5, we can see the BH-AS is better than BCSO and BELA. Now, for instance D.5, BH-AS is better than all studied approximates techniques. Now, to solve NRG.5 results indicate that the BH-AS method is the best alternative. Last, if we compare BH-AS v/s MIP, we can say that our approach overcomes the exact method due to this is not able to solve the hardest groups.


## 6. Conclusions and Future Work

In this paper, we have presented an adaptive approach for black hole algorithm to solve different instances of the set covering problem. This approach is based on adaptive for population size parameter which is valuated before the run of the metaheuristic. To this end, we use autonomous search which is a particular case of adaptive systems that improve their solving performance by modifying and adjusting themselves to the problem at hand, either by adaptation or supervised adaptation. We have added to the core algorithm an effective preprocessing process that allows filtering and discarding values leading to unfeasible solutions. On the other hand, we include a set of binarization strategies to adapt the black hole algorithm to binary domain. We have tested 65 nonunicost instances from the Beasleys OR-Library where several global optimum values which were not reached using by the basic black algorithm were achieved via the autoadaptive approach. We have also compared the proposed adaptive approach by using a nonparametric statistical tests and the results are conclusive.As future work, we plan to experiment autoadaptive approaches in recent bioinspired algorithms and to provide a larger comparison of techniques for solving the set covering problem. The integration of autonomous search can led the research towards new study lines, such as dynamically selecting the best binarization strategy during solving according to performance indicators as analogously studied in [67, 68].



---

*Source: 2183214-2018-10-16.xml*