Solving the Set Covering Problem Using the Binary Cat Swarm Optimization Metaheuristic

Authors: Broderick Crawford, Ricardo Soto, Natalia Berrios, Eduardo Olguin

Abstract:

In this paper, we present a binary cat swarm optimization for solving the Set covering problem. The set covering problem is a well-known NP-hard problem with many practical applications, including those involving scheduling, production planning and location problems. Binary cat swarm optimization is a recent swarm metaheuristic technique based on the behavior of discrete cats. Domestic cats show the ability to hunt and are curious about moving objects. The cats have two modes of behavior: seeking mode and tracing mode. We illustrate this approach with 65 instances of the problem from the OR-Library. Moreover, we solve this problem with 40 new binarization techniques and we select the technical with the best results obtained. Finally, we make a comparison between results obtained in previous studies and the new binarization technique, that is, with roulette wheel as transfer function and V3 as discretization technique.

Keywords: Binary cat swarm optimization, set covering problem, metaheuristic, binarization methods.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1115354

References:

[1] U. Aickelin. An indirect genetic algorithm for set covering problems. Journal of the Operational Research Society, pages 1118–1126, 2002.
[2] A. I. Ali and H. Thiagarajan. A network relaxation based enumeration algorithm for set partitioning. European Journal of Operational Research, 38(1):76–85, 1989.
[3] F. Amini and P. Ghaderi. Hybridization of harmony search and ant colony optimization for optimal locating of structural dampers. Applied Soft Computing, pages 2272–2280, 2013.
[4] M. L. Balinski and R. E. Quandt. On an integer program for a delivery problem. Operations Research, 12(2):300–304, 1964.
[5] J. Beasley. A lagrangian heuristic for set covering problems. Naval Research Logistics, 37:151–164, 1990.
[6] J. Beasley and K. Jornsten. Enhancing an algorithm for set covering problems. European Journal of Operational Research, 58(2):293–300, April 1992.
[7] M. Bellmore and H. D. Ratliff. Optimal defense of multi-commodity networks. Management Science, 18(4-part-i):B174–B185, 1971.
[8] M. A. Breuer. Simplification of the covering problem with application to boolean expressions. Journal of the Association for Computing Machinery, 17(1):166–181, Jan. 1970.
[9] A. Caprara, M. Fischetti, and P. Toth. Algorithms for the set covering problem. Annals of Operations Research, 98:353–371, 2000.
[10] N. Christofides. Zero-one programming using non-binary tree-search. Computer Journal, 14(4):418–421, 1971.
[11] S. Chu and P. Tsai. Computational intelligence based on the behavior of cats. International Journal of Innovative Computing, Information and Control, pages 163 – 173, 2007.
[12] S. Chu, P. Tsai, and J. Pan. Cat swarm optimization. In Trends in Artificial Intelligence, pages 854–858. Springer-Verlag, Berlin, Heidelberg, 2006.
[13] B. Crawford, R. Soto, N. Berrios, 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(Article ID 578541):1–8, 2015.
[14] 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(Article ID 189164):1–8, 2014.
[15] B. Crawford, R. Soto, and E. Monfroy. Cultural algorithms for the set covering problem. In Y. Tan, Y. Shi, and H. Mo, editors, Advances in Swarm Intelligence, 4th International Conference, volume 7929 of Lecture Notes in Computer Science, pages 27–34. Springer, Harbin, China, 2013.
[16] B. Crawford, R. Soto, E. Monfroy, W. Palma, C. Castro, and F. Paredes. Parameter tuning of a choice-a function based hyperheuristic using particle swarm optimization. Expert Systems with Applications, pages 1690–1695, 2013.
[17] B. Crawford, R. Soto, M. Olivares-Su´arez, W. Palma, F. Paredes, E. Olguin, and E. Norero. A binary coded firefly algorithm that solves the set covering problem. volume 17, pages 252–264, 2014.
[18] B. Crawford, R. Soto, M. Olivares-Su´arez, and F. Paredes. A binary firefly algorithm for the set covering problem. In 3rd Computer Science On-line Conference 2014, Modern Trends and Techniques in Computer Science, volume 285, pages 65–73. Springer, 2014.
[19] B. Crawford, R. Soto, C. Pe˜na, W. Palma, F. Johnson, and F. Paredes. Solving the set covering problem with a shuffled frog leaping algorithm. In N. T. Nguyen, B. Trawinski, and R. Kosala, editors, Intelligent Information and Database Systems - 7th Asian Conference, volume 9012 of LNCS, pages 41–50, Bali, Indonesia, 2015. Springer.
[20] B. Crawford, R. Soto, M. Riquelme-Leiva, C. Pena, C. Torres-Rojas, F. Johnson, and F. Paredes. Set covering problem solved by new binary firefly algorithm. In 10th Iberian Conference on Information Systems and Technologies, pages 1–4. 2015.
[21] R. H. Day. Letter to the editoron optimal extracting from a multiple file data storage system: An application of integer programming. Operations Research, 13(3):482–494, 1965.
[22] M. L. Fisher and M. B. Rosenwein. An interactive optimization system for bulk-cargo ship scheduling. Naval Research Logistics, 36(1):27–42, 1989.
[23] B. A. Freeman and J. V. Jucker. The line balancing problem. Journal of Industrial Engineering, 18:361–364, 1967.
[24] R. S. Garfinkel and G. L. Nemhauser. Optimal political districting by implicit enumeration techniques. Management Science, 16(8):B495–B508, 1970.
[25] D. Goldberg. Real-coded genetic algorithms, virtual alphabets, and blocking. Complex Systems, pages 139–167, 1990.
[26] D. Gouwanda and S. Ponnambalam. Evolutionary search techniques to solve set covering problems. World Academy of Science, Engineering and Technology, 39:20–25, 2008.
[27] E. Housos and T. Elmroth. Automatic optimization of subproblems in scheduling airline crews. Interfaces, 27(5):68–77, 1997.
[28] L. Lessing, I. Dumitrescu, and T. Stutzle. A comparison between aco algorithms for the set covering problem. In Ant Colony Optimization and Swarm Intelligence, pages 1–12. 2004.
[29] G. Panda, P. Pradhan, and B. Majhi. Iir system identification using cat swarm optimization. Expert Systems with Applications, 38:12671–12683, 2011.
[30] Z. Ren, Z. Feng, L. Ke, and Z. Zhang. New ideas for applying ant colony optimization to the set covering problem. Computers & Industrial Engineering, pages 774 – 784, 2010.
[31] C. C. Ribeiro, M. Minoux, and M. C. Penna. An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment. European Journal of Operational Research, 41(2):232–239, 1989.
[32] Y. Sharafi, M. Khanesar, and M. Teshnehlab. Discrete binary cat swarm optimization algorithm. Computer, Control and Communication, pages 1–6, 2013.
[33] P. Tsai, J. Pan, S. Chen, and B. Liao. Enhanced parallel cat swarm optimization based on the taguchi method. Expert Systems with Applications, 39:6309–6319, 2012.
[34] F. J. Vasko, F. E. Wolf, and K. L. Stott. Optimal selection of ingot sizes via set covering. Operations Research, 35(3):346–353, June 1987.
[35] W. Walker. Using the set-covering problem to assign fire companies to fire houses. Operations Research, 22:275–277, 1974.