A Feature-Independent Hyper-Heuristic Approach for Solving the Knapsack Problem
Recent years have witnessed a growing interest in automatic learning mechanisms and applications. The concept of hyper-heuristics, algorithms that either select among existing algorithms or generate new ones, holds high relevance in this matter. Current research suggests that, under certain circumst...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-10-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/11/21/10209 |
| _version_ | 1797512776970665984 |
|---|---|
| author | Xavier Sánchez-Díaz José Carlos Ortiz-Bayliss Ivan Amaya Jorge M. Cruz-Duarte Santiago Enrique Conant-Pablos Hugo Terashima-Marín |
| author_facet | Xavier Sánchez-Díaz José Carlos Ortiz-Bayliss Ivan Amaya Jorge M. Cruz-Duarte Santiago Enrique Conant-Pablos Hugo Terashima-Marín |
| author_sort | Xavier Sánchez-Díaz |
| collection | DOAJ |
| description | Recent years have witnessed a growing interest in automatic learning mechanisms and applications. The concept of hyper-heuristics, algorithms that either select among existing algorithms or generate new ones, holds high relevance in this matter. Current research suggests that, under certain circumstances, hyper-heuristics outperform single heuristics when evaluated in isolation. When hyper-heuristics are selected among existing algorithms, they map problem states into suitable solvers. Unfortunately, identifying the features that accurately describe the problem state—and thus allow for a proper mapping—requires plenty of domain-specific knowledge, which is not always available. This work proposes a simple yet effective hyper-heuristic model that does not rely on problem features to produce such a mapping. The model defines a fixed sequence of heuristics that improves the solving process of knapsack problems. This research comprises an analysis of feature-independent hyper-heuristic performance under different learning conditions and different problem sets. |
| first_indexed | 2024-03-10T06:06:28Z |
| format | Article |
| id | doaj.art-5c14838d268843179edafee591028c85 |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-03-10T06:06:28Z |
| publishDate | 2021-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-5c14838d268843179edafee591028c852023-11-22T20:29:25ZengMDPI AGApplied Sciences2076-34172021-10-0111211020910.3390/app112110209A Feature-Independent Hyper-Heuristic Approach for Solving the Knapsack ProblemXavier Sánchez-Díaz0José Carlos Ortiz-Bayliss1Ivan Amaya2Jorge M. Cruz-Duarte3Santiago Enrique Conant-Pablos4Hugo Terashima-Marín5Tecnologico de Monterrey, School of Engineering and Sciences, Monterrey 64849, MexicoTecnologico de Monterrey, School of Engineering and Sciences, Monterrey 64849, MexicoTecnologico de Monterrey, School of Engineering and Sciences, Monterrey 64849, MexicoTecnologico de Monterrey, School of Engineering and Sciences, Monterrey 64849, MexicoTecnologico de Monterrey, School of Engineering and Sciences, Monterrey 64849, MexicoTecnologico de Monterrey, School of Engineering and Sciences, Monterrey 64849, MexicoRecent years have witnessed a growing interest in automatic learning mechanisms and applications. The concept of hyper-heuristics, algorithms that either select among existing algorithms or generate new ones, holds high relevance in this matter. Current research suggests that, under certain circumstances, hyper-heuristics outperform single heuristics when evaluated in isolation. When hyper-heuristics are selected among existing algorithms, they map problem states into suitable solvers. Unfortunately, identifying the features that accurately describe the problem state—and thus allow for a proper mapping—requires plenty of domain-specific knowledge, which is not always available. This work proposes a simple yet effective hyper-heuristic model that does not rely on problem features to produce such a mapping. The model defines a fixed sequence of heuristics that improves the solving process of knapsack problems. This research comprises an analysis of feature-independent hyper-heuristic performance under different learning conditions and different problem sets.https://www.mdpi.com/2076-3417/11/21/10209hyper-heuristicsknapsack problemoptimization |
| spellingShingle | Xavier Sánchez-Díaz José Carlos Ortiz-Bayliss Ivan Amaya Jorge M. Cruz-Duarte Santiago Enrique Conant-Pablos Hugo Terashima-Marín A Feature-Independent Hyper-Heuristic Approach for Solving the Knapsack Problem Applied Sciences hyper-heuristics knapsack problem optimization |
| title | A Feature-Independent Hyper-Heuristic Approach for Solving the Knapsack Problem |
| title_full | A Feature-Independent Hyper-Heuristic Approach for Solving the Knapsack Problem |
| title_fullStr | A Feature-Independent Hyper-Heuristic Approach for Solving the Knapsack Problem |
| title_full_unstemmed | A Feature-Independent Hyper-Heuristic Approach for Solving the Knapsack Problem |
| title_short | A Feature-Independent Hyper-Heuristic Approach for Solving the Knapsack Problem |
| title_sort | feature independent hyper heuristic approach for solving the knapsack problem |
| topic | hyper-heuristics knapsack problem optimization |
| url | https://www.mdpi.com/2076-3417/11/21/10209 |
| work_keys_str_mv | AT xaviersanchezdiaz afeatureindependenthyperheuristicapproachforsolvingtheknapsackproblem AT josecarlosortizbayliss afeatureindependenthyperheuristicapproachforsolvingtheknapsackproblem AT ivanamaya afeatureindependenthyperheuristicapproachforsolvingtheknapsackproblem AT jorgemcruzduarte afeatureindependenthyperheuristicapproachforsolvingtheknapsackproblem AT santiagoenriqueconantpablos afeatureindependenthyperheuristicapproachforsolvingtheknapsackproblem AT hugoterashimamarin afeatureindependenthyperheuristicapproachforsolvingtheknapsackproblem AT xaviersanchezdiaz featureindependenthyperheuristicapproachforsolvingtheknapsackproblem AT josecarlosortizbayliss featureindependenthyperheuristicapproachforsolvingtheknapsackproblem AT ivanamaya featureindependenthyperheuristicapproachforsolvingtheknapsackproblem AT jorgemcruzduarte featureindependenthyperheuristicapproachforsolvingtheknapsackproblem AT santiagoenriqueconantpablos featureindependenthyperheuristicapproachforsolvingtheknapsackproblem AT hugoterashimamarin featureindependenthyperheuristicapproachforsolvingtheknapsackproblem |