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

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.