Abstract
The study and understanding of algorithms that solve combinatorial problems based on swarm intelligence continuous metaheuristics, is an area of interest at the level of basic and applied science. This is due to the fact that many of the problems addressed at industrial level are of a combinatorial type and a subset no less than these are of the NP-hard type. In this article, a mechanism of binarization of continuous metaheuristics that uses the concept of the percentile is proposed. This percentile concept is applied to the An Lion optimization algorithm, solving the set covering problem (SCP). Experiments were designed to demonstrate the importance of the percentile concept in the binarization process. Subsequently, the efficiency of the algorithm is verified through reference instances. The results indicate that the binary percentile gravitational search algorithm (BPGSA) obtains adequate results when evaluated with a combinatorial problem such as the SCP.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Yang, X.-S., Deb, S.: Cuckoo search via lévy flights. In: World Congress on Nature & Biologically Inspired Computing, 2009. NaBIC 2009, pp. 210–214. IEEE (2009)
Hatamlou, A.: Black hole: a new heuristic optimization approach for data clustering. Inf. Sci. 222, 175–184 (2013)
Yang, X.-S.: A new metaheuristic bat-inspired algorithm. In: Nature Inspired Cooperative Strategies for Optimization (NICSO 2010), pp. 65–74 (2010)
Mirjalili, S.: SCA: a sine cosine algorithm for solving optimization problems. Knowl. Based Syst. 96, 120–133 (2016)
García, J., Martí, J.V., Yepes, V.: The buttressed walls problem: an application of a hybrid clustering particle swarm optimization algorithm. Mathematics 8(6), 862 (2020)
García, J., Yepes, V., Martí, J.V.: A hybrid k-means cuckoo search algorithm applied to the counterfort retaining walls problem. Mathematics 8(4), 555 (2020)
Yepes, V., Martí, J.V., García, J.: Black hole algorithm for sustainable design of counterfort retaining walls. Sustainability 12(7), 2767 (2020)
García, J., Moraga, P., Valenzuela, M., Pinto, H.: A db-scan hybrid algorithm: an application to the multidimensional knapsack problem. Mathematics 8(4), 507 (2020)
Crawford, B., Soto, R., Astorga, G., García, J.: Constructive metaheuristics for the set covering problem. In: International Conference on Bioinspired Methods and Their Applications, pp. 88–99. Springer (2018)
García, J., Peña, A.: Robust optimization: Concepts and applications. In: Nature-Inspired Methods for Stochastic. Robust and Dynamic Optimization. IntechOpen (2018)
García, J., Moraga, P., Valenzuela, M., Crawford, B., Soto, R., Pinto, H., Peña, A., Altimiras, F., Astorga, G.: A db-scan binarization algorithmapplied to matrix covering problems. Comput. Intell. Neurosci. 2019, 16 (2019)
García, J., Altimiras, F., Peña, A., Astorga, G., Peredo, O.: Abinary cuckoo search big data algorithm applied to large-scale crewscheduling problems. Complexity 2018, 15 (2018)
García, J., Crawford, B., Soto, R., Astorga, G.: A percentile transition ranking algorithm applied to knapsack problem. In: Proceedings of the Computational Methods in Systems and Software, pp. 126–138. Springer (2017)
Astorga, G., Crawford, B., Soto, R., Monfroy, E., García, J., Cortes, E.: A meta-optimization approach to solve the set covering problem. Ingeniería 23(3), 274–288 (2018)
García, J., Lalla-Ruiz, E., Voß, S., Droguett, E.L.: Enhancing a machine learning binarization framework by perturbation operators: analysis on the multidimensional knapsack problem. Int. J. Mach. Learn. Cybern. 11, 1–20 (2020)
García, J., Crawford, B., Soto, R., García, P.: A multi dynamic binary black hole algorithm applied to set covering problem. In: International Conference on Harmony Search Algorithm, pp. 42–51. Springer (2017)
García, J., Crawford, B., Soto, R., Astorga, G.: A percentile transition ranking algorithm applied to binarization of continuous swarm intelligence metaheuristics. In: International Conference on Soft Computing and Data Mining, pp. 3–13. Springer (2018)
Crawford, B., Soto, R., Astorga, G., García, J., Castro, C., Paredes, F.: Putting continuous metaheuristics to work in binary search spaces. Complexity 2017, 19 (2017)
García, J., Crawford, B., Soto, R., Astorga, G.: A clustering algorithm applied to the binarization of swarm intelligence continuous metaheuristics. Swarm Evol. Comput. 44, 646–664 (2019)
Garcia, J., Măntoiu, M.: Localization results for zero order pseudodifferential operators. J. Pseudo Diff. Oper. Appl. 5(2), 255–276 (2014)
Balaji, S., Revathi, N.: A new approach for solving set covering problem using jumping particle swarm optimization method. Nat. Comput. 15(3), 503–517 (2016)
Gary, M.R., Johnson, D.S.: Computers and intractability. In: A Guide to the Theory of NP-Completeness (1979)
Lu, Y., Vasko, F.J.: An or practitioner’s solution approach for the set covering problem. Int. J. Appl. Metaheuristic Comput. (IJAMC) 6(4), 1–13 (2015)
Li, Y., Cai, Z.: Gravity-based heuristic for set covering problems and its application in fault diagnosis. J. Syst. Eng. Electron. 23(3), 391–398 (2012)
Crawford, B., Soto, R., Monfroy, E., Astorga, G., García, J., Cortes, E.: A meta-optimization approach for covering problems in facility location. In: Workshop on Engineering Applications, pp. 565–578. Springer (2017)
Kasirzadeh, A., Saddoune, M., Soumis, F.: Airline crew scheduling: models, algorithms, and data sets. EURO J. Transp. Logistics 6(2), 111–137 (2017)
Horváth, M., Kis, T.: Computing strong lower and upper bounds for the integrated multiple-depot vehicle and crew scheduling problem with branch-and-price. CEJOR 27(1), 1–29 (2017)
Stojković, M.: The operational flight and multi-crew scheduling problem. Yugoslav J. Oper. Res. 15(1), 25–48 (2016)
García, J., Crawford, B., Soto, R., Carlos, C., Paredes, F.: A k-means binarization framework applied to multidimensional knapsack problem. Appl. Intell. 48(2), 1–24 (2017)
García, J., Pope, C., Altimiras, F.: A distributed k-means segmentation algorithm applied to lobesia botrana recognition. Complexity 2017, 14 (2017)
Graells-Garrido, E., García, J.: Visual exploration of urban dynamics using mobile data. In: International Conference on Ubiquitous Computing and Ambient Intelligence, pp. 480–491. Springer (2015)
Graells-Garrido, E., Peredo, O., García, J.: Sensing urban patterns with antenna mappings: the case of Santiago, Chile. Sensors 16(7), 1098 (2016)
Peredo, O.F., García, J.A., Stuven, R., Ortiz, J.M.: Urban dynamic estimation using mobile phone logs and locally varying anisotropy. In: Geostatistics Valencia 2016, pp. 949–964. Springer (2017)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Pavez, L., Altimiras, F., Villavicencio, G. (2020). A Percentil Gravitational Search Algorithm an Aplication to the Set Covering Problem. In: Silhavy, R., Silhavy, P., Prokopova, Z. (eds) Software Engineering Perspectives in Intelligent Systems. CoMeSySo 2020. Advances in Intelligent Systems and Computing, vol 1295. Springer, Cham. https://doi.org/10.1007/978-3-030-63319-6_62
Download citation
DOI: https://doi.org/10.1007/978-3-030-63319-6_62
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-63318-9
Online ISBN: 978-3-030-63319-6
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)