Modeling and solving of knapsack problem with setup based on evolutionary algorithm

Yichao He, Jinghong Wang, Xuejing Liu, Xizhao Wang and Haibin Ouyang

Mathematics and Computers in Simulation (MATCOM), 2024, vol. 219, issue C, 378-403

Abstract: The knapsack problem with setup (KPS) is a combinatorial optimization problem with important application in the industrial field. In order to solve KPS more quickly and effectively with evolutionary algorithms, a new mathematical model is first established. On the basis of the random algorithm RGSA to generate the potential solution and the repair and optimization algorithm gROA to handle with the infeasible solution, an algorithm framework EA-KPS for solving KPS is given by using evolutionary algorithm. According to EA-KPS, a heuristic algorithm RA-GTOA for solving KPS is proposed by group theory-based optimization algorithm. The comparison of calculation results between RA-GTOA and six representative algorithms for solving 200 KPS benchmark instances shows that RA-GTOA is superior to others in solution accuracy, speed and robustness. This not only shows that RA-GTOA is an efficient algorithm for solving KPS, but also demonstrates that using evolutionary algorithms to solve KPS is an effective method.

Keywords: Evolutionary algorithm; Knapsack problem with setup; Group theory-based optimization algorithm; Infeasible solution; Greedy repair and optimization (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378475423005402
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:matcom:v:219:y:2024:i:c:p:378-403

DOI: 10.1016/j.matcom.2023.12.033

Access Statistics for this article

Mathematics and Computers in Simulation (MATCOM) is currently edited by Robert Beauwens

More articles in Mathematics and Computers in Simulation (MATCOM) from Elsevier
Bibliographic data for series maintained by Catherine Liu ().