An Ant Colony based Hyper-Heuristic Approach for the Set Covering Problem

  • Alexandre Silvestre Ferreira
    C-Bio Group, Federal University of Parana alexandrefscan[at]gmail.com
  • Aurora Pozo
    C-Bio Group, Federal University of Parana
  • Richard Aderbal Gonçalves
    C-Bio Group, State University of Centro-Oeste

Abstract

The Set Covering Problem (SCP) is a NP-hard combinatorial optimization problem that is challenging for meta-heuristic algorithms. In the optimization literature, several approaches using meta-heuristics have been developed to tackle the SCP and the quality of the results provided by these approaches highly depends on customized operators that demands high effort from researchers and practitioners. In order to alleviate the complexity of designing metaheuristics, a methodology called hyper-heuristic has emerged as a possible solution. A hyper-heuristic is capable of dynamically selecting simple low-level heuristics accordingly to their performance, alleviating the design complexity of the problem solver and obtaining satisfactory results at the same time. In a previous study, we proposed a hyper-heuristic approach based on Ant Colony Optimization (ACO-HH) for solving the SCP. This paper extends our previous efforts, presenting better results and a deeper analysis of ACO-HH parameters and behavior, specially about the selection of low-level heuristics. The paper also presents a comparison with an ACO meta-heuristic customized for the SCP.
  • Referencias
  • Cómo citar
  • Del mismo autor
  • Métricas
Balas, E. and Carrera, M. C., 1996. A dynamic subgradient-based branch-and-bound procedure for set covering. Operations Research, 44(6):875–890.

Beasley, J. E., 1990. OR-Library: distributing test problems by electronic mail. Journal of the operational research society, pages 1069–1072.

Beasley, J. E. and Chu, P. C., 1996. A genetic algorithm for the set covering problem. European Journal of Operational Research, 94(2):392–404.

Biazzini, M., Banhelyi, B., Montresor, A., and Jelasity, M., 2009. Distributed hyper-heuristics for real parameter optimization. In GECCO ’09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation, pages 1339–1346. ACM, New York, NY, USA. ISBN 978-1-60558-325-9. doi:10.1145/1569901.1570081.

Burke, E., Kendall, G., Silva, D. L., O’Brien, R., L, D., Silva, A., and Soubeiga, E., 2005. An Ant Algorithm Hyperheuristic for the Project Presentation Scheduling Problem. In In: Proceedings of the Congress on Evolutionary Computation 2005 (CEC 2005). Volume 3, pages 2263–2270. IEEE press.

Burke, E. K., Gendreau, M., Hyde, M., Kendall, G., Ochoa, G., Ozcan, E., and Qu, R., 2013. Hyper-heuristics. J Oper Res Soc, 64(12):1695–1724. ISSN 0160-5682.

Burke, E. K., Hyde, M., Kendall, G., Ochoa, G., Özcan, E., and Woodward, J. R., 2010. A classification of hyper-heuristic approaches. In Handbook of metaheuristics, pages 449–468. Springer.

Caprara, A., Toth, P., and Fischetti, M., 2000. Algorithms for the set covering problem. Annals of Operations Research, 98(1-4):353–371.

Chen, P.-C., Kendall, G., and Berghe, G., 2007. An Ant Based Hyper-heuristic for the Travelling Tournament Problem. In Computational Intelligence in Scheduling, 2007. SCIS ’07. IEEE Symposium on, pages 19–26. doi:10.1109/SCIS.2007.367665.

Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C., 2009. Introduction to algorithms. MIT press.

Cowling, P., Kendall, G., and Han, L., 2002. an investigation of a hyperheuristic genetic algorithm applied to a trainer scheduling problem. In Proceedings of the Congress on Evolutionary Computation 2002, CEC 2002, pages 1185–1190.

Cowling, P., Kendall, G., and Soubeiga, E., 2001. A hyperheuristic approach to scheduling a sales summit. In Practice and Theory of Automated Timetabling III, pages 176–190. Springer.

Deneubourg, J.-L., Aron, S., Goss, S., and Pasteels, J. M., 1990. The self-organizing exploratory pattern of the argentine ant. Journal of insect behavior, 3(2):159–168.
Dorigo, M. and Socha, 2006. An Introduction to Ant Colony Optimization. Technical Report, No. TR/IRIDIA/2006-010.

Ferreira, A. S., Pozo, A. T., and Gonçalves, R. A., 2014. Aplicação do Algoritmo ACO-HH para o problema de cobertura de conjuntos. In Encontro Nacional de Inteligência Artificial e Computacional - ENIAC, pages 342–346. Sociedade Brasileira de Computação - SBC. In Portuguese.

Fisher, M. L. and Kedia, P., 1990. Optimal solution of set covering/partitioning problems using dual heuristics. Management science, 36(6):674–688.

Grobler, J., Engelbrecht, A., Kendall, G., and Yadavalli, V., 2012. Investigating the use of local search for improving meta-hyper-heuristic performance. In Evolutionary Computation (CEC), 2012 IEEE Congress on, pages 1–8. doi:10.1109/CEC.2012.6252970.

Han, L. and Kendall, G., 2003. Guided Operators for a Hyper-Heuristic Genetic Algorithm. In Proceedings of AI-2003: Advances in Artificial Intelligence. The 16th Australian Conference on Artificial Intelligence, pages 807–820.

Jacobs, L. W. and Brusco, M. J., 1995. Note: A local-search heuristic for large set-covering problems. Naval Research Logistics (NRL), 42(7):1129–1140.

Lan, G., DePuy, G. W., and Whitehouse, G. E., 2007. An effective and simple heuristic for the set covering problem. European journal of operational research, 176(3):1387–1403.

Meignan, D., Koukam, A., and CrÃl’put, J.-C., 2010. Coalition-based metaheuristic: a self-adaptive metaheuristic using reinforcement learning and mimetism. Journal of Heuristics, 16(6):859–879. ISSN 1381-1231. doi:10.1007/s10732-009-9121-7.

Mulati, M. H., 2009. Investigação da Meta-Heurística de Otimização por Colônia de Formigas Artificiais Aplicada ao Problema de Cobertura de Conjunto. Master’s thesis, Dissertação de mestrado, Universidade Estadual de Maringá, Departamento de Informática.

Mulati, M. H. and Constantino, A. A., 2011. Ant-Line: A Line-Oriented ACO Algorithm for the Set Covering Problem. In Proceedings of the 2011 30th International Conference of the Chilean Computer Science Society, pages 265–274. IEEE Computer Society.

Nareyek, A., 2004. chapter Choosing Search Heuristics by Non-stationary Reinforcement Learning, pages 523–544. Kluwer Academic Publishers, Norwell, MA, USA. ISBN 1-4020-7653-3.

Núnez, J. L. and Ceballos, A., 2011. A general purpose Hyper-Heuristic based on Ant colony optimization.

Ochoa, G., Hyde, M., Curtois, T., Vazquez-Rodriguez, J., Walker, J., Gendreau, M., Kendall, G., McCollum, B., Parkes, A., Petrovic, S., and Burke, E., 2012. HyFlex: A Benchmark Framework for Cross-domain Heuristic Search, volume 7245 of LNCS, pages 136–147. Springer, Heidelberg.

Oliveira, N. V. d. et al., 1999. Problema de cobertura de conjuntos: uma comparação numérica de algoritmos heurísticos.

Ren, Z., Feng, Z., Ke, L., and Chang, H., 2008. A fast and efficient ant colony optimization approach for the set covering problem. In Evolutionary Computation, 2008. CEC 2008.(IEEE World Congress on Computational Intelligence). IEEE Congress on, pages 1839–1844. IEEE.

Ren, Z., Jiang, H., Xuan, J., and Luo, Z., 2010. Ant Based Hyper Heuristics with Space Reduction: A Case Study of the P-median Problem. In Proceedings of the 11th International Conference on Parallel Problem Solving from Nature: Part I, PPSN’10, pages 546–555. Springer-Verlag, Berlin, Heidelberg. ISBN 3-642-15843-9, 978-3-642-15843-8.

Vrugt, J. A. and Robinson, B. A., 2007. Improved evolutionary optimization from genetically adaptive multimethod search. Proceedings of the National Academy of Sciences, 104(3):708–711. doi:10.1073/pnas.0610471104.
Ferreira, A. S., Pozo, A., & Gonçalves, R. A. (2015). An Ant Colony based Hyper-Heuristic Approach for the Set Covering Problem. ADCAIJ: Advances in Distributed Computing and Artificial Intelligence Journal, 4(1), 1–21. https://doi.org/10.14201/ADCAIJ201541121

Downloads

Download data is not yet available.
+