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

被引：0

作者：

Cerulli, Raffaele ^{[1
]}

D’Ambrosio, Ciriaco ^{[1
]}

Raiconi, Andrea ^{[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)

← 1 2 3 4 →