Self-adaptive check and repair operator-based particle swarm optimization for the multidimensional knapsack problem

• We propose a novel self-adaptive check and repair operator (SACRO).
• Particle swarm optimization (PSO) is utilized to cooperate with the idea of SACRO.
• The SACRO based algorithms were tested using 137 benchmarks from OR-Library.
• The SACRO is competitive and robust than traditional check and repair operator.
• The SACRO based algorithms rival other state-of-the-art PSO and other algorithms.

The multidimensional knapsack problem (MKP) is a combinatorial optimization problem belonging to the class of NP-hard problems. This study proposes a novel self-adaptive check and repair operator (SACRO) combined with particle swarm optimization (PSO) to solve the MKP. The traditional check and repair operator (CRO) uses a unique pseudo-utility ratio, whereas SACRO dynamically and automatically changes the alternative pseudo-utility ratio as the PSO algorithm runs. Two existing PSO algorithms are used as the foundation to support the novel SACRO methods, the proposed SACRO-based algorithms were tested using 137 benchmark problems from the OR-Library to validate and demonstrate the efficiency of SACRO idea. The results were compared with those of other population-based algorithms. Simulation and evaluation results show that SACRO is more competitive and robust than the traditional CRO. The proposed SACRO-based algorithms rival other state-of-the-art PSO and other algorithms. Therefore, changing different types of pseudo-utility ratios produces solutions with better results in solving MKP. Moreover, SACRO can be combined with other population-based optimization algorithms to solve constrained optimization problems.

Flowchart of the SACRO along with PSO.Figure optionsDownload as PowerPoint slide