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

Operations Research Transactions ›› 2013, Vol. 17 ›› Issue (2): 19-26.

• Original Articles • Previous Articles Next Articles

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

CLC Number:

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

References

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.

A quantum-inspired ant colony algorithm for graph coloring problem

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 0

Recommended Articles

Metrics

Comments