A novel multi-mutation binary particle swarm optimization for 0/1 knapsack problem

Particle swarm optimization (PSO) algorithm as a novel computational intelligence technique has been applied successfully in many continuous optimization problems. Then the binary PSO (BPSO) is developed and Qi presented a modified binary PSO (QBPSO). As the two algorithms have not a satisfactory optimization capability, here in order to tackle the 0/1 knapsack problem effectively, multi mutation strategy including single mutation operator and full mutation operator binary particle swarm optimization (MMBPSO) is proposed based QBPSO algorithm. Single mutation operator can be considered as a microcosmic mutation, which adjusts the particle in local bit with a random probability. Full mutation operator is a macroscopic mutation that may change particle´s all bits by a random probability. In optimization process, MMBPSO allows the generation of infeasible solutions, and uses two methods called greedy transform algorithm and penalty function method to produce the best outcomes for constraint handling, respectively. The simulation results for a series of benchmark 0/1 knapsack problems show that the proposed MMBPSO outperforms the traditional binary PSO algorithm and QBPSO, especially with the increasing quantity of the goods, as MMBPSO can effectively escape from the local optima to avoid premature convergence and obtain better solutions.