Abstract
The design of robust continuous metaheuristic techniques to apply them to combinatorial problems is a line of research with great applied potential. There are two major challenges in this regard. The first is related to the fact that many of the problems addressed at an industrial level are of the combinatorial type and the second has to do with the fact that no lesser subset of these problems are of the NP-hard type. In this study, a binarization mechanism has been proposed for continuous swarm intelligence metaheuristics which uses the percentile concept to perform binarization. This percentile concept is applied to Whale’s optimization algorithm to solve the set coverage problem (SCP). To identify the contribution of the method, experiments were designed which are compared with a baseline. Additionally, the proposal is compared with recently published algorithms, using reference instances. The results indicate that the binary percentile whale (BPWH) algorithm obtains adequate results when it is 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: Nature & Biologically Inspired Computing, 2009. NaBIC 2009. World Congress on, pp. 210–214. IEEE (2009)
Yang, X.-S.: A new metaheuristic bat-inspired algorithm. In: Nature Inspired Cooperative Strategies for Optimization (NICSO 2010), pp. 65–74 (2010)
Mirjalili, S., Lewis, A.: The whale optimization algorithm. Adv. Eng. Softw. 95, 51–67 (2016)
Altimiras, F., et al.: Altered gut microbiota in a fragile x syndrome mouse model. Front. Neurosci. 15 (2021)
Crawford, B., et al.: Investigating the efficiency of swarm algorithms for bridge strengthening by conversion to tied-arch: a numerical case study on San Luis bridge. Iran. J. Sci. Technol. Trans. Civ. Eng. 1–13 (2020)
Crawford, B., Soto, R., Astorga, G., García, J.: Constructive metaheuristics for the set covering problem. In: Korošec, P., Melab, N., Talbi, E.G. (eds.) Bioinspired Optimization Methods and Their Applications. International Conference on Bioinspired Methods and Their Applications, pp. 88–99. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-91641-5_8
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., et al.: A Db-scan binarization algorithm applied to matrix covering problems. Comput. Intell. Neurosci. 2019 (2019)
Crawford, B., et al.: Q-learnheuristics: towards data-driven balanced metaheuristics.Mathematics 9(16) (2021)
García, J., Altimiras, F., Peña, A., Astorga, G., Peredo, O.: A binary cuckoo search big data algorithm applied to large-scale crew scheduling problems. Complexity 2018 (2018)
García, J., Maureira, C.: A KNN quantum cuckoo search algorithm applied to the multidimensional knapsack problem. Appl. Soft Comput. 102, 107077 (2021)
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(9), 1951–1970 (2020). https://doi.org/10.1007/s13042-020-01085-8
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)
García J., Crawford B., Soto R., Astorga G.: A percentile transition ranking algorithm applied to knapsack problem. In: Silhavy, R., Silhavy, P., Prokopova, Z. (eds.) Applied Computational Intelligence and Mathematical Methods. Proceedings of the Computational Methods in Systems and Software, pp. 126–138, Springer, Cham (2017). https://doi.org/10.1007/978-3-319-67621-0_11
García, J., Crawford, B., Soto, R., Astorga, G.: A percentile transition ranking algorithm applied to binarization of continuous swarm intelligence metaheuristics. In: Ghazali, R., Deris, M., Nawi, N., Abawajy, J. (eds.) Recent Advances on Soft Computing and Data Mining. International Conference on Soft Computing and Data Mining, pp. 3–13, Springer, Cham (2018). https://doi.org/10.1007/978-3-319-72550-5_1
García, J., Astorga, G., Yepes, V.: An analysis of a KNN perturbation operator: an application to the binarization of continuous metaheuristics. Mathematics 9(3), 225 (2021)
Tapia, D., et al.: A Q-learning hyperheuristic binarization framework to balance exploration and exploitation. In: Florez, H., Misra, S. (eds.) International Conference on Applied Informatics, pp. 14–28. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-61702-8_2
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)
García, J., Măntoiu, M.: Localization results for zero order pseudodifferential operators. J. Pseudo-Differ. Oper. Appl. 5(2), 255–276 (2013). https://doi.org/10.1007/s11868-013-0084-y
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)
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)
Yepes, V., Martí, J.V., García, J.: Black hole algorithm for sustainable design of counterfort retaining walls. Sustainability 12(7), 2767 (2020)
Martínez-Muñoz, D., Marté, J.V., Garcéa, J., Yepes, V.: Embodied energy optimization of buttressed earth-retaining walls with hybrid simulated annealing. Appl. Sci. 11(4) (2021)
Balaji, S., Revathi, N.: A new approach for solving set covering problem using jumping particle swarm optimization method. Nat. Comput. 15(3), 503–517 (2015). https://doi.org/10.1007/s11047-015-9509-2
García, J., Crawford, B., Soto, R., García, P.: A multi dynamic binary black hole algorithm applied to set covering problem. In: Del Ser, J. (eds.) Harmony Search Algorithm. International Conference on Harmony Search Algorithm, pp. 42–51. Springer, Singapore (2017). https://doi.org/10.1007/978-981-10-3728-3_6
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: Figueroa-Garcia, J., López-Santana, E., Villa-Ramírez, J., Ferro-Escobar, R. (eds.) Workshop on Engineering Applications, pp. 565–578. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66963-2_50
Kasirzadeh, A., Saddoune, M., Soumis, F.: Airline crew scheduling: models, algorithms, and data sets. EURO J. Transp. Logistics 6(2), 111–137 (2015). https://doi.org/10.1007/s13676-015-0080-x
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. Central Eur. J. Oper. Res. 27(1), 39–67 (2017). https://doi.org/10.1007/s10100-017-0489-4
Stojković, M.: The operational flight and multi-crew scheduling problem. Yugoslav J. Oper. Res. 15(1) (2016)
García, J., Crawford, B., Soto, R., Castro, C., Paredes, F.: A k-means binarization framework applied to multidimensional knapsack problem. Appl. Intell. 48(2), 357–380 (2017). https://doi.org/10.1007/s10489-017-0972-6
García, J., Pope, C., Altimiras, F.: A distributed k-means segmentation algorithm applied to Lobesia botrana recognition. Complexity 2017 (2017)
Graells-Garrido, E., García, J.: Visual exploration of urban dynamics using mobile data. In: García-Chamizo, J., Fortino, G., Ochoa, S. (eds.) Ubiquitous Computing and Ambient Intelligence. Sensing, Processing, and Using Environmental Information. International Conference on Ubiquitous Computing and Ambient Intelligence, pp. 480–491. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-26401-1_45
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: Gómez-Hernández J., Rodrigo-Ilarri J., Rodrigo-Clavero M., Cassiraga E., Vargas-Guzmán J. (eds.) Geostatistics Valencia 2016, pp. 949–964. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-46819-8_66
Maureira, C., Pinto, H., Yepes, V., Garcia, J.: Towards an AEC-AI industry optimization algorithmic knowledge mapping an adaptive methodology for macroscopic conceptual analysis. IEEE Access 1 (2021)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Jorquera, L., Valenzuela, P., Causa, L., Moraga, P., Rubio, JM. (2021). A Percentile Whale Algorithm an Application to the Set Covering Problem. In: Silhavy, R., Silhavy, P., Prokopova, Z. (eds) Data Science and Intelligent Systems. CoMeSySo 2021. Lecture Notes in Networks and Systems, vol 231. Springer, Cham. https://doi.org/10.1007/978-3-030-90321-3_32
Download citation
DOI: https://doi.org/10.1007/978-3-030-90321-3_32
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-90320-6
Online ISBN: 978-3-030-90321-3
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)