并行免疫离散粒子群优化算法求解背包问题

Parallel Binary Particle Swarm Optimization Algorithm Based on Immunity for Solving Knapsack Problem

针对离散变量的优化问题,提出了一种改进的二进制混合粒子群优化算法(MHBPSO)。MHBPSO算法利用生物免疫机理和并行运算原理简化算法结构,并针对后期可能出现局部收敛、停滞的问题,从保持粒子群位置的多样性入手,引入了鲶鱼效应和交叉变异操作。仿真实验比较了几种成熟的离散优化算法在解决典型0-1背包问题时的性能。结果表明MHBPSO算法结构简单、收敛速度快、全局寻优能力强,是一种解决离散优化问题的有效方法。

To realize optimization problems with discrete binary variables, a modified hybrid binary particle swarm optimization （MHBPSO） was proposed. To simplify the structure of MtlBPSO algorithm, the theories of immunity in biology and parallel computation were introduced. The catfish effect and the operation of crossover and mutation were also embedded in order to avoid the local convergence and stagnation and maintain the diversity of swarm＇s searching positions during the later period of MHBPSO algorithm. Simulation performance of different mature discrete optimization algorithms were compared by solving classical 0-1 knapsacks problems. The simulation results show that MHBPSO has a simple structure, high convergence speed and superior global optimization capability, which is an efficient method for discrete optimization problems.