Quantum inspired cuckoo search algorithm for graph colouring problem. (2015)

• Record Type: Journal Article
• Authors: Djelloul, Halima; Layeb, Abdesslem; Chikhi, Salim
• Is Part Of: International journal of bio-inspired computation. Volume 7:Number 3(2015)
• Page Start: 183
• Page End: 194
• Publication Date: 2015
• Subjects: graph colouring problem -- GCP -- cuckoo search algorithm -- quantum computing -- heuristics -- hybrid algorithms -- combinatorial optimisation -- qubit representation -- adjacency matrix -- hybrid quantum mutation; Biologically-inspired computing -- Periodicals; Computational biology -- Periodicals; 572.0285
• Languages: English
• ISSNs: 1758-0366

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.