求解二次分配问题的离散粒子群优化算法

Discrete Particle Swarm Optimization Algorithm for QAP

提出了一种求解二次分配问题的离散粒子群优化算法.根据二次分配问题及离散量的特点,重新定义了粒子的位置、速度等量及其运算规则,为抑制早熟停滞现象,为粒子和粒子群分别定义了个体多样性和平均多样性.算法中定义了排斥算子来保持粒子群的多样性,使用局部搜索算子来提高算法的局部求精能力,使算法在空间勘探和局部求精间取得了较好的平衡.在QAPLIB的实例上的仿真结果表明,离散粒子群优化算法具有良好的性能.

A discrete particle swarm optimization algorithm is presented to tackle the quadratic assignment problem （QAP）. Based on the characteristics of QAP and discrete variable, this paper redefines particles＇ position, velocity, and their operation rules. In order to restrain premature stagnation, individualdiversity of particle and average-diversity of particle swarm are defined. A repulsion operator is designed to keep the diversity of particle swarm, and an efficient local search operator is used to improve the algorithm＇s intensification ability. Using those operators, the proposed algorithm can get good balance between exploration and exploitation. Experiments were performed on QAP instances from QAPLIB. The simulation results show that it can produce good results.