Binary Particle Swarm Optimization Based Hyper-Heuristic for Solving the Set-Union Knapsack Problem

The set-union knapsack problem(SUKP)is proved to be a strongly NP-hard problem,and it is an extension of the classic NP-hard problem:the 0-1 knapsack problem(KP).Solving the SUKP through exact approaches is computationally expensive.Therefore,several swarm intelligent algorithms have been proposed in order to solve the SUKP.Hyper-heuristics have received notable attention by researchers in recent years,and they are successfully applied to solve the combinatorial optimization problems.In this article,we propose a binary particle swarm optimization(BPSO)based hyper-heuristic for solving the SUKP,in which the BPSO is employed as a search methodology.The proposed approach has been evaluated on three sets of SUKP instances.The results are compared with 6 approaches:BABC,EMS,gPSO,DHJaya,b WSA,and HBPSO/TS,and demonstrate that the proposed approach for the SUKP outperforms other approaches.