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 particles 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.
Words: Binary PSO Multi-Mutation Greedy transform algorithm and penalty function method 0/1 Knapsack Problem
Zhuangkuo Li Ning Li
School of management, Guilin University of Electronic Technology, Guilin 541004, China
国际会议
2009年中国控制与决策会议(2009 Chinese Control and Decision Conference)
广西桂林
英文
3042-3047
2009-06-17（万方平台首次上网日期，不代表论文的发表时间）