Solving Graph Coloring Problem Using an Enhanced Binary Dragonfly Algorithm

Solving Graph Coloring Problem Using an Enhanced Binary Dragonfly Algorithm

Karim Baiche (Applied Automation Laboratory, University of MHamed Bougara Boumerdes, Boumerdes, Algeria), Yassine Meraihi (Department of Automation, Applied Automation Laboratory, University of M'Hamed Bougara Boumerdes, Boumerdes, Algeria), Manolo Dulva Hina (ECE Paris School of Engineering, Paris, France), Amar Ramdane-Cherif (LISV Laboratory, University of Versailles St-Quentin-en-Yvelines, Versailles, France) and Mohammed Mahseur (University of Sciences and Technology Houari Boumediene, Bab Ezzouar, Algeria)
Copyright: © 2019 |Pages: 23
DOI: 10.4018/IJSIR.2019070102

Abstract

The graph coloring problem (GCP) is one of the most interesting classical combinatorial optimization problems in graph theory. It is known to be an NP-Hard problem, so many heuristic algorithms have been employed to solve this problem. In this article, the authors propose a new enhanced binary dragonfly algorithm to solve the graph coloring problem. The binary dragonfly algorithm has been enhanced by introducing two modifications. First, the authors use the Gaussian distribution random selection method for choosing the right value of the inertia weight w used to update the step vector (∆X). Second, the authors adopt chaotic maps to determine the random parameters s, a, c, f, and e. The aim of these modifications is to improve the performance and the efficiency of the binary dragonfly algorithm and ensure the diversity of solutions. The authors consider the well-known DIMACS benchmark graph coloring instances to evaluate the performance of their algorithm. The simulation results reveal the effectiveness and the successfulness of the proposed algorithm in comparison with some well-known algorithms in the literature.
Article Preview
Top

1. Introduction

The Graph Coloring Problem (GCP) is a very well-known NP-Hard combinatorial optimization problem in computer science, mathematics, and operations research. It deals with assigning a color to each node of a given graph with the restriction that no two adjacent nodes are colored with the same color and that the number of different colors used is minimized. The minimum number of colors by which a graph can be colored is called its chromatic number and it is denoted by χ(G). A graph G is K-colorable if it can be legally colored with at most K colors. The graph coloring problem has recently drawn an increasing attention from researchers and has been widely used to model and solve many significant real-world problems, such as time tabling (de Werra, 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), noise reduction in VLSI circuits (Maitra, Pal, Bhattacharyya, & Kim, 2010), channel routing (Sen Sarma, Mandal, & Seth, 1994), and communication networks (Woo, Su, & Newman-Wolfe, 1991).

Several approaches have been adopted in solving this problem including greedy constructive approaches, local search heuristics, meta-heuristics and hybrid approaches.

The two 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 methods are based on greedy approach which colors the nodes of the graph one at time using a predefined greedy function. Recently, these approaches have been used to generate initial solutions for advanced evolutionary algorithms.

Local search heuristics have been widely proposed to solve the GCP. Tabu Search Algorithm proposed by Hertz and de 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 improved by several researchers and used as a subcomponent of more graph coloring algorithms.

Moreover, many efficient meta-heuristics such as Genetic Algorithm (GA) (Abbasian & Mouhoub, 2013), Cuckoo Search algorithm (CS) (Mahmoudi & Lotfi, 2015), Artificial Bee Colony (ABC) (Faraji & Javadi, 2011), Ant Based Algorithm(ABA) (Bui, Nguyen, Patel, & Phan, 2008), Particle Swarm Optimization (PSO) (Agrawal & Agrawal, 2015), Bat Algorithm (BA) (Djelloul, Sabba, & Chikhi, 2014), Memetic Algorithm (MA) (Lü & Hao, 2010), Firefly Algorithm (FA) (Chen & Kanoh, 2017), and combining algorithms (Douiri & Elbernoussi, 2015; Marappan & Sethumadhavan, 2018) have been employed in solving the Graph coloring problem.

Abbasian and Mouhoub (Abbasian & Mouhoub, 2013) proposed a Hierarchical approach based on Parallel Genetic Algorithms (HPGAs) for solving the GCP. In this approach, a novel estimator is implemented to predict an upper-bound for the graph’s chromatic number. Furthermore, an extension of the genetic algorithm, namely the Genetic Modification (GM) and the parental success crossover operator have been proposed. Experimental results showed that the proposed approach was very accurate and faster in solving this problem.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 11: 4 Issues (2020): 2 Released, 2 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