Conference Proceedings

International Conference on Advances In Computing, Electronics and Electrical Technology CEET 2014

Quantum-Inspired Evolutionary Algorithm to Solve Graph Coloring Problem

Author(s) : MOZAMMEL H. A. KHAN, PRONAYA PROSUN DAS

Abstract

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.

Conference Title : International Conference on Advances In Computing, Electronics and Electrical Technology CEET 2014
Conference Date(s) : 02 - 03 August, 2014
Place : Hotel G Tower, Kuala Lumpur, Malaysia
No fo Author(s) : 2
DOI : 10.15224/978-1-63248-005-7-31
Page(s) : 21 - 25
Electronic ISBN : 978-1-63248-005-7
Views : 987   |   Download(s) : 203