A Modified Binary Particle Swarm Optimization for Knapsack Problems

摘要

The Knapsack Problems (KPs) are classical NP-hard problems in Operations Research having a number of engineering applications. Several traditional as well as population based search algorithms are available in literature for the solution of these problems. In this paper, a new Modified Binary Particle Swarm Optimization (MBPSO) algorithm is proposed for solving KPs, particularly 0–1 Knapsack Problem (KP) and Multidimensional Knapsack Problem (MKP). Compared to the basic Binary Particle Swarm Optimization (BPSO), this improved algorithm introduces a new probability function which maintains the diversity in the swarm and makes it more explorative, effective and efficient in solving KPs. MBPSO is tested through computational experiments over benchmark problems and the results are compared with those of BPSO and a relatively recent modified version of BPSO namely Genotype–Phenotype Modified Binary Particle Swarm Optimization (GPMBPSO). To validate our idea and demonstrate the efficiency of the proposed algorithm for KPs, experiments are carried out with various data instances of KP and MKP and the results are compared with those of BPSO and GPMBPSO.