Abstract: Aiming at the Traveling Salesman Problem based on ant colony optimization which is easy to fall into local optimums and has a slow convergence rate, a hybrid quantum ant colony optimization algorithm is presented. In this algorithm, the pheromone on each path is encoded by a group of quantum bits, the quantum rotation gate and ant’s tour are used to update the pheromone so as to accelerate its convergence speed. To avoid the search falling into local optimum, the new neighborhood exchange strategy is designed to improve solution efficiency. Some cases from the TSP library（TSPLIB） are used to experiment, the results show that the algorithm has rapider convergence speed and higher accuracy than the classical ant colony algorithm.

Key words: Quantum Ant Colony Algorithm, neighborhood exchange strategy, Traveling Salesman Problem

摘要： 针对蚁群算法求解旅行商问题时易陷入局部最优和收敛速度慢的问题，提出一种新的求解旅行商问题的混合量子蚁群算法。该算法采用量子比特的概率幅对各路径上的信息素进行编码，采用量子旋转门及蚂蚁走过的路径对信息素进行更新，设计一种新的变换邻域准则。基于TSPLIB的仿真实验结果表明了该算法具有较快的收敛速度和求解精度。

关键词: 量子蚁群算法, 变换邻域准则, 旅行商问题