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

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.

Authors:

• Broderick Crawford
• Ricardo Soto
• Natalia Berrios
• Eduardo Olguin

Keywords:

• Binary cat swarm optimization
• set covering problem
• metaheuristic
• binarization methods.

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.