Abstract
In complexity theory, there is a widely studied grouping of optimization problems that belongs to the non-deterministic polynomial-time hard set. One of them is the set covering problem, known as one of Karp’s 21 \({\mathscr {NP}}\)-complete problems, and it consists of finding a subset of decision variables for satisfying a set of constraints at the minimum feasible cost. However, due to the nature of the problem, this cannot be solved using traditional complete algorithms for hard instances. In this work, we present an improved binary version of the monkey search algorithm for solving the set covering problem. Originally, this approximate method was naturally inspired by the cognitive behavior of monkeys for climbing mountains. We propose a new climbing process with a better exploratory capability and a new cooperation procedure to reduce the number of unfeasible solutions. For testing this approach, we present a detailed computational results section, where we illustrate how this variation of the monkey search algorithm is capable of reaching various global optimums for a well-known instance set from the Beasley’s OR-Library and how it outperforms many other heuristics and meta-heuristics addressed in the literature. Moreover, we add a complete statistical analysis to show the effectiveness of the proposed approach with respect to the original version.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Affenzeller M, Wagner S, Winkler S (2007) Self-adaptive population size adjustment for genetic algorithms. Computer aided systems theory EUROCAST 2007. Springer, Berlin, pp 820–828
Akay B, Karaboga D (2012) A modified artificial bee colony algorithm for real-parameter optimization. Inf Sci 192:120
Balas E (1997) A dynamic subgradient-based branch-and-bound procedure for set covering. Locat Sci 5(3):203
Basset MA, Zhou Y (2018) An elite opposition-flower pollination algorithm for a 0–1 knapsack problem. Int J Bio Inspir Comput 11(1):46. https://doi.org/10.1504/ijbic.2018.090080
Beasley J (2018) Or-library. http://people.brunel.ac.uk/~mastjjb/jeb/orlib/scpinfo.html. Accessed 14 Feb 2018
Beasley J (1987) An algorithm for set covering problem. Eur J Oper Res 31(1):85
Bilal N, Galinier P, Guibault F (2014) An iterated-tabu-search heuristic for a variant of the partial set covering problem. J Heuristics 20(2):143
Brotcorne L, Laporte G, Semet F (2003) Ambulance location and relocation models. Eur J Oper Res 147(3):451
Brusco M, Jacobs L, Thompson G (1999) A morphing procedure to supplement a simulated annealing heuristic for cost and coverage correlated set covering problems. Ann Oper Res 86:611
Burke E, Kendall G, Newall J, Hart E, Ross P, Schulenburg S (2003) Handbook of metaheuristics, vol 57. International series in operations research and management science. Springer, Berlin, pp 457–474
Calvet L, de Armas J, Masip D, Juan AA (2017) Learnheuristics: hybridizing metaheuristics with machine learning for optimization with dynamic inputs. Open Math 15(1):261–80
Caprara A, Fischetti M, Toth P (1999) A heuristic method for the set covering problem. Oper Res 47(5):730
Caprara A, Fischetti M, Toth P (2000) Algorithms for the set covering problem. Annals OR 98(1–4):353
Ceria S, Nobili P, Sassano A (1998) A lagrangian-based heuristic for large-scale set covering problems. Math Program 81:215
Chvatal V (1979) A greedy heuristic for the set-covering problem. Math Oper Res 4(3):233
Crawford B, Soto R, Monfroy E, Paredes F, Palma W (2011) A hybrid ant algorithm for the set covering problem. Int J Phys Sci 6(19):4667
Crawford B, Soto R, Olivares-Suárez M, Paredes F (2014a) Advances in intelligent systems and computing. 3rd Computer science on-line conference 2014 (CSOC 2014), vol 285. Springer, Berlin, pp 65–73
Crawford B, Soto R, Palma W, Johnson F, Paredes F, Olguín E (2014b) Advances in swarm intelligence. Lecture notes in computer science, vol 8794. Springer, Berlin, pp 189–196
Crawford B, Soto R, Astorga G, García J, Castro C, Paredes F (2017) Putting continuous metaheuristics to work in binary search spaces. Complexity 2017:1
Crawford B, Soto R, Berríos N, Johnson F, Paredes F, Castro C, Norero E (2015a) A binary cat swarm optimization algorithm for the non-unicost set covering problem. Math Prob Eng 2015:1
Crawford B, Soto R, Peña C, Palma W, Johnson F, Paredes F (2015b) Intelligent information and database systems. In: 7th Asian conference, ACIIDS 2015, Bali, Indonesia, March 23–25, 2015, Proceedings, Part II. Lecture notes in computer science, vol 9012. Springer, Berlin, pp 41–50
Cui L, Li G, Zhu Z, Wen Z, Lu N, Lu J (2017) A novel differential evolution algorithm with a self-adaptation parameter control method by differential evolution. Soft Comput. https://doi.org/10.1007/s00500-017-2685-5
Day RH (1965) Letter to the editor-on optimal extracting from a multiple file data storage system: an application of integer programming. Oper Res 13(3):482
Dorigo M, Maniezzo V, Colorni A (1996) The ant system: optimization by a colony of cooperating agents. IEEE Trans Syst Man Cybern 26(1):1
Eaton JW (2018) Gnu octave. https://www.gnu.org/software/octave/ (2002). Accessed 14 Feb 2018
Eiben A, Hinterding R, Michalewicz Z (1999) Parameter control in evolutionary algorithms. IEEE Trans Evol Comput 3(2):124
Feo TA, Resende MG (1989) A probabilistic heuristic for a computationally difficult set covering problem. Oper Res Lett 8(2):67
Fink M (2007) Proceedings of the Eleventh international conference on artificial intelligence and statistics, proceedings of machine learning research (PMLR, San Juan, Puerto Rico, 2007), vol 2, pp 115–122
Fisher ML, Kedia P (1990) Optimal solution of set covering/partitioning problems using dual heuristics. Manage Sci 36(6):674
Han MF, Liao SH, Chang JY, Lin CT (2012) Dynamic group-based differential evolution using a self-adaptive strategy for global optimization problems. Appl Intell 39(1):41. https://doi.org/10.1007/s10489-012-0393-5
Hartmanis J (1982) Computers and intractability: a guide to the theory of NP-completeness. SIAM Rev 24(1):90
Holland JH (1975) Adaptation in natural and artificial systems. The University of Michigan Press, Ann Arbor
Housos E, Elmroth T (1997) Automatic optimization of subproblems in scheduling airline crews. Interfaces 27(5):68
Iba H (2018) Evolutionary approach to machine learning and deep neural networks. Springer, Singapore, pp 27–75. https://doi.org/10.1007/978-981-13-0200-8_2
Ituarte-Villarreal CM, Lopez N, Espiritu JF (2012) Using the monkey algorithm for hybrid power systems optimization. Proc Comput Sci 12:344
Karaboga D, Basturk B (2007) A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. J Global Optim 39(3):459
Lan G, DePuy G (2006) On the effectiveness of incorporating randomness and memory into a multi-start metaheuristic with application to the set covering problem. Comput Ind Eng 51(3):362
Lanza-Gutierrez J, Crawford B, Soto R, Berrios N, Gomez-Pulido J, Paredes F (2017) Analyzing the effects of binarization techniques when solving the set covering problem through swarm optimization. Expert Syst Appl 70:67
Li X, Yin M (2012) Self-adaptive constrained artificial bee colony for constrained numerical optimization. Neural Comput Appl 24(3–4):723
Li X, Yin M (2015) Modified cuckoo search algorithm with self adaptive parameter method. Inf Sci 298:80
Liang KH, Yao X, Newton CS (2001) Adapting self-adaptive parameters in evolutionary algorithms. Appl Intell 15(3):171. https://doi.org/10.1023/a:1011286929823
Lilliefors H (1967) On the Kolmogorov-Smirnov test for normality with mean and variance unknown. J Am Stat Assoc 62(318):399
Mahmoudi S, Lotfi S (2015) Modified cuckoo optimization algorithm (MCOA) to solve graph coloring problem. Appl Soft Comput 33:48
Mann H, Donald W (1947) On a test of whether one of two random variables is stochastically larger than the other. Ann Math Stat 18(1):50
Memeti S, Pllana S, Binotto A, Kołodziej J, Brandic I (2018) Proceedings of the international conference on learning and optimization algorithms: theory and applications - LOPAL 18. ACM Press. doi 10(1145/3230905):3230906
Nguyen TT, Vo DN (2015) Modified cuckoo search algorithm for short-term hydrothermal scheduling. Int J Electr Power Energy Syst 65:271
Olamaei J, Moradi M, Kaboodi T (2013) 18th Electric power distribution conference, pp 1–6
Qin A, Suganthan P (2005) Self-adaptive differential evolution algorithm for numerical optimization. In: 2005 IEEE congress on evolutionary computation (IEEE, 2005), pp 1785–1791. https://doi.org/10.1109/cec.2005.1554904
ReVelle C, Toregas C, Falkson L (2010) Applications of the location set covering problem. Geogr Anal 8(1):65
Roeper T, Williams E (1987) Parameter setting. In: Hyams N (ed) The theory of parameters and syntactic development. Springer, Netherlands, pp 191–215
Salto C, Alba E (2011) Designing heterogeneous distributed GAs by efficiently self-adapting the migration period. Appl Intell 36(4):800. https://doi.org/10.1007/s10489-011-0297-9
Salveson ME (1995) The assembly line balancing problem. J Ind Eng 6(3):18
Soto R, Crawford B, Misra S, Palma W, Monfroy E, Castro C, Paredes F (2013) Choice functions for autonomous search in constraint programming: GA vs PSO. Tech Gaz 20(4):621
Soto R, Crawford B, Palma W, Monfroy E, Olivares C, Castro Rodrigoand, Paredes F (2015a) Top- k based adaptive enumeration in constraint programming. Math Prob Eng 2015:1
Soto R, Crawford B, Palma W, Galleguillos K, Castro C, Monfroy E, Johnson F, Paredes F (2015b) Boosting autonomous search for CSPs via skylines. Inf Sci 308:38
Soto R, Crawford B, Muñoz A, Johnson F, Paredes F (2015c) Advances in intelligent systems and computing. Artificial Intelligence Perspectives and Applications, vol 347. Springer, Berlin, pp 89–97
Soto R, Crawford B, Olivares R, Barraza J, Figueroa I, Johnson F, Paredes F, Olguín E (2017) Solving the non-unicost set covering problem by using cuckoo search and black hole optimization. Nat Comput 16(2):213
Spall J (1992) Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE Trans Autom Control 37(3):332
Stutzle T, Lopez-Ibanez M, Pellegrini P, Maur M, Montes de Oca M, Birattari M, Dorigo M (2012) What is autonomous search?. Parameter adaptation in ant colony optimization. Springer, Berlin, pp 191–215
Valenzuela C, Crawford B, Soto R, Monfroy E, Paredes F (2014) A 2-level metaheuristic for the set covering problem. Int J Comput Commun Control 7(2):377
Vasko FJ, Wilson GR (1984) Using a facility location algorithm to solve large set covering problems. Oper Res Lett 3(2):85
Vasko FJ, Wolf FE, Stott KL (1987) Optimal selection of ingot sizes via set covering. Oper Res 35(3):346
Xin C, Zhou Y, Zhonghua T, Qifang L (2017) A hybrid algorithm combining glowworm swarm optimization and complete 2-opt algorithm for spherical travelling salesman problems. Appl Soft Comput 58:104. https://doi.org/10.1016/j.asoc.2017.04.057
Yang XS (2010) Nature Inspired Cooperative Strategies for optimization (NICSO), vol 284. Studies in computational intelligence. Springer, Berlin, pp 65–74
Yang XS, He X (2013) Firefly algorithm: recent advances and applications. Int J Swarm Intell 1(1):36. https://doi.org/10.1504/ijsi.2013.055801
Yelbay B, Birbil Şİ, Bülbül K (2014) The set covering problem revisited: an empirical study of the value of dual information. JIMO 11(2):575
Yi W, Gao L, Li X, Zhou Y (2014) A new differential evolution algorithm with a hybrid mutation operator and self-adapting control parameters for global optimization problems. Appl Intell 42(4):642. https://doi.org/10.1007/s10489-014-0620-3
Zhang S, Zhou Y, Li Z, Pan W (2016) Grey wolf optimizer for unmanned combat aerial vehicle path planning. Adv Eng Softw 99:121. https://doi.org/10.1016/j.advengsoft.2016.05.015
Zhao R, Tang W (2008) Monkey algorithm for global numerical optimization. J Uncertain Syst 2(3):165
Zhou Y (2016) Hybrid symbiotic organisms search algorithm for solving 0–1 knapsack problem. Int J Bio Inspir Comput 1(1):1. https://doi.org/10.1504/ijbic.2016.10004304
Zhou Y, Chen H, Zhou G (2014) Invasive weed optimization algorithm for optimization no-idle flow shop scheduling problem. Neurocomputing 137:285. https://doi.org/10.1016/j.neucom.2013.05.063
Zhou Y, Luo Q, Chen H, He A, Wu J (2015a) A discrete invasive weed optimization algorithm for solving traveling salesman problem. Neurocomputing 151:1227. https://doi.org/10.1016/j.neucom.2014.01.078
Zhou Y, Li L, Ma M (2015b) A complex-valued encoding bat algorithm for solving 0–1 knapsack problem. Neural Process Lett 44(2):407. https://doi.org/10.1007/s11063-015-9465-y
Zhou Y, Bao Z, Luo Q, Zhang S (2016a) A complex-valued encoding wind driven optimization for the 0–1 knapsack problem. Appl Intell 46(3):684. https://doi.org/10.1007/s10489-016-0855-2
Zhou Y, Chen X, Zhou G (2016b) An improved monkey algorithm for a 0–1 knapsack problem. Appl Soft Comput 38:817
Acknowledgements
Broderick Crawford is supported by Grant CONICYT/FONDECYT/REGULAR/1171243. Ricardo Soto is supported by Grant CONICYT/FONDECYT/REGULAR/1190129. Rodrigo Olivares is supported by CONICYT/FONDEF/IDeA/ID16I10449, STIC-AMSUD/17STIC- 03, FONDECYT/MEC/MEC80170097 and Postgraduate Grant Pontificia Universidad Católica de Valparaíso (INF-PUCV 2015-2019).
Author information
Authors and Affiliations
Corresponding authors
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Crawford, B., Soto, R., Olivares, R. et al. A binary monkey search algorithm variation for solving the set covering problem. Nat Comput 19, 825–841 (2020). https://doi.org/10.1007/s11047-019-09752-8
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11047-019-09752-8