摘要： 针对具有NP难度的矩形Packing问题，提出一种带变异算子的双种群粒子群算法，该算法将粒子群分为2个不同的子群，使种群在全局和局部都有较好的搜索能力。通过子群重组实现种群间的信息交换。同时在算法中引入变异算子，对产生的局部最优解的邻域进行搜索。实验结果表明，该算法是一种求解矩形Packing问题的高效实用的算法。

关键词: Packing问题, 双群, 粒子群, 变异算子

Abstract: To solve the rectangle packing problem, one of the NP hard problems, a bi-group Particle Swarm Optimization(PSO) algorithm with mutation operator is presented, by searching the two sub-groups which are parallely performed, it can achieve a better location in both overall and local situations. Information is exchanged when sub-groups are reorganized. Meanwhile, mutation operator is adopted to search in the neighborhood of local optimal solution. The effectiveness of this algorithm is demonstrated for rectangle-packing problem through a number of typical computational experiments.

Key words: Packing problem, bi-group, particle swarm, mutation operator

中图分类号: 

• TP18