一种求解集合组合问题的离散粒子群优化模型

针对变长集合组合优化问题,提出了一种离散粒子群优化模型.该模型将集合的概念和运算引入粒子群优化中,定义了一个可变集合搜索空间,并重新定义了粒子的位置、速度及作用于此空间的运算规则,既保留了粒子群本身的优化特性,又体现了集合组合优化的特点.采用典型的变长集合组合优化问题——背包问题来验证此模型的性能,并与二进制粒子群优化(BPSO)算法进行了对比.结果表明,该模型具有较强的寻优能力和更高的稳定性.

Discrete Particle Swarm Optimization Model for Set-Based Combinatorial Optimization Problems

In order to solve set-based combinatorial problems, a new model of discrete particle swarm optimization is proposed. According to set characteristics, set concepts and operations are introduced into particle swarm optimization. In the model, a search space of variable set is defined and particle’ velocity and location are re-stated. New operators are defined to work on the set search space. For validating it, the model was applied to solve knapsack problem，a typical set-based combinatorial optimization problem. The experiment results demonstrate that the PSO based on the model has great superiority both in searching ability and stability.