A Modified Binary Crow Search Algorithm for Solving the Graph Coloring Problem

A Modified Binary Crow Search Algorithm for Solving the Graph Coloring Problem

Yassine Meraihi (University of M'Hamed Bougara, Boumerdes, Algeria), Mohammed Mahseur (University of Sciences and Technology Houari Boumediene, Bab Ezzouar, Algeria) and Dalila Acheli (University of M'Hamed Bougara, Boumerdes, Algeria)
Copyright: © 2020 |Pages: 19
DOI: 10.4018/IJAEC.2020040103

Abstract

The graph coloring problem (GCP) is a well-known classical combinatorial optimization problem in graph theory. It is known to be an NP-Hard problem, so many heuristic algorithms have been employed to solve this problem. This article proposes a modified binary crow search algorithm (MBCSA) to solve the graph coloring problem. First, the binary crow search algorithm is obtained from the original crow search algorithm using the V-shaped transfer function and the discretization method. Second, we use chaotic maps to choose the right values of the flight length (FL) and the awareness probability (AP). Third, we adopt the Gaussian distribution method to replace the random variables used for updating the position of the crows. The aim of these contributions is to avoid the premature convergence to local optima and ensure the diversity of the solutions. To evaluate the performance of our algorithm, we use the well-known DIMACS benchmark graph coloring instances. The simulation results reveal the efficiency of our proposed algorithm in comparison with other existing algorithms in the literature.
Article Preview
Top

1. Introduction

The graph coloring problem (GCP) is one of the most interesting and difficult combinatorial optimization problems in computer science, mathematics, and operations research. It has been widely used for modeling and solving many significant real-world problems like time tabling (de Werra, An introduction to timetabling, 1985), scheduling (Lotfi & Sarin, 1986), (Dowsland & Thompson, 2005), computer register allocation (Chaitin, Cocke, Hopkins, & Markstein, 1981), (de Werra, Eisenbeis, Lelait, & Marmol, 1999), radio frequency assignment (Gamst, 1986), (Smith, Hurley, & Thiel, 1998), printed circuit board-testing (Garey, Johnson, & So, 1976), communication networks (Woo, Su, & Newman-Wolfe, 1991), and many others. The graph coloring problem consists in assigning a color to each vertex of a given graph with the limitation that no two adjacent vertices gain same colors and the number of different colors used is minimized. The minimum number of colors by which a graph is colored is called its chromatic number, it is denoted by χ(G). A graph G is K-colorable, if it can be legally colored using at most K colors. The problem of finding the chromatic number χ(G) of any graph is known to be an NP-Hard problem (Garey & Johnson, 1979) and has recently drawn an increasing attention from researchers, so several methods have been adopted for solving this problem including greedy constructive approaches, local search heuristics, metaheuristics, and hybrid approaches.

Constructive approaches are based on greedy approach which color the vertices of the graph one by one using a predefined greedy function. The most constructive algorithms employed to solve the GCP are the Recursive Largest First algorithm (RLF) proposed by Leighton (Leighton, 1979) and the largest saturation degree algorithm (DSATUR) developed by Brélaz (Brélaz, 1979). These constructive methods are recently used to generate initial solutions for advanced metaheuristic.

A large number of local search methods have been widely proposed for solving the GCP. The Tabu Search Algorithm proposed by Hertz and Werra (Hertz & de Werra, 1987) was the first local search algorithm applied to solve the graph coloring problem. It is called TABUCOL and has been enhanced by several authors and used as a subcomponent of more other graph coloring algorithms.

Moreover, many efficient metaheuristics such as Genetic Algorithm (GA) (Abbasian & Mouhoub, 2013), (Zhang, Qiu, Li, & Liu, 2014), Cuckoo Search algorithm (CS) (Zhou, Zheng, Luo, & Wu, 2013), (Djelloul, Layeb, & Chikhi, 2014), (Mahmoudi & Lotfi, 2015), Artificial Bee Colony (ABC) (Faraji & Javadi, 2011), (Dorrigiv & Markib, 2012), Particle Swarm Optimization (PSO) (Aoki, Aranha, & Kanoh, 2015), Memetic Algorithm (MA) (Lü & Hao, 2010), and combining algorithms (Mabrouk, Hasni, & Mahjoub, 2009), (Ge, Wei, Tian, & Huang, 2010), (Qin, Yin, & Ban, 2011), (Douiri & Elbernoussi, 2015) have been employed to solve the Graph coloring problem.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 12: 4 Issues (2021): Forthcoming, Available for Pre-Order
Volume 11: 4 Issues (2020): 3 Released, 1 Forthcoming
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing