Abstract
The Weighted Set Covering Problem is a formal model for many practical optimization problems. In this problem the goal is to choose a subset of columns of minimal cost covering every row. Here, a Binary Firefly Algorithm has been developed to tackle the Weighted Set Covering Problem. Firefly Algorithm is a recently developed population-based metaheuristic inspired by the flashing behaviour of fireflies. Experimental results show that our approach is competitive solving the problem at hand.
Chapter PDF
Similar content being viewed by others
References
Aickelin, U.: An indirect genetic algorithm for set covering problems. Journal of the Operational Research Society 53, 1118–1126 (2002)
Balas, E., Carrera, M.C.: A dynamic subgradient-based branch-and-bound procedure for set covering. Operations Research 44(6), 875–890 (1996)
Beasley, J., Chu, P.: A genetic algorithm for the set covering problem. European Journal of Operational Research 94(2), 392–404 (1996)
Beasley, J.E.: A lagrangian heuristic for set-covering problems. Naval Research Logistics (NRL) 37(1), 151–164 (1990)
Beasley, J.E., Jornsten, K.: Enhancing an algorithm for set covering problems. European Journal of Operational Research 58(2), 293–300 (1992)
Brusco, M.J., Jacobs, L.W., Thompson, G.M.: A morphing procedure to supplement a simulated annealing heuristic for cost- and coverage-correlated set-covering problems. Annals of Operations Research 86, 611–627 (1999)
Caprara, A., Toth, P., Fischetti, M.: Algorithms for the set covering problem. Annals of Operations Research 98, 353–371 (2000)
Caserta, M.: abu search-based metaheuristic algorithm for large-scale set covering problems. In: Doerner, K.F., et al. (eds.) Metaheuristics: Progress in complex systems optimization. Springer
Crawford, B., Castro, C., Monfroy, E.: A New ACO Transition Rule for Set Partitioning and Covering Problems. In: SoCPaR, pp. 426–429 (2009)
Crawford, B., Lagos, C., Castro, C., Parede, F.: A Evolutionary Approach to Solve Set Covering. In: ICEIS, vol. 2, pp. 356–363 (2007)
Crawford, B., Soto, R., Castro, C., Monfroy, E.: Extensible CP-based autonomous search. In: Stephanidis, C. (ed.) Posters, Part I, HCII 2011. CCIS, vol. 173, pp. 561–565. Springer, Heidelberg (2011)
Crawford, B., Soto, R., Monfroy, E.: Cultural algorithms for the set covering problem. In: Tan, Y., Shi, Y., Mo, H. (eds.) ICSI 2013, Part II. LNCS, vol. 7929, pp. 27–34. Springer, Heidelberg (2013)
Crawford, B., Soto, R., Monfroy, E., Palma, W., Castro, C., Paredes, F.: Parameter tuning of a choice-function based hyperheuristic using particle swarm optimization. Expert Systems with Applications 40(5), 1690–1695 (2013)
Feo, T.A., Resende, M.G.C.: A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters 8(2), 67–71 (1989)
Fisher, M.L., Kedia, P.: Optimal solution of set covering/partitioning problems using dual heuristics. Management Science 36(6), 674–688 (1990)
Yang, X.-S.: Nature-Inspired Metaheuristic Algorithms. Luniver Press (2008)
Yang, X.-S.: Firefly algorithms for multimodal optimization. In: Watanabe, O., Zeugmann, T. (eds.) SAGA 2009. LNCS, vol. 5792, pp. 169–178. Springer, Heidelberg (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Crawford, B., Soto, R., Olivares-Suárez, M., Paredes, F. (2014). Using the Firefly Optimization Method to Solve the Weighted Set Covering Problem. In: Stephanidis, C. (eds) HCI International 2014 - Posters’ Extended Abstracts. HCI 2014. Communications in Computer and Information Science, vol 434. Springer, Cham. https://doi.org/10.1007/978-3-319-07857-1_89
Download citation
DOI: https://doi.org/10.1007/978-3-319-07857-1_89
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-07856-4
Online ISBN: 978-3-319-07857-1
eBook Packages: Computer ScienceComputer Science (R0)