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

Study of TSP Problem Solving Based on Improved Quantum Ant Colony Algorithm

作　　者：王启明[1] 李玮瑶[1] 

机构地区：[1]平顶山学院计算机科学与技术学院,平顶山467000

出　　处：《微处理机》2015年第3期31-33,共3页Microprocessors

摘　　要：TSP问题是一个组合优化问题,该问题具有NP计算复杂性,运用量子蚁群算法求解该问题时易陷入局部最优和收敛速度慢的问题。因此提出一种基于博弈论的量子蚁群算法(GQACA),该算法采用重复博弈模型,在重复博弈中产生一个博弈序列,使得每次博弈都能够产生最大效益,并得到相应博弈过程的纳什均衡。把该算法应用于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.

关 键 词：改进 博弈论 蚁群算法 旅行商问题 

分 类 号：TN393[电子电信—物理电子学]