A biased random-key genetic algorithm for the knapsack problem with forfeit sets

被引：0
作者：
Raffaele Cerulli [1 ]
Ciriaco D’Ambrosio [1 ]
Andrea Raiconi [2 ]
机构：
[1] Department of Mathematics, University of Salerno, Via Giovanni Paolo II 132, SA, Fisciano
[2] CNR-IAC, Institute for Applied Mathematics “Mauro Picone”, Via Pietro Castellino 111, Naples
来源：
Soft Computing | 2024年 / 28卷 / 20期
关键词：
Biased random-key genetic algorithm; Forfeit sets; Knapsack problem; Metaheuristic;
D O I：
10.1007/s00500-024-09948-w
中图分类号：
学科分类号：
摘要：
This work addresses the Knapsack Problem with Forfeit Sets, a recently introduced variant of the 0/1 Knapsack Problem considering subsets of items associated with contrasting choices. Some penalty costs need to be paid whenever the number of items in the solution belonging to a forfeit set exceeds a predefined allowance threshold. We propose an effective metaheuristic to solve the problem, based on the Biased Random-Key Genetic Algorithm paradigm. An appropriately designed decoder function assigns a feasible solution to each chromosome, and improves it using some additional heuristic procedures. We show experimentally that the algorithm outperforms significantly a previously introduced metaheuristic for the problem. © The Author(s) 2024.
引用
收藏
页码：12021 / 12041
页数：20
相关论文
共 32 条
  • [1] Akinc U., Approximate and exact algorithms for the fixed-charge knapsack problem, Eur J Oper Res, 170, pp. 363-375, (2006)
  • [2] Basnet C., Heuristics for the multiple knapsack problem with conflicts, Int J Oper Res, 32, 4, pp. 514-525, (2018)
  • [3] Ben Salem M., Taktak R., Mahjoub A.R., Ben-Abdallah H., Optimization algorithms for the disjunctively constrained knapsack problem, Soft Comput, 22, pp. 2025-2043, (2018)
  • [4] Bettinelli A., Cacchiani V., Malaguti E., A branch-and-bound algorithm for the knapsack problem with conflict graph, INFORMS J Comput, 29, 3, pp. 457-473, (2017)
  • [5] Buriol L.S., Resende M.G.C., Thorup M., Survivable ip network design with ospf routing, Networks, 49, pp. 51-64, (2007)
  • [6] Capobianco G., D'Ambrosio C., Pavone L., Raiconi A., Vitale G., Sebastiano F., A hybrid metaheuristic for the knapsack problem with forfeits, Soft Comput, 26, pp. 749-762, (2022)
  • [7] Carrabs F., A biased random-key genetic algorithm for the set orienteering problem, Eur J Oper Res, 292, 3, pp. 830-854, (2021)
  • [8] Cerrone C., Cerulli R., Golden B., Carousel greedy: a generalized greedy algorithm with applications in optimization, Comput Oper Res, 85, pp. 97-112, (2017)
  • [9] Cerulli R., D'Ambrosio C., Raiconi A., Vitale G., The knapsack problem with forfeits, In: Combinatorial Optimization. 5Th International Symposium ISCO 2020. Lecture Notes in Computer Science, 12176, pp. 263-272, (2020)
  • [10] Ceselli A., Righini G., An optimization algorithm for a penalized knapsack problem, Oper Res Lett, 34, pp. 394-404, (2006)
1234