Journals Proceedings

International Journal of Advances in Computer Science and Its Applications

Quantum-Inspired Evolutionary Algorithm to Solve Graph Coloring Problem



Graph Coloring Problem (GCP) bears an enormous significance to the researchers in the field of soft computing. In this paper, we demonstrate a Quantum-Inspired Evolutionary Algorithm (QEA) to solve GCP. We use two dimensional arrays of Q-bits called Q-bit individual to produce binary individual. Q-gate operation is applied as a variation operator on Q-bit individuals. In traditional evolutionary algorithm (EA) for GCP, k-coloring approach is used and the EA is run several times for decreasing value of k until lowest possible k is reached. In our QEA, we start with the number of colors equal to the theoretical upper bound of the chromatic number, which is maximum out-degree + 1, and during evolution some colors are made unused to reduce the number of color in each generation. As a result, solution is found in a single run. We test 36 datasets from DIMACS benchmark and compare the result with several recent works. For five datasets, our algorithm obtains better solution than other.

No fo Author(s) : 2
Page(s) : 66 - 70
Electronic ISSN : 2250 - 3765
Volume 4 : Issue 4
Views : 338   |   Download(s) : 143