Binary Particle Swarm Optimization Algorithm Based on Z-shaped Probability Transfer Function to Solve 0-1 Knapsack Problem

摘要

Binary particle swarm optimization (BPSO) algorithm can map the original continuous searching space to the binary searching space by introducing a new velocity transfer function. For the 0-1 knapsack problem, a binary particle swarm optimization algorithm based on the Z-shaped probability transfer function was proposed. In order to solve the shortcomings of BPSO algorithm based on S-shaped and V-shaped probability functions that it is easy to fall into local optima and slow convergence speed, a new probability function (Z-shaped transfer function) was proposed. Then a penalty function strategy is adopted to deal with the violation of the constraint solutions. In order to verify the effectiveness of the proposed algorithm, the BPSO algorithm based on the Z-shaped transfer function with different parameters was used to solve the typical 0-1 knapsack problems,which is compared with the BPSO algorithm based on the S-shape and the V-shape transfer functions. Simulation experiment results show that the proposed Z-shaped probability transfer function improves the convergence speed and optimization accuracy of the BPSO algorithm.