An improved binary quantum-behaved particle swarm optimization algorithm for knapsack problems

The 0-1 knapsack problem is a typical NP-hard combinatorial optimization problem that is difficult to solve efficiently based on traditional optimization approaches. Binary quantum behaved particle swarm optimization (BQPSO) algorithm is a simple yet efficient discrete optimization approach since it guarantees global search. However, BQPSO suffers from local optimum and slow convergence problems due to aggregation among particles, limiting its performance. To address this problem, an improved BQPSO (IBQPSO) algorithm is proposed to effectively solve the 0-1 knapsack problem. First, to address the discretization issues in existing QPSO algorithms, a mapping strategy based on the average position of all particles is introduced. Then, the transfer function is used to discretize the local attractors into binary vectors for crossover operations, which can guide individuals in the discrete space to the optimum. In addition, a new repair method is employed to address infeasible solutions, and a diversity maintenance mechanism is developed in IBQPSO to alleviate the local optima problem. The proposed algorithm is compared with ten state-of-the-art heuristic algorithms on a set of 0-1 knapsack problems with different scales. Experimental results show that IBQPSO has obvious superiority over the other ten algorithms in terms of convergence speed and search performance.

Automated summary

This research proposes an improved BQPSO algorithm to solve the 0-1 knapsack problem. The algorithm optimizes the discretization issue by introducing a mapping strategy and a transfer function. It also addresses infeasible solutions and local optima problems with a new repair method and a diversity maintenance mechanism. Experimental results show its superiority over other ten algorithms in terms of convergence speed and search performance.