付 聪，沙 伟，张海霞，杨 亚

（河海大学物联网工程学院，常州213022）

基于差分进化的离散粒子群算法求解TSP问题

付 聪，沙 伟，张海霞，杨 亚

（河海大学物联网工程学院，常州213022）

针对TSP问题，结合离散粒子群算法和差分进化算法各自的特点，提出了基于差分进化的离散粒子群算法。该算法先利用差分进化算法的变异、选择算子产生新的群体，再通过离散粒子群算法和交叉及选择算子进行局部搜索。通过对标准的30个城市进行实验，实验结果表明，该优化算法在求解TSP问题上有很好的性能。

优化算法；离散粒子群；差分进化；旅行商问题

1 引 言

TSP问题是诸多领域内出现的多种复杂问题的集中概括和简化，是图论、运筹学和组合优化中的NP难问题，常被用于对智能启发式算法有效性的验证。虽然它的数学描述很简单，但却很难精确求出最优解，另一方面很多研究领域出现的复杂优化问题可以被抽象概括为TSP问题加以求解，因此找到能够有效解决TSP问题的方法，在理论上和实际应用中都很有价值［1］。

目前求解TSP问题的算法大致可以分两类：一类是局部启发式算法，比如2-opt、3-opt、LK算法等，这类算法的优点是寻找最优解效率非常高，但是由于过分依赖于问题，容易陷入局部最优；另外一类是智能优化算法，例如遗传算法、差分进化算法、蚁群算法、粒子群算法等，这类方法独立于问题，目前已经取得了些阶段性的成果，而差分进化算法和粒子群算法都是近年的研究热点［2］。基于以上分析，提出基于差分进化的离散粒子群算法，并应用到TSP问题中，取得了满意的效果。……