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

摘要

TSP 问题是一个组合优化问题，该问题具有 NP 计算复杂性，运用量子蚁群算法求解该问题时易陷入局部最优和收敛速度慢的问题。因此提出一种基于博弈论的量子蚁群算法（GQA-CA），该算法采用重复博弈模型，在重复博弈中产生一个博弈序列，使得每次博弈都能够产生最大效益，并得到相应博弈过程的纳什均衡。把该算法应用于 TSP 求解，实验结果表明本文中 GQACA算法的收敛精度和稳定性均要优于其他量子蚁群算法。%TST,as a combinatorial optimization problem,is solved by Quantum ant colony algorithm which is easy to fall into the local optimum and slow convergence.The quantum ant colony algorithm, based on game theory (GQACA),is put forward in this paper.It uses the repeated game to create the repeated game sequence for maximum benefit in each game,and get the corresponding game process of Nash equilibrium.The typical test functions are used for GQACA algorithm optimization performance experiment testing.The experimental results show that the GQACA convergence precision and stability of the algorithm are better than QACA algorithm and ACA one.