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

运筹学学报 ›› 2013, Vol. 17 ›› Issue (2): 19-26.

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

何小锋^1,*，马良¹

1. 上海理工大学管理学院，上海 200093

收稿日期:2011-06-14 出版日期:2013-06-15 发布日期:2013-06-15
通讯作者: 何小锋 E-mail:hexife@126.com
基金资助:
国家自然科学基金 (No. 70871081)；上海市重点学科建设 (No. S30504)；上海市研究生创新基金 (No. JWCXSL1201)；上海市一流学科建设 (No. S1201YLXK)

A quantum-inspired ant colony algorithm for graph coloring problem

HE Xiaofeng^1,*,MA Liang¹

1. School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China

Received:2011-06-14 Online:2013-06-15 Published:2013-06-15

摘要/Abstract

摘要： 针对经典的图着色问题，在蚁群算法的基础上结合量子计算提出一种求解图着色问题的量子蚁群算法. 将量子比特和量子逻辑门引入到蚁群算法中，较好地避免了蚁群算法搜索易陷入局部极小的缺陷，并显著加快了算法的运算速度. 通过图着色实例的大量仿真实验，表明算法对图着色问题的求解是可行的、有效的，且具有通用性.

关键词: 图着色, 蚁群算法, 量子计算, 量子蚁群算法

Abstract: 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.

Key words: graph coloring, ant colony algorithm, quantum computing, quantum-inspired ant colony algorithm

中图分类号:

何小锋，马良. 求解图着色问题的量子蚁群算法[J]. 运筹学学报, 2013, 17(2): 19-26.

HE Xiaofeng,MA Liang. A quantum-inspired ant colony algorithm for graph coloring problem[J]. Operations Research Transactions, 2013, 17(2): 19-26.

参考文献

Bui T N, Nguyen T V H, Patel C M, et al. An ant-based algorithm for coloring graphs [J]. Discrete Applied Mathematics, 2008, 156(2): 190-200.
殷剑宏, 吴开亚. 图论及其算法 [M]. 合肥：中国科技大学出版社, 2003.
兰绍江, 韩丽霞, 王宇平. 图着色问题的混合遗传算法 [J]. 计算机工程与应用, 2008, 44(28): 57-59.
Bui T N, Nguyen T V H, Patel C M, et al. An ant-based algorithm for coloring graphs [J]. Discrete Applied Mathematics, 2008, 156(2): 190-200.
康立山, 谢云, 尤矢勇, 等. 非数值并行算法-模拟退火算法 [M]. 北京：科学出版社, 1998.
张丽, 马良, 石丽娜. 图着色问题的蚂蚁算法研究 [J]. 上海工程技术大学学报, 2009, 23(4): 328-332.
Dowsland K A, Thompson J M. An improved ant colony optimization heuristic for graph colouring [J]. Discrete Applied Mathematics, 2008, 156(3): 313-324.
Bui T N, Nguyen T V H, Patel C M, et al. An ant-based algorithm for coloring graphs [J]. Discrete Applied Mathematics, 2008, 156(2): 190-200.
Titiloye O, Crispin A. Quantum annealing of the graph coloring problem [J]. Discrete Optimization, 2011, 8: 376-384.
马良, 朱刚, 宁爱兵. 蚁群优化算法 [M]. 北京：科学出版社, 2008.
Titiloye O, Crispin A. Quantum annealing of the graph coloring problem [J]. Discrete Optimization, 2011, 8: 376-384.
李士勇, 李盼池. 量子计算与量子优化算法 [M]. 哈尔滨：哈尔滨工业大学出版社, 2009.
林妍, 吴瑾, 樊锁海. 图着色和标号问题的蚁群优化算法 [J]. 数学的实践与认识, 2012, 42(17): 182-191.
D'Hondt E. Quantum approaches to graph colouring [J]. Theoretical Computer Science, 2009, 410(4-5): 302-309.
Titiloye O, Crispin A. Quantum annealing of the graph coloring problem [J]. Discrete Optimization, 2011, 8: 376-384.
K H Han, Kim J H. Quantum-inspired evolutionary algorithm for a class of combinatorial optimization [J]. IEEE Transactions on Evolutionary Computation, 2002, 6(6): 580-593.