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 Xiaofeng1,*,MA Liang1   

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