A Meta-Optimization Approach to Solve the Set Covering Problem

Un Enfoque de Meta-Optimización para Resolver el Problema de Cobertura de Conjunto

  • Gino Astorga Pontificia Universidad Católica de Valparaíso
  • Broderick Crawford Pontificia Universidad Católica de Valparaíso
  • Ricardo Soto Pontificia Universidad Católica de Valparaíso
  • Eric Monfroy Universite de Nantes
  • José García Pontificia Universidad Católica de Valparaíso
  • Enrique Cortes Universidad de Playa Ancha

Abstract (en_US)

Context: In the industry the resources are increasingly scarce. For this reason, we must make a good
use of it. Being the optimization tools, a good alternative that it is necessary to bear in mind. A realworld
problem is the facilities location being the Set Covering Problem, one of the most used models.
Our interest, it is to find solution alternatives to this problem of the real-world using metaheuristics.

Method: One of the main problems which we turn out to be faced on having used metaheuristic is the
difficulty of realizing a correct parametrization with the purpose to find good solutions. This is not an
easy task, for which our proposal is to use a metaheuristic that allows to provide good parameters to
another metaheuristics that will be responsible for resolving the Set Covering Problem.

Results: To prove our proposal, we use the set of 65 instances of OR-Library which also was compared
with other recent algorithms, used to solve the Set Covering Problem.

Conclusions: Our proposal has proved to be very effective able to produce solutions of good quality
avoiding also have to invest large amounts of time in the parametrization of the metaheuristic responsible
for resolving the problem.

Abstract (es_ES)

Contexto: En la industria los recursos son cada vez más escasos. Por esta razón debemos hacer un buen uso de ellos.Siendo las herramientas de optimización una buena alternativa que se debe tener presente. Un problema del mundo real lo contituye la ubicación de instalaciones siendo el Problema de Cobertura de Conjuntos uno de los modelos más utilizados. Nuestro interés, es encontrar alternativas de solución a este problema de la vida-real utilizando metaheuristicas.

Método: Uno de los principales problemas a que nos vemos enfrentados al utilizar metaheurísticas es la dificultad de realizar una correcta parametrización con el objetivo de encontrar buenas soluciones. Esta no es una tarea fácil, para lo cual nuestra propuesta es utilizar una metaheurística que permita proporcionar buenos parametros a otra metaheurstica que será la encargada de resolver el Problema de Cobertura de Conjuntos.

Resultados: Para probar nuestra propuesta, utilizamos el set de 65 instancias de OR-Library el cual además fue comparado con otros recientes algoritmos utilizados para resolver el Problema de Cobertura de Conjuntos.


Conclusiones: Nuestra propuesta a demostrado ser muy efectiva logrando producir soluciones de buena calidad evitando además que se tenga que invertir gran cantidad de tiempo en la parametrización de la metaheurística encargada de resolver el problema.

Downloads

Download data is not yet available.

References

C. Ansótegui, M. Sellmann, and K. Tierney. A gender-based genetic algorithm for the automatic configuration of algorithms. In International Conference on Principles and Practice of Constraint Programming, pages 142–157. Springer, 2009.

S. Balaji and N. Revathi. A new approach for solving set covering problem using jumping particle swarm

optimization method. Natural Computing, 15(3):503–517, 2016.

M. Birattari and M. Dorigo. The problem of tuning metaheuristics as seen from a machine learning perspective. 2004.

B. Crawford, R. Soto, G. Astorga, J. García, C. Castro, and F. Paredes. Putting continuous metaheuristics to work in binary search spaces. Complexity, 2017, 2017.

B. Crawford, R. Soto, N. Berríos, F. Johnson, F. Paredes, C. Castro, and E. Norero. A binary cat swarm optimization algorithm for the non-unicost set covering problem. Mathematical Problems in Engineering, 2015,

B. Crawford, R. Soto, R. Cuesta, and F. Paredes. Application of the artificial bee colony algorithm for solving

the set covering problem. The Scientific World Journal, 2014(189164):1–8, April 2014.

B. Crawford, R. Soto, E. Monfroy, G. Astorga, J. Garc´ıa, and E. Cortes. A meta-optimization approach for

covering problems in facility location. In Workshop on Engineering Applications, pages 565–578. Springer,

B. Crawford, R. Soto, M. Olivares-Suárez, and F. Paredes. A binary firefly algorithm for the set covering problem. In 3rd Computer Science On-line Conference 2014 (CSOC 2014), volume 285 of Advances in Intelligent Systems and Computing, pages 65–73. Springer International Publishing, 2014.

B. Crawford, R. Soto, M. Olivares-Surez, F. Paredes, and F. Johnson. Binary firefly algorithm for the set covering problem. In 2014 9th Iberian Conference on Information Systems and Technologies (CISTI), pages 1–5, June 2014.

B. Crawford, R. Soto, W. Palma, F. Johnson, F. Paredes, and E. Olguín. A 2-level approach for the set covering problem: Parameter tuning of artificial bee colony algorithm by using genetic algorithm. In Y. Tan, Y. Shi,and C. Coello, editors, Advances in Swarm Intelligence, volume 8794, pages 189–196. Springer International Publishing, 2014.

B. Crawford, R. Soto, C. Peña, W. Palma, F. Johnson, and F. Paredes. Solving the set covering problem with a shuffled frog leaping algorithm. In 7th Asian Conference, ACIIDS 2015, Bali, Indonesia, March 23-25, 2015, Proceedings, Part II, volume 9012 of Lecture Notes in Computer Science, pages 41–50. Springer International Publishing, 2015.

B. Crawford, C. Valenzuela, R. Soto, E. Monfroy, and F. Paredes. Parameter tuning of metaheuristics using

metaheuristics. Advanced Science Letters, 19(12):3556–3559, 2013.

R. Cuesta, B. Crawford, R. Soto, and F. Paredes. An artificial bee colony algorithm for the set covering problem. In 3rd Computer Science On-line Conference 2014 (CSOC 2014), volume 285 of Advances in Intelligent Systems and Computing, pages 53–63. Springer International Publishing, 2014.

T. Drezner, Z. Drezner, and Z. Goldstein. A stochastic gradual cover location problem. Naval Research Logistics (NRL), 57(4):367–372, 2010.

G. Franceschini and S. Macchietto. Model-based design of experiments for parameter precision: State of the art. Chemical Engineering Science, 63(19):4846–4872, 2008.

J. García, B. Crawford, R. Soto, C. Carlos, and F. Paredes. A k-means binarization framework applied to

multidimensional knapsack problem. Applied Intelligence, pages 1–24, 2017.

J. García, B. Crawford, R. Soto, and P. García. A multi dynamic binary black hole algorithm applied to set

covering problem. In International Conference on Harmony Search Algorithm, pages 42–51. Springer, 2017.

J. J. Grefenstette. Optimization of control parameters for genetic algorithms. IEEE Transactions on systems, man, and cybernetics, 16(1):122–128, 1986.

D. Karaboga. An idea based on honey bee swarm for numerical optimization. Technical report, Technical

report-tr06, Erciyes university, engineering faculty, computer engineering department, 2005.

D. Karaboga. An idea based on honey bee swarm for numerical optimization. Technical Report TR06. Computer Engineering Department, Erciyes University, Turkey, 2005.

D. Karaboga and B. Basturk. A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. Journal Global Optimization, 39(3):459–471, 2007.

D. Karaboga, B. Gorkemli, C. Ozturk, and N. Karaboga. A comprehensive survey: artificial bee colony (ABC) algorithm and applications. Artificial Intelligence Review, 42(3):21–57, 2014.

M. López-Ibánez, J. Dubois-Lacoste, L. P. Cáceres, M. Birattari, and T. Sttzle. The irace package: Iterated

racing for automatic algorithm configuration. Operations Research Perspectives, 3:43 – 58, 2016.

Y. Lu and F. J. Vasko. An or practitioner’s solution approach for the set covering problem. International Journal of Applied Metaheuristic Computing (IJAMC), 6(4):1–13, 2015.

H. B. Mann and D. R. Whitney. On a test of whether one of two random variables is stochastically larger than the other. The annals of mathematical statistics, pages 50–60, 1947.

L. Santana, E. Ramiro, and J. d. J. Romero Carvajal. A hybrid column generation and clustering approach to the school bus routing problem with time windows. Ingeniería, 20(1):101–117, 2015.

D. Schilling, V. Jayaraman, and R. Barkhi. A review of covering problem in facility location. Location Science, Vol. 1(1):25–55, 1993.

B. Senthilkumar, T. Kannan, and R. Madesh. Optimization of flux-cored arc welding process parameters by

using genetic algorithm. The International Journal of Advanced Manufacturing Technology, 93(1-4):35–41,2017.

H. Shah-Hosseini. Intelligent water drops algorithm: A new optimization method for solving the multiple

knapsack problem. International Journal of Intelligent Computing and Cybernetics, 1(2):193–212, 2008.

S. S. Shapiro and M. B. Wilk. An analysis of variance test for normality (complete samples). Biometrika,

(3/4):591–611, 1965.

A. Singh. An artificial bee colony algorithm for the leaf-constrained minimum spanning tree problem. Applied Soft Computing, 9(2):625–631, 2009.

R. Soto, B. Crawford, A.Mu˜noz, F. Johnson, and F. Paredes. Pre-processing, repairing and transfer functions can help binary electromagnetism-like algorithms. In Artificial Intelligence Perspectives and Applications, volume 347 of Advances in Intelligent Systems and Computing, pages 89–97. Springer International Publishing, 2015.

R. Soto, B. Crawford, R. Olivares, J. Barraza, I. Figueroa, F. Johnson, F. Paredes, and E. Olgu´ın. Solving the non-unicost set covering problem by using cuckoo search and black hole optimization. Natural Computing,

pages 1–17, 2017.

C. Toregas, R. Swain, C. ReVelle, and L. Bergman. The location of emergency service facilities. Operations

Research, 19(6):1363–1373, 1971.

How to Cite
Astorga, G., Crawford, B., Soto, R., Monfroy, E., García, J., & Cortes, E. (2018). A Meta-Optimization Approach to Solve the Set Covering Problem. Ingeniería, 23(3). https://doi.org/10.14483/23448393.13247
Published: 2018-11-05
Section
Computational Intelligence

Introduction

The Set Covering Problem (SCP), introduced in [1], is an important problem NP-Hard present in the current industry. The following applications for covering problems were mentioned in [2]: Bus stop location, Fire equipment allocation, Fire company relocation, Fire service sitting and Terrain visibility. Also, in [3] were presented some general applications of the gradual covering problem: The delivery problem; Competitive location; Dense competition; The radio, TV, or cellular transmitter problem and Medical facility location problem.

Mathematically SCP can be defined as: Let A = (a ij ) be an m-row, n-column, zero-one matrix. We say that a column j can cover a row i if aij = 1. Each column j is associated with a non-negative real cost c j . be the row set and column set, respectively. The SCP calls for a minimum cost subset , such that each row is covered by at least one column. A mathematical model for the SCP is stated in the following:

subject to

If the costs are equal for each , the problem is referred to as the unicost SCP, otherwise, the problem is called the weighted or non-unicost SCP, where the subset of columns covering row the subset of rows covered by column j .

The goal is to minimize the sum of the costs of the selected columns, where if the column j is in the solution, 0 otherwise. The constraints ensure that each row i is covered by at least one column.

Different solving methods have been proposed in the literature for the Set Covering Problem. The use of metaheuristics is a good alternative to tackle this problem as can be swarm intelligence continuous metaheuristic. Because they are continuous metaheuristics and SCP is a combinatorial problem, these metaheuristics must be accompanied by a binarization mechanism. In the literature, we find the main binarization technique used to solve SCP corresponds to transfer functions, for more details on binarization techniques see gas [4], [5]. Among the main algorithms that use this technique we found a cat swarm [6], a binary Firefly Optimization [7], a Binary Cuckoo Search (BCS) [8] and artificial bee colony [9]. Specific binarization techniques have also been developed to solve SCP, among the most efficient are: a Teaching-learning binarization [10], a Binary Black Hole (BBH) [11], and a specific Jumping Particle Swarm Optimization (JPSO) method [12].

Depending on the algorithm that has been used, the quality of the solution wanted and the complexity of the SCP chosen, it is defined the amount of customization effort required. Being of paramount importance the determination of the values that are given to the parameters. Conveniently, this work proposes a meta-optimization approach where the task of customization is transferred to another metaheuristic (a “high level”metaheuristic) which can handle the task of parameters adjustment for a low level metaheuristic [13].

Our proposal considers a Genetic Algorithm (GA) for parameter setting and an ABC algorithm at a lower level using an Automatic Parameter Tuning approach. The Automatic Parameter Tuning is carried by the GA which searches for the best parameters in the parameter space in order to tune the solver automatically.

This approach is considered as meta-optimization since there are two metaheuristics covering tasks of parameter setting, for the former, and problem solving, for the latter [14]. This work is an extension of[15] where emphasis is given to the percentage of improvement of the different instances.

The rest of this paper is organized as follows. In Section 2, we briefly survey the ABC algorithm. In section 3 we present the meta-optimization approach. In Section 4, we present the experimental results obtained. The analysis of the results of comparing our proposal with a constructive metaheuristic is presented in section 5. Finally, in Section 6 we conclude the paper and give some perspectives for further research.

Artificial Bee Colony Algorithm

ABC is one of the most recent algorithms in the domain of the collective intelligence [16]. Created by Dervis Karaboga in 2005, who was motivated by the intelligent behavior observed in the domestic bees to take the process of foraging [17]. ABC is an algorithm of combinatorial optimization based on populations, in which the solutions of the problem of optimization, the sources of food, are modified by the artificial bees, that fungen as operators of variation. The aim of these bees is to discover the food sources with major nectar.

In the ABC algorithm, the artificial bees move in a multidimensional search space choosing sources of nectar depending on its past experience and its companions of beehive or fitting his position. Some bees (exploratory) fly and choose food sources randomly without using experience. When they find a source of major nectar, they memorize his position and forget the previous one. Thus, ABC combines methods of local search and global search, trying to balance the process of the exploration and exploitation of the space of search. The Flow chart of Artificial Bee Colony is showed in Fig. 1.

Flow Chart of ABC Algorithm.

Figure 1: Flow Chart of ABC Algorithm.

The procedure for determining a food source in the neighbourhood of a particular food source which depends on the nature of the problem. Karaboga [18] developed the first ABC algorithm for continuous optimization. The method for determining a food source in the neighbourhood of a particular food source is based on changing the value of one randomly chosen variable while keeping other variables unchanged. This is done by adding to the current value of the variable the product of a uniform value in [-1, 1] and the difference in values of this variable for this food source and some other randomly chosen food source. This approach can not be used for discrete optimization problems for which it generates at best a random effect.

Singh [19] subsequently proposed a method, which is appropriate for subset selection problems. In his model, to generate a neighbouring solution, an object is randomly dropped from the solution and in its place another object, which is not already present in the solution is added. The object to be added is selected from another randomly chosen solution. If there are more than one candidate objects for addition then ties are broken arbitrarily. In this work we use the ABC algorithm described in [20] and extending the work presented in [14].

A Meta-Optimization Approach to Solve the SCP

Metaheuristics, in their original definition, are solution methods that orchestrate an interaction between local improvement procedures and higher level strategies. Thus, metaheuristics create a process capable of escaping from local optima and performing a robust search of a solution space.

Over time, these methods have also come to include any procedures that employ strategies for overcoming the trap of local optimality in complex solution spaces. The use of one or more neighborhood structures as a means of defining admissible moves to transition from one solution to another, or to build or destroy solutions in constructive and destructive processes are examples of such procedures.

Parameter setting

The selection of an adequate set of values for parameters improves the performance of metaheuristic methods. This configuration can be realized of two ways:

Offline configuration

It consists of finding the appropriate configuration of parameters of the algorithm before the algorithm is executed. It is mostly done in the form of trial and error. This makes tuning process a very high consuming time task. There depends much of the intuition and the experience of the creator of the algorithm. They are typically undocumented and therefore not reproducible driving often to an unequal adjustment of different algorithms. An alternative to find good values for the parameters shown in [21]. Within this group are the racing methods where it is evaluated iteratively different candidate configurations for a certain number of instances [22];Also this Sequential Model-Based Optimisation, this approach, consists of improving the initial values of the parameters alternating .the experiment design and the identification of the parameters [23] and Graphic Radial Method, in this approach radar chart curve is used to define the best configuration [5].

Online configuration

It is an important research area, since the algorithms can adapt themselves better to the characteristics of a particular instance. In the search process, it is essential to identify the phases of exploration and exploitation of the algorithm since the adjustment of parameters can be different in each stage allowing to achieve a better performance. Can improve results in cases of algorithms that are used in situations which are very different to those that were built.

Different techniques exist, being the most simple to define the rule variation of parameters before executing the algorithm.

The on-line approaches can be classified in dynamic and adaptive. Dynamic approaches are those where the updating of the parameters is performed in a random or deterministic way. On the other hand in adaptive approaches the memory is used and the change of value is made according to the progress in the search process. One special case is the autonomous search concept where internal and external information is used for adjustment. Find a correct configuration of parameters constitutes an optimization problem for which we can use a meta-Level optimizer.

Meta-Optimization

A meta-optimization approach can be considered as two or more metaheuristics where a higher level metaheuristic controls the parameters of a lower level one, which is at charge of dealing more directly to the problem. Our ABC algorithm employs four control parameters which are: number of food sources, the value of limit,% of Columns to add, and% of Columns to eliminate. On a higher level GA allows to evaluate different parameter configurations avoiding manual configuration. Each GA individual encodes the parameters of an ABC algorithm generating an ABC instance. The detail of the proposed approach is presented below:

Higher level metaheuristic

GA has been successfully used in various algorithm configurations, a particular case is the presented by Grefenstette [24], that used it to find the parameter values of another genetic algorithm. Another example is [25] where several subpopulations are used and a specialized cross-over operator to generate new candidate configurations. On the other hand it was recently used by Senthilkumar in [26] to find the parameters of the arc welding process with flux core. Using a proven algorithm in the search for configurations, allows us to validate our proposal.

In the GA component, the chromosome genes are: “Food sources”, it is the number of initial solutions for ABC (which is equal to the number of workers or onlookers bees), it will take values between 50 and 500. The second gene, “Limit”, it takes values between 0 and 100. Similarly, the third and fourth genes, “% Columns to Add” and “% Columns to Eliminate”, they take values between 0.01 and 10.

During each generation of the GA algorithm, in order to produce offsprings, a tournament selection method is used to select a set of individuals from the population as follows. Given the size k of the tournament group and a probability p, the k individuals are sorted using their fitness value and a random value r is generated. If , the best individual is choosen, otherwise the probability p is incremented, a new random value is generated and the tournament group is reduced by one. This process is repeated at most k times. If no individual is chosen after k attempts, the worst individual belonging to the tournament group is selected. To select n individuals this selection procedure is carried out n times.

The operator randomly selects two chromosomes from the population and performs the crossover as follows. It generates randomly a binary crossover mask with the same length as the chromosomes. If the value of a bit is 1, chromosome information is copied from the first parent. If the value is 0, the genes from the second parent are used and vice-versa for the second offspring.

The mutation operator is applied with a certain rate replacing the value of a gene with a value drawn uniformly from its domain.

Lower level Metaheuristic

In the ABC component, a first step is performed in order to initialize the parameters of ABC as size of the colony, number of workers and onlookers bees, limit of attempts and maximum number of cycles (iterations). To generate the initial population we cross every row of the counterfoil of constraints and by every row a column is selected at random. This column is part of the solution which is represented by means of an entire vector. This vector considers the columns chosen in one solution. To complete this vector a procedure is performed for all the rows in such a way that the generated solution complies with all the constraints. Then, the evaluation of the population fitness is performed using the objective function, see (1). Afterwards, the modification of the position and selection of sites for worker bees is performed as follows. A hard-working bee modifies its current position selecting a food source randomly. If a hard-working bee duplicates a solution, it is transformed to an explorer bee. Otherwise, it proceeds to add a certain random number of columns between 0 and the maximum number of columns to be added. Then, it proceeds to eliminate a certain random number of columns between 0 and the maximum number of columns to be eliminated. If the new solution does not meet the constraints, it is repaired.

We use repair method where all rows not covered are identified and the columns required are added. So in this way all the constraints will be covered. The search of these columns are based in the relationship showed in the Equation 4.

Once the columns are added and the solution is feasible, a method is applied to remove redundant columns of the solution. A redundant column are those that are removed, the solution remains a feasible solution.

After this, the fitness of the solution is evaluated by means of the objective function of the SCP and if the fitness is minor that the solution previously obtained, the solution is replaced. Otherwise, the number of attempts for improving this solution is increased and the algorithm continues evaluating another hard-working bee.

Integrating Components

The Figure 2 shows the meta-optimization approach developed to solve the SCP. Once the GA population is generated, each individual is taken to run the ABC algorithm until a certain cut-off. Then, the genetic operators are applied and a termination criterion is evaluated in order to stop the parameter setting. Once the termination criterion is achieved, the best individual from the GA contains the best parameter set which is selected to run the ABC algorithm.

Tuning ABC().

Figure 2: Tuning ABC().

Results

In this section we detail the behaviour of our approach. To solve the different SCP instances, a Computer with Windows 7, 2.5 GHz Dual Core processor and 4GB in RAM was used.

The ABC algorithm was executed 30 times for each instance, where the main features are shown in the Table I,where the density corresponds to the percentage of non-zero in the matrix.

In the top level Java Package was used1 (jgap) 3,5 version to implement the genetic algorithm using the parameters shown in the Table II. The GA implementation has 3 main phases: configuration, initial population and evolution of the population.

Table I: Features of the 65 instances [20].

Table II: Parameters used in GA

The best parameters settings for each instance were found using GA, since these may vary because the search space can change very much of one instance to another. In the table IIIshows the values of the parameters of the best chromosomes obtained.

Table III: Parameters values from best chromosome

Table IV: Results obtained for IWD - Meta-Optimization

In order to compare our proposal with other works and given information available, we use the relative percentage deviation (RPD) which quantifies the deviation of the target value Z of Zopt. We report the optimal value, the best found value using our proposed and its average. The results are shown in the Tables V, VIand VII.

Table V: Results obtained for Set 4

Table VI: Results obtained for Set 5

Table VII: Results obtained for Set B, C and H

To validate our proposal were resolved the 65 instances of OR-Library and were compared with published results of recent approaches: Binary Cat Swarm Optimization (BCSO) [6]; Binary Firefly Optimization (BFO) [27]; Binary Shuffled Frog Leaping Algorithm (BSFLA) [28]; Binary Electromagnetism - Like Algorithm (BELA) [29]; and Binary Artificial Bee Colony (BABC) [30]. The comparison is done using relative percentage deviation (RPD).

The table Vshow the results obtained for instances from group 4, where ABC had the best optimal values compared to the results by the previous approaches, only BFO exhibit a good performance for this data with two global optimums.

In the group 5, ABC, BFO, BSFLA AND BABC obtained optimal values, detailed as follows: ABC, four optimal values; BFO, three optimal values; BSFLA, four optimal values; BABC, two optimal values. BELA and BCSO did not achieve some optimum. The results are shown in the Table VI.

The results of groups B, C and H are shown in the Table VIIwhere it is visualized that ABC achieves all the optimals for groups B and H, also achieving 2 optimal for group C. In relation to the other techniques used in the comparison, BFO finds two optimal values, BSFLA finds four optimal values. In the case of BABC, there are two optimal values. BCSO not get optimal as well as BELA.

Additionally, our proposal was compared with the constructive Metaheuristic called Intelligent Water Drops presented by [31]. For this comparison was used the first instances of the groups 4, 5, 6, A, B y C. The results are shown in the table IV.

In order to demonstrate that our approach helps to improve the overall time to solve a problem, to contribute to the search for a good configuration parameters in less time, we use the table VIIIit shows the times used for the configuration of each instance. Manually we used 5 hours, in contrast with GA we use 720 seconds for each group of instances.

In the Table VIIIwe can see that the biggest instances the percentage of progress of the time diminishes what it makes necessary to incorporate in the future other techniques to improve this behavior.

Table VIII: Comparison of ABC with manually and automatically tuned parameters

In tables IXto XI we analysed the difference of RPD of the different techniques with respect to the RPD obtained by ABC. We can observe that for Set 4 table Xin average the lowest percentage of improvement corresponds to 36,41 %, however low to 27.84% for set 5. For the most complicated groups, our proposal also presents important improvement with respect to the other techniques.

Table IX: Comparison RPD Set 4 with ABC

Table X: Comparison RPD Set 5 with ABC

Table XI: Comparison RPD Set B, C and H with ABC

Statistical Analysis

To perform the statistical analysis in this study, we use the following tests:

  • Kolmogorov-Smirnov-Lilliefors 32 is used to determine the independence of samples.

  • Wilcoxons Signed Rank 33 is used to verify superiority of the strategy of resolution using Meta-optimization in relation to the IWD algorithm

For both tests, we use a significance level of 0.05, that is, values smaller than 0.05 indicate that the corresponding hypothesis cannot be assumed. For the first test, the following hypothesis is used:

H0 = The data follow a normal distribution.

H1 = The data do not follow a normal distribution.

Given the P-values obtained in the tests, the hypothesis is rejected.

The Wilcoxon-Mann-Whitney [33] test is then applied. To verify the superiority of the resolution strategy using Meta-Optimization in relation to the IWD Algorithm, fitness is used, and the following hypotheses are defined:

H1 = IWD algorithm < Meta-Optimization

It is obtained p-value < 0.05; therefore, the hypothesis H0 is rejected, and H1 is accepted, which implies that Meta-optimization provides better results. This procedure extends to each instance of the benchmark (Table XII). The results of this analysis are coincident with those verified by RPD.

Table XII: Statistical Analysis Results.

Conclusions

In our work we use a metaheuristics with a meta-optimization approach to solve the SCP. The results revealed, once again, the importance of the parametrization of the algorithms. The results were very good in comparison with the other proposals used. Clearly the use of the automation in the parameters, allows to significantly improve the results in relation to the manual parameterization. In theis work, was possible to observe that the time of instances of the groups 4 and 5, considering the time used in the process of configuration, was greater than 50 percent. As future work, we propose the use of other metaheuristics with different parameters with the order to improve the results and also to facilitate the use by simplifying the parametrization of the metaheuristic of top level. In addition you can use this approach to other problems of the real world as is the problem of routing of school buses with time windows [34].

Acknowledgements

Acknowledgment

Broderick Crawford is supported by grant CONICYT / FONDECYT / REGULAR 1171243 and Ricardo Soto is supported by Grant CONICYT / FONDECYT / REGULAR / 1160455, Gino Astorga is supported by Postgraduate Grant, Pontificia Universidad Católica de Valparaíso, 2015 and José Garcia is supported by INF-PUCV 2016. This research was partially funded by CORFO Program Ingeniería 2030 PUCV - Consortium of Chilean Engineering Faculties.

Referencias

  1. [1] C. Toregas, R. Swain, C. ReVelle, and L. Bergman, “The location of emergency service facilities,” Operations Research, vol. 19, no. 6, pp. 1363-1373, 1971. https://doi.org/10.1287/opre.19.6.1363 [Link]
  2. [2] D. Schilling, V. Jayaraman, and R. Barkhi, “A review of covering problem in facility location,” Location Science, Vol. 1, no. 1, pp. 25-55, 1993
  3. [3] T. Drezner, Z. Drezner, and Z. Goldstein, “A stochastic gradual cover location problem,” Naval Research Logistics (NRL), vol. 57, no. 4, pp. 367-372, 2010. https://doi.org/10.1002/nav.20410 [Link]
  4. [4] B. Crawford, R. Soto, G. Astorga, J. García, C. Castro, and F. Paredes, “Putting continuous metaheuristics to work in binary search spaces,” Complexity, vol. 2017, no. 2, 2017. https://doi.org/10.1155/2017/8404231 [Link]
  5. [5] J. Garcia, B. Crawford, R. Soto, C. Castro, and F. Paredes, “A k-means binarization framework applied to multidimensional knapsack problem,” Applied Intelligence, vol. 48, no. 2, pp. 357-380, 2017
  6. [6] B. Crawford, R. Soto, N. Berríos, F. Johnson, F. Paredes, C. Castro, and E. Norero, “A binary cat swarm optimization algorithm for the non-unicost set covering problem,” Mathematical Problems in Engineering, vol. 2015, no. 2, 2015. https://doi.org/10.1155/2015/578541 [Link]
  7. [7] B. Crawford, R. Soto, M. Olivares-Suárez, F. Paredes, and F. Johnson, “Binary firefly algorithm for the set covering problem,” in 2014 9th Iberian Conference on Information Systems and Technologies (CISTI), pp. 1-5, june 2014. https://doi.org/10.1109/CISTI.2014.6877090. https://doi.org/10.1007/978-3-319-06740-7_6 [Link]
  8. [8] R. Soto, B. Crawford, R. Olivares, J. Barraza, I. Figueroa, F. Johnson, F. Paredes, and E. Olguín, “Solving the non-unicost set covering problem by using cuckoo search and black hole optimization,” Natural Computing, pp. 1-17, 2017. https://doi.org/10.1007/s11047-016-9609-7 [Link]
  9. [9] D. Karaboga, “An idea based on honey bee swarm for numerical optimization,” tech. rep., Technical report-tr06, Erciyes university, engineering faculty, computer engineering department, 2005
  10. [10] Y. Lu and F. J. Vasko, “An or practitioner’s solution approach for the set covering problem,” International Journal of Applied Metaheuristic Computing (IJAMC), vol. 6, no. 4, pp. 1-13, 2015. https://doi.org/10.4018/IJAMC.2015100101 [Link]
  11. [11] J. García, B. Crawford, R. Soto, and P. García, “A multi dynamic binary black hole algorithm applied to set covering problem,” in Harmony Search Algorithm, pp. 42-51, Springer, 2017
  12. [12] S. Balaji and N. Revathi, “A new approach for solving set covering problem using jumping particle swarm optimization method,” Natural Computing, vol. 15, no. 3, pp. 503-517, 2016. https://doi.org/10.1007/s11047-015-9509-2 [Link]
  13. [13] B. Crawford, C. Valenzuela, R. Soto, E. Monfroy, and F. Paredes, “Parameter tuning of metaheuristics using metaheuristics,” Advanced Science Letters, vol. 19, no. 12, pp. 3556-3559, 2013. https://doi.org/10.1166/asl.2013.5236 [Link]
  14. [14] B. Crawford, R. Soto, W. Palma, F. Johnson, F. Paredes, and E. Olguín, “A 2-level approach for the set covering problem: Parameter tuning of artificial bee colony algorithm by using genetic algorithm,” in Advances in Swarm Intelligence (Y. Tan, Y. Shi, and C. Coello, eds.), vol. 8794, pp. 189-196, Springer International Publishing, 2014
  15. [15] B. Crawford, R. Soto, E. Monfroy, G. Astorga, J. García, and E. Cortes, “A meta-optimization approach for covering problems in facility location,” in 4th Workshop on Engineering Applications, pp. 565-578, Springer, 2017. https://doi.org/10.1007/978-3-319-66963-2_50 [Link]
  16. [16] D. Karaboga, B. Gorkemli, C. Ozturk, and N. Karaboga, “A comprehensive survey: artificial bee colony (ABC) algorithm and applications,” Artificial Intelligence Review, vol. 42, no. 3, pp. 21-57, 2014. https://doi.org/10.1007/s10462-012-9328-0 [Link]
  17. [17] D. Karaboga and B. Basturk, “A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm,” Journal Global Optimization, vol. 39, no. 3, pp. 459-471, 2007. https://doi.org/10.1007/s10898-007-9149-x [Link]
  18. [18] D. Karaboga, “An idea based on honey bee swarm for numerical optimization,” Technical Report TR06. Computer Engineering Department, Erciyes University, Turkey, 2005.
  19. [19] A. Singh, “An artificial bee colony algorithm for the leaf-constrained minimum spanning tree problem,” Applied Soft Computing, vol. 9, no. 2, pp. 625-631, 2009. https://doi.org/10.1016/j.asoc.2008.09.001 [Link]
  20. [20] B. Crawford, R. Soto, R. Cuesta, and F. Paredes, “Application of the artificial bee colony algorithm for solving the set covering problem,” The Scientific World Journal, vol. 2014, no. 1, 2014. https://doi.org/10.1155/2014/189164 [Link]
  21. [21] M. López-Ibánez, J. Dubois-Lacoste, L. P. Cáceres, M. Birattari, and T. Stützle, “The irace package: Iterated racing for automatic algorithm configuration,” Operations Research Perspectives, vol. 3, pp. 43 - 58, 2016. https://doi.org/10.1016/j.orp.2016.09.002 [Link]
  22. [22] M. Birattari, “The problem of tuning metaheuristics as seen from a machine learning perspective,” Amsterdam: IOS Press, 2004
  23. [23] G. Franceschini and S. Macchietto, “Model-based design of experiments for parameter precision: State of the art,” Chemical Engineering Science, vol. 63, no. 19, pp. 4846-4872, 2008. https://doi.org/10.1016/j.ces.2007.11.034 [Link]
  24. [24] J. J. Grefenstette , “Optimization of control parameters for genetic algorithms,” IEEE Transactions on systems, man, and cybernetics, vol. 16, no. 1, pp. 122-128, 1986. https://doi.org/10.1109/TSMC.1986.289288 [Link]
  25. [25] C. Ansótegui, M. Sellmann, and K. Tierney, “A gender-based genetic algorithm for the automatic configuration of algorithms,” in International Conference on Principles and Practice of Constraint Programming, pp. 142- 157, Springer, 2009. https://doi.org/10.1007/978-3-642-04244-7_14 [Link]
  26. [26] B. Senthilkumar, T. Kannan, and R. Madesh, “Optimization of flux-cored arc welding process parameters by using genetic algorithm,” The International Journal of Advanced Manufacturing Technology, vol. 93, no. 1-4, pp. 35-41, 2017. https://doi.org/10.1007/s00170-015-7636-7 [Link]
  27. [27] B. Crawford, R. Soto, M. Olivares-Suárez, and F. Paredes, “A binary firefly algorithm for the set covering problem,” in 3rd Computer Science On-line Conference 2014 (CSOC 2014), vol. 285 of Advances in Intelligent Systems and Computing, pp. 65-73, Springer International Publishing, 2014.
  28. [28] B. Crawford, R. Soto, C. Peña, W. Palma, F. Johnson, and F. Paredes, “Solving the set covering problem with a shuffled frog leaping algorithm,” in 7th Asian Conference, ACIIDS 2015, Bali, march 23-25, 2015.
  29. [29] R. Soto, B. Crawford, A. Muñoz, F. Johnson, and F. Paredes, “Pre-processing, repairing and transfer functions can help binary electromagnetism-like algorithms,” in Artificial Intelligence Perspectives and Applications, vol. 347 of Advances in Intelligent Systems and Computing, pp. 89-97, Springer International Publishing, 2015. https://doi.org/10.1007/978-3-319-18476-0_10 [Link]
  30. [30] R. Cuesta, B. Crawford, R. Soto, and F. Paredes, “An artificial bee colony algorithm for the set covering problem,” in Modern Trends and Techniques in Computer Science:3rd Computer Science On-line Conference 2014 (CSOC 2014) , Springer International Publishing, 2014. https://doi.org/10.1007/978-3-319-06740-7_5 [Link]
  31. [31] H. Shah-Hosseini, “Intelligent water drops algorithm: A new optimization method for solving the multiple knapsack problem,” International Journal of Intelligent Computing and Cybernetics, vol. 1, no. 2, pp. 193-212, 2008. https://doi.org/10.1108/17563780810874717 [Link]
  32. [32] S. S. Shapiro and M. B. Wilk, “An analysis of variance test for normality (complete samples),” Biometrika, vol. 52, no. 3/4, pp. 591-611, 1965. https://doi.org/10.2307/2333709. https://doi.org/10.1093/biomet/52.3-4.591 [Link]
  33. [33] H. B. Mann and D. R. Whitney, “On a test of whether one of two random variables is stochastically larger than the other,” The annals of mathematical statistics, pp. 50-60, 1947. https://doi.org/10.1214/aoms/1177730491 [Link]
  34. [34] L. Santana, E. Ramiro, and J. Romero, “A hybrid column generation and clustering approach to the school bus routing problem with time windows,” Ingeniería, vol. 20, no. 1, pp. 101-117, 2015