王启明，李玮瑶

（平顶山学院计算机科学与技术学院，平顶山467000）

基于改进量子蚁群算法的TSP求解问题研究

王启明，李玮瑶

（平顶山学院计算机科学与技术学院，平顶山467000）

TSP问题是一个组合优化问题，该问题具有NP计算复杂性，运用量子蚁群算法求解该问题时易陷入局部最优和收敛速度慢的问题。因此提出一种基于博弈论的量子蚁群算法（GQACA），该算法采用重复博弈模型，在重复博弈中产生一个博弈序列，使得每次博弈都能够产生最大效益，并得到相应博弈过程的纳什均衡。把该算法应用于TSP求解，实验结果表明本文中GQACA算法的收敛精度和稳定性均要优于其他量子蚁群算法。

改进；博弈论；蚁群算法；旅行商问题

1 引 言

旅行商问题，即TSP问题（Travelling Salesman Problem），又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一［1-2］。可以描述为：已知n个城市之间的相互距离，现有一推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发的城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？解决旅行商问题的各种优化算法，都是通过牺牲解的精确性来换取较少的耗时［3］。其他一些启发式的搜索算法则依赖于特定的问题域，缺乏通用性。相比较而言，遗传算法是一种通用性很好的全局搜索算法，因此遗传算法是解决旅行商问题的一种不错的算法。贾瑞玉等分析了量子蚁群算法的优缺点，提出一种新的求解旅行商问题（Traveling Salesman Problem，TSP）的混合量子蚁群算法［4-5］。……