一种基于子群杂交机制的粒子群算法求解旅行商问题

Sub Swarm and Crossbreed Strategy PSO for TSP

粒子群算法是在借鉴海鸥群落觅食行为基础上发展起来的仿生学优化算法,为求解复杂的组合优化问题提供了一种新的思路。本文提出一种结合粒子群算法结构和求解TSP问题蚁群算法特点的新算法,将多用于连续空间优化的粒子群成功扩展到TSP领域。算法通过杂交粒子选择机制,运用两种不同设计的杂交算子,成功模拟了自然界同物种不同种群间的协作与交流,将多子群策略和子群间杂交操作引入粒子群结构之中,增强算法的寻优能力。实验结果表明,该算法能有效地保证粒子间多样性差异,通过优化信息在子群间顺畅交流,有效地促进整个群落的进化收敛。该算法在解决TSP问题时,无论在收敛性和鲁棒性方面都优于一般的单群体、非杂交算法,是一种优秀的TSP问题解法。最终优化结果均达到TSPLIB中记录的已知最优解。

Particle swarm optimization, a novel simulated evolutionary algorithm, which is based on observations to real seagull swarm behaviors, provides a new method for complicated combinatorial optimization problems. This paper presents a novel algorithm, combining PSO structure and trip building method of ACS named with swarm and crossbreed strategy PSO (SCPSO). It is an attempt to expand PSO to TSP problems. By adding sub-swarm division and crossbreed strategy, our algorithm simulates real life-form crossbreed behaviors. And in this paper, two crossbreed operators and select mechanism of crossbreed particles are designed in order to improve algorithm performance. Experiment results show that our algorithm is efficient. With optimization information spread within sub-swarms, diversity of particles is improved and the whole particle swarm converges faster with greater accuracy. When approaching TSP problems, sub-swarm and crossbreed - PSO (SCPSO) works much better than single swarm PSO and some other algorithms. The final results have reached the optimal solutions recorded in TSPLIB.