计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (32): 42-44.

• 研究、探讨 • 上一篇    下一篇

求解TSP的新量子蚁群算法

李 絮,刘争艳,谭拂晓   

  1. 阜阳师范学院 计算机与信息学院,安徽 阜阳 236041
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-11-11 发布日期:2011-11-11

Novel quantum ant colony algorithm for TSP

LI Xu,LIU Zhengyan,TAN Fuxiao   

  1. School of Computer and Information,Fuyang Teachers College,Fuyang,Anhui 236041,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2011-11-11 Published:2011-11-11

摘要: 鉴于蚁群算法(ACA)在求解TSP时表现出的优越性,以及量子进化算法(QEA)在求解组合优化问题时表现出的高效性,将ACA与QEA的算法思想进行融合,提出一种新的求解TSP的量子蚁群算法。该算法对各路径上的信息素进行量子比特编码,设计了一种新的信息素表示方式,即量子信息素;采用量子旋转门及最优路径对信息素进行更新,加快算法收敛速度;为了避免搜索陷入局部最优,设计了一种量子交叉策略,以改善种群信息结构。仿真实验结果表明了该算法具有较快的收敛速度和全局寻优能力,性能明显优于ACS。

关键词: 量子进化, 蚁群算法, 旅行商问题(TSP), 组合优化

Abstract: Ant Colony Algorithm(ACA) demonstrates the superiority in solving TSP,and Quantum Evolution Algorithm(QEA) has the performance of high efficiency on combinational optimization problems,so combining the thought of ACA with QEA,a novel quantum ant colony algorithm for TSP is proposed.In this algorithm,the pheromone on each path is encoded by a group of quantum bits,and a new pheromone representation is designed,called quantum pheromone.The quantum rotation gate and the best tour are applied to update the pheromone so as to accelerate its convergence speed.To avoid the search falling into local optimum,the strategy of quantum crossover is designed to improve the information structure of population.Simulation results show that the algorithm has fast convergence speed and global optimal ability,and the algorithm is more effective than ACS.

Key words: quantum evolution, ant colony algorithm, Traveling Salesman Problem(TSP), combinational optimization