AN ANT COLONY BASED HYPER-HEURISTIC APPROACH FOR THE SET COVERING PROBLEM

AN ANT COLONY BASED HYPER-HEURISTIC APPROACH FOR THE SET COVERING PROBLEM

Authors:
Alexandre Silvestre FERREIRA, Aurora POZO, Richard Aderbal GONÇALVES

DOI:
http://dx.doi.org/10.14201/ADCAIJ201541121

Volume:
Regular Issue 4 (1), 2015

Keywords: 
ant colony; hyper-heuristic; set covering problem; optimization
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.

JCR

Position in 2022 Journal Citation Indicator (JCI) Ranking:
Category COMPUTER SCIENCE, ARTIFICIAL INTELLIGENCE


CONTACT