1. Modeling and solving of knapsack problem with setup based on evolutionary algorithm.
- Author
-
He, Yichao, Wang, Jinghong, Liu, Xuejing, Wang, Xizhao, and Ouyang, Haibin
- 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. • A new model of knapsack problem with setup (KPS) is established. • An algorithm for eliminating infeasible solutions of KPS is proposed. • The basic framework of solving KPS is advanced based on evolutionary algorithms. • Algorithm RA-GTOA for KPS is proposed by group theory-based optimization algorithm. • The calculation results show that RA-GTOA is a fast and effective for KPS. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF