摘要
针对经典的图着色问题,在蚁群算法的基础上结合量子计算提出一种求解图着色问题的量子蚁群算法.将量子比特和量子逻辑门引入到蚁群算法中,较好地避免了蚁群算法搜索易陷入局部极小的缺陷,并显著加快了算法的运算速度.通过图着色实例的大量仿真实验,表明算法对图着色问题的求解是可行的、有效的,且具有通用性.
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.
出处
《运筹学学报》
CSCD
北大核心
2013年第2期19-26,共8页
Operations Research Transactions
基金
国家自然科学基金(No.70871081)
上海市重点学科建设(No.S30504)
上海市研究生创新基金(No.JWCXSL1201)
上海市一流学科建设(No.S1201YLXK)
关键词
图着色
蚁群算法
量子计算
量子蚁群算法
graph coloring
ant colony algorithm
quantum computing
quantuminspired ant colony algorithm
