Journal of East China Normal University(Natural Science) ›› 2020, Vol. 2020 ›› Issue (6): 90-98.doi: 10.3969/j.issn.1000-5641.201921025

• Computer Science • Previous Articles     Next Articles

Study of an improved hybrid particle swarm optimization algorithm for solving 0-1 knapsack problems

YAO Ruoxia, XUE Dan, XIE Juanying, FAN Hong   

  1. School of Computer Science, Shaanxi Normal University, Xi’an 710119, China
  • Received:2019-12-06 Published:2020-12-01

Abstract: In order to solve 0-1 knapsack problems with greater stability and efficiency, we propose a BPSOSA-CGOO (Hybrid optimization algorithm based on the BPSO (binary particle swarm optimization), the simulated annealing (SA) algorithm and the combined greedy optimization operator (CGOO)) algorithm which is composed of the BPSO, the greedy optimization strategy, and the simulated annealing algorithm. Simulation experiments of 9 groups of different dimensions show that the BPSOSA-CGOO algorithm can solve 0-1 knapsack problems efficiently for small population sizes and iteration times. Meanwhile, it was observed that experiments performed with the algorithm can also find a better solution for 20-dimensional test data. In independent and repeated experiments, the BPSOSA-CGOO algorithm can achieve the optimal solution with high probability for both low-dimensional and high-dimensional knapsack problems; hence, stability and reliability is significantly improved when using the BPSOSA-CGOO algorithm to solve high-dimensional knapsack problems.

Key words: knapsack problem, particle swarm optimization algorithm, greedy optimization strategy, simulated annealing algorithm

CLC Number: