Quantum-Inspired Evolutionary Algorithm to Solve Graph Coloring Problem

MOZAMMEL, H. A KHAN and PRONAYA, PROSUN DAS (2014) Quantum-Inspired Evolutionary Algorithm to Solve Graph Coloring Problem. In: International Conference on Advances In Computing, Electronics and Electrical Technology CEET 2014, 02 - 03 August, 2014, Kuala Lumpur, Malaysia.

20150620_122415.pdf - Published Version

Download (896kB) | Preview
Official URL: https://www.seekdl.org/conferences/paper/details/3...


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.

Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: quantum-inspired evolutionary algorithm (QEA), graph coloring problem (GCP), combinatorial optimization, Qbit representation, Q-gate.
Depositing User: Mr. John Steve
Date Deposited: 27 May 2019 08:31
Last Modified: 27 May 2019 08:31
URI: http://publications.theired.org/id/eprint/2777

Actions (login required)

View Item View Item