A hybrid metaheuristic for the Knapsack Problem with Forfeits
| Autor: | Ciriaco D’Ambrosio, Luigi Pavone, Giovanni Capobianco, Gaetano Vitale, Andrea Raiconi, Fabio Sebastiano |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
Mathematical optimization
Generalization Computer science Conflicts Forfeits Knapsack Problem Genetic algorithm Carousel Greedy Computational intelligence Theoretical Computer Science Set (abstract data type) Knapsack problem Benchmark (computing) Geometry and Topology Heuristics Metaheuristic Software |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|