Back to Search
Start Over
A hybrid metaheuristic for the Knapsack Problem with Forfeits.
- Source :
-
Soft Computing - A Fusion of Foundations, Methodologies & Applications . Jan2022, Vol. 26 Issue 2, p749-762. 14p. - Publication Year :
- 2022
-
Abstract
- In this paper, we present a novel hybrid metaheuristic for the Knapsack Problem with Forfeits (KPF). KPF is a recently introduced generalization of the Knapsack Problem. In this variant, a penalty cost incurs whenever both items composing a so-called forfeit pair belong to the solution. Our proposed algorithm, called GA–CG Forfeits, combines the strengths of the Genetic and Carousel Greedy paradigms. In this work, we define the algorithm and compare it with two previously proposed heuristics on a set of benchmark instances. In these tests, GA–CG Forfeits provided significantly better solutions than the other two algorithms on all instances. [ABSTRACT FROM AUTHOR]
- Subjects :
- *KNAPSACK problems
*METAHEURISTIC algorithms
*GENETIC algorithms
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 14327643
- Volume :
- 26
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- Soft Computing - A Fusion of Foundations, Methodologies & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 154663741
- Full Text :
- https://doi.org/10.1007/s00500-021-06331-x