Abstract
Different criteria exist for the classification of the metaheuristics. One important classification is: improvement metaheuristics and constructive. On the one hand improvement metaheuristics, begins with an initial solution and iteratively improves the quality of the solution using neighborhood search. On the other hand, constructive metaheuristics, are those in which a solution is built from the beginning, finding in each iteration a local optimum. In this article, we to compare two constructive metaheuristics, Ant Colony Optimization and Intelligent Water Drops, by solving a classical NP-hard problem, such like the Set Covering Problem, which has many practical applications, including line balancing production, service installation and crew scheduling in railway, among others. The results reveal that Ant Colony Optimization has a better behavior than Intelligent Water Drops in relation to the problem considered.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aickelin, U.: An indirect genetic algorithm for set covering problems. J. Oper. Res. Soc. 53, 1118–1126 (2002)
Beasley, J.: An algorithm for set covering problem. Eur. J. Oper. Res. 31, 85–93 (1987)
Beasley, J.E., Chu, P.C.: A genetic algorithm for the set covering problem. Eur. J. Oper. Res. 94, 392–404 (1996)
Brusco, M.J., Jacobs, L.W., Thompson, G.M.: A morphing procedure to supplement a simulated annealing heuristic for cost and coverage correlated set covering problems. Ann. Oper. Res. 86, 611–627 (1999)
Crawford, B., Soto, R., Berríos, N., Johnson, F., Paredes, F., Castro, C., Norero, E.: A binary cat swarm optimization algorithm for the non-unicost set covering problem. In: Mathematical Problems in Engineering (2015)
Crawford, B., Soto, R., Córdova, J., Olguín, E.: A nature inspired intelligent water drop algorithm and its application for solving the set covering problem. In: Silhavy, R., Senkerik, R., Oplatkova, Z.K., Silhavy, P., Prokopova, Z. (eds.) Artificial Intelligence Perspectives in Intelligent Systems. AISC, vol. 464, pp. 437–447. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-33625-1_39
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-García, J.C., López-Santana, E.R., Villa-Ramírez, J.L., Ferro-Escobar, R. (eds.) WEA 2017. CCIS, vol. 742, pp. 565–578. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66963-2_50
Dorigo, M., Maniezzo, V., Colorni, A.: Ant system: optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. Part B (Cybern.) 26(1), 29–41 (1996)
Fisher, M., Kedia, P.: Optimal solution of set covering/partitioning problems using dual heuristics. Manag. Sci. 36(6), 674–688 (1990)
Hartmanis, J.: Computers and intractability: a guide to the theory of np-completeness (Michael R. Garey and David S. Johnson). SIAM Rev. 24(1), 90 (1982)
Lessing, L., Dumitrescu, I., Stützle, T.: A comparison between ACO algorithms for the set covering problem. In: Dorigo, M., Birattari, M., Blum, C., Gambardella, L.M., Mondada, F., Stützle, T. (eds.) ANTS 2004. LNCS, vol. 3172, pp. 1–12. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28646-2_1
Shah-Hosseini, H.: Intelligent water drops algorithm: A new optimization method for solving the multiple knapsack problem. Int. J. Intell. Comput. Cybern. 1(2), 193–212 (2008)
Soto, R., Crawford, B., Galleguillos, C., Barraza, J., Lizama, S., Muñoz, A., Vilches, J., Misra, S., Paredes, F.: Comparing cuckoo search, bee colony, firefly optimization, and electromagnetism-like algorithms for solving the set covering problem. In: Gervasi, O., Murgante, B., Misra, S., Gavrilova, M.L., Rocha, A.M.A.C., Torre, C., Taniar, D., Apduhan, B.O. (eds.) ICCSA 2015. LNCS, vol. 9155, pp. 187–202. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21404-7_14
Acknowledgements
Broderick Crawford is supported by grant CONICYT/FONDECYT/REGULAR 1171243 and Ricardo Soto is supported by Grant CONICYT/FONDECYT/REGULAR/1160455, Gino Astorga is supported by Postgraduate Grant, Pontificia Universidad Catolica de Valparaíso, 2015 and José García is supported by INF-PUCV 2016. The authors are grateful for the support of the Project CORFO 14ENI2-26905 “Nueva Ingeniería para el 2030” - PUCV.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Crawford, B., Soto, R., Astorga, G., García, J. (2018). Constructive Metaheuristics for the Set Covering Problem. In: Korošec, P., Melab, N., Talbi, EG. (eds) Bioinspired Optimization Methods and Their Applications. BIOMA 2018. Lecture Notes in Computer Science(), vol 10835. Springer, Cham. https://doi.org/10.1007/978-3-319-91641-5_8
Download citation
DOI: https://doi.org/10.1007/978-3-319-91641-5_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-91640-8
Online ISBN: 978-3-319-91641-5
eBook Packages: Computer ScienceComputer Science (R0)