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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Xavier Sánchez-Díaz, José Carlos Ortiz-Bayliss, Ivan Amaya, Jorge M. Cruz-Duarte, Santiago Enrique Conant-Pablos, Hugo Terashima-Marín
Formato:	article
Lenguaje:	EN
Publicado:	MDPI AG 2021
Materias:	hyper-heuristics knapsack problem optimization Technology T Engineering (General). Civil engineering (General) TA1-2040 Biology (General) QH301-705.5 Physics QC1-999 Chemistry QD1-999
Acceso en línea:	https://doaj.org/article/5c14838d268843179edafee591028c85
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:5c14838d268843179edafee591028c85
record_format	dspace
spelling	oai:doaj.org-article:5c14838d268843179edafee591028c852021-11-11T15:15:46ZA Feature-Independent Hyper-Heuristic Approach for Solving the Knapsack Problem10.3390/app1121102092076-3417https://doaj.org/article/5c14838d268843179edafee591028c852021-10-01T00:00:00Zhttps://www.mdpi.com/2076-3417/11/21/10209https://doaj.org/toc/2076-3417Recent 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.Xavier Sánchez-DíazJosé Carlos Ortiz-BaylissIvan AmayaJorge M. Cruz-DuarteSantiago Enrique Conant-PablosHugo Terashima-MarínMDPI AGarticlehyper-heuristicsknapsack problemoptimizationTechnologyTEngineering (General). Civil engineering (General)TA1-2040Biology (General)QH301-705.5PhysicsQC1-999ChemistryQD1-999ENApplied Sciences, Vol 11, Iss 10209, p 10209 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	hyper-heuristics knapsack problem optimization Technology T Engineering (General). Civil engineering (General) TA1-2040 Biology (General) QH301-705.5 Physics QC1-999 Chemistry QD1-999
spellingShingle	hyper-heuristics knapsack problem optimization Technology T Engineering (General). Civil engineering (General) TA1-2040 Biology (General) QH301-705.5 Physics QC1-999 Chemistry QD1-999 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
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.
format	article
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
title	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_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_sort	feature-independent hyper-heuristic approach for solving the knapsack problem
publisher	MDPI AG
publishDate	2021
url	https://doaj.org/article/5c14838d268843179edafee591028c85
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
_version_	1718435983977873408

A Feature-Independent Hyper-Heuristic Approach for Solving the Knapsack Problem

Ejemplares similares