A Meta-Optimization Approach to Solve the Set Covering Problem

  • 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

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.

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