An Ant Colony based Hyper-Heuristic Approach for the Set Covering Problem
<span>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 thes...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ediciones Universidad de Salamanca
2015-12-01
|
| Series: | Advances in Distributed Computing and Artificial Intelligence Journal |
| Subjects: | |
| Online Access: | https://revistas.usal.es/index.php/2255-2863/article/view/13172 |
| _version_ | 1818179392954695680 |
|---|---|
| author | Alexandre Silvestre FERREIRA Aurora POZO Richard Aderbal GONÇALVES |
| author_facet | Alexandre Silvestre FERREIRA Aurora POZO Richard Aderbal GONÇALVES |
| author_sort | Alexandre Silvestre FERREIRA |
| collection | DOAJ |
| description | <span>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.<br class="Apple-interchange-newline" /></span> |
| first_indexed | 2024-12-11T21:03:09Z |
| format | Article |
| id | doaj.art-7598233e40f743e9907f44bfb37e15e8 |
| institution | Directory Open Access Journal |
| issn | 2255-2863 |
| language | English |
| last_indexed | 2024-12-11T21:03:09Z |
| publishDate | 2015-12-01 |
| publisher | Ediciones Universidad de Salamanca |
| record_format | Article |
| series | Advances in Distributed Computing and Artificial Intelligence Journal |
| spelling | doaj.art-7598233e40f743e9907f44bfb37e15e82022-12-22T00:50:56ZengEdiciones Universidad de SalamancaAdvances in Distributed Computing and Artificial Intelligence Journal2255-28632015-12-014112110.14201/ADCAIJ20154112112235An Ant Colony based Hyper-Heuristic Approach for the Set Covering ProblemAlexandre Silvestre FERREIRA0Aurora POZO1Richard Aderbal GONÇALVES2C-Bio Group, Federal University of ParanaC-Bio Group, Federal University of ParanaC-Bio Group, State University of Centro-Oeste<span>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.<br class="Apple-interchange-newline" /></span>https://revistas.usal.es/index.php/2255-2863/article/view/13172ant colonyhyper-heuristicset covering problemoptimization |
| spellingShingle | Alexandre Silvestre FERREIRA Aurora POZO Richard Aderbal GONÇALVES An Ant Colony based Hyper-Heuristic Approach for the Set Covering Problem Advances in Distributed Computing and Artificial Intelligence Journal ant colony hyper-heuristic set covering problem optimization |
| title | An Ant Colony based Hyper-Heuristic Approach for the Set Covering Problem |
| title_full | An Ant Colony based Hyper-Heuristic Approach for the Set Covering Problem |
| title_fullStr | An Ant Colony based Hyper-Heuristic Approach for the Set Covering Problem |
| title_full_unstemmed | An Ant Colony based Hyper-Heuristic Approach for the Set Covering Problem |
| title_short | An Ant Colony based Hyper-Heuristic Approach for the Set Covering Problem |
| title_sort | ant colony based hyper heuristic approach for the set covering problem |
| topic | ant colony hyper-heuristic set covering problem optimization |
| url | https://revistas.usal.es/index.php/2255-2863/article/view/13172 |
| work_keys_str_mv | AT alexandresilvestreferreira anantcolonybasedhyperheuristicapproachforthesetcoveringproblem AT aurorapozo anantcolonybasedhyperheuristicapproachforthesetcoveringproblem AT richardaderbalgoncalves anantcolonybasedhyperheuristicapproachforthesetcoveringproblem AT alexandresilvestreferreira antcolonybasedhyperheuristicapproachforthesetcoveringproblem AT aurorapozo antcolonybasedhyperheuristicapproachforthesetcoveringproblem AT richardaderbalgoncalves antcolonybasedhyperheuristicapproachforthesetcoveringproblem |