求解旅行商问题的改进型量子蚁群算法  

Improved quantum ant colony algorithm for Traveling Salesman Problem

作　　者：万正宜 彭玉旭[1] WAN Zhengyi;PENG Yuxu(Institute of Computer & Communication Engineering, Changsha University of Sciences & Technology, Changsha 410114, China)

机构地区：[1]长沙理工大学计算机与通信工程学院,长沙410114

出　　处：《计算机工程与应用》2016年第22期59-63,122,共6页Computer Engineering and Applications

基　　金：湖南省自然科学基金(No.14JJ7043)

摘　　要：针对传统量子蚁群算法在求解TSP时容易陷入局部最优以及收敛速度较慢,提出了一种求解旅行商问题的改进型量子蚁群算法(IQACA)。该算法设计了一种新信息素挥发因子的自适应动态更新策略,对信息素进行动态更新;并采用一种新的量子旋转门对量子概率幅值的收敛趋势进行改变。通过三个基本函数极值优化仿真与传统量子蚁群算法进行对比,证明算法性能较优。基于TSPLIB的仿真实验与其他几种算法进行比较,结果表明,算法具有较快的收敛速度,提高了解的全局性,有效避免了算法陷入局部最优。Against the disadvantages of being easy to fall into local optimum and slow convergence speed on solvingTraveling Salesman Problem(TSP)with traditional quantum ant colony algorithm(QACA), this paper proposes an ImprovedQuantum Ant Colony Algorithm(IQACA)on solving Traveling Salesman Problem. This algorithm designs a new strategywhich is used to update pheromone volatilization factor adaptively, and it can update the pheromone dynamically. Furthermorea new quantum revolving door is adopted to change the convergence tend of quantum probability amplitude. Threebasic function extremum optimization simulation compared with traditional quantum ant colony algorithm, proves that thepaper’s algorithm has better performance. Experimental results based on TSP library(TSPLIB)show that both convergencerate and optimized global results are much improved compared with other algorithms, and it can avoid falling into localoptimum effectively.

关 键 词：TSP 量子蚁群算法 改进型量子蚁群算法 量子旋转门 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]