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

摘要

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