求解图着色问题的量子蚁群算法

摘要

A quantum-inspired ant colony algorithm (QACA) for the classic graph coloring problem is proposed based upon the combination of ant colony optimization and quantum computing.The quantum bits and quantum logic gates are introduced to the ant colony algorithm (ACA),and the disadvantage of getting into the local optimum can be effectively avoided.The computational speed of the algorithm is therefore significantly improved.Series of simulation instances of the graph coloring problem are tested.And the results show that the QACA is a feasible,effective and versatile method for solving the graph coloring problem.%针对经典的图着色问题,在蚁群算法的基础上结合量子计算提出一种求解图着色问题的量子蚁群算法.将量子比特和量子逻辑门引入到蚁群算法中,较好地避免了蚁群算法搜索易陷入局部极小的缺陷,并显著加快了算法的运算速度.通过图着色实例的大量仿真实验,表明算法对图着色问题的求解是可行的、有效的,且具有通用性.