Title: Quantum inspired cuckoo search algorithm for graph colouring problem

Authors: Halima Djelloul; Abdesslem Layeb; Salim Chikhi

Addresses: Department of Information and Applications, MISC Laboratory, University of Constantine II, Ali Mendjeli City, Constantine, 25000, Algeria ' Department of Information and Applications, MISC Laboratory, University of Constantine II, Ali Mendjeli City, Constantine, 25000, Algeria ' Department of Information and Applications, MISC Laboratory, University of Constantine II, Ali Mendjeli City, Constantine, 25000, Algeria

Abstract: The graph colouring problem (GCP) is one of the most interesting, studied and difficult combinatorial optimisation problems. That is why, several approaches were developed for solving this problem, including exact approaches, heuristic approaches, metaheuristics and hybrid approaches. In this paper, we try to solve the graph colouring problem using a new approach based on the quantum inspired cuckoo search algorithm. The first contribution consists in defining an appropriate quantum representation based on qubit representation to represent the graph colouring solutions. The second contribution is the proposition of a novel measure operator based on the adjacency matrix. The third contribution involves the proposition of an adapted hybrid quantum mutation operation. To show the feasibility and the effectiveness of the algorithm, we have used the standard DIMACS benchmark, and the obtained results are very encouraging.

Keywords: graph colouring problem; GCP; cuckoo search algorithm; quantum computing; heuristics; hybrid algorithms; combinatorial optimisation; qubit representation; adjacency matrix; hybrid quantum mutation.

DOI: 10.1504/IJBIC.2015.069554

International Journal of Bio-Inspired Computation, 2015 Vol.7 No.3, pp.183 - 194

Received: 31 May 2013
Accepted: 19 Jan 2014
Published online: 26 May 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article