Hybrid Genetic Approach for Solving Fuzzy Graph Coloring Problem

Introduction And Background

The Graph coloring is highly studied as a combinatorial optimization problem (Pardalos, 1998). Several practical problem can be modeled by graph coloring such as traffic light signal, frequency assignment problem (Roberts, 1979), register allocation (Chaitin, 1981), etc. It includes both vertex coloring and edge coloring. However, the term graph coloring usually refers to vertex coloring rather than edge coloring (Jensen, 2011).

The objective of the graph coloring problem (GCP) is to find minimum number of vertices clusters with respect to the adjacency constraint in such a way that two connected vertices cannot be in the same cluster, each cluster use a color to mark his vertices.

A graph is called a k-colored graph, if accept a k-coloring, and k is called the chromatic number χ when it is the minimum possible color for coloring the graph.

The chromatic number is given by the following formula:

The graph coloring problems are very interesting from the theoretical standpoint since they are a class of NP-complete problems that also belong to constraint satisfaction problems (Garey, 2002).

The coloring problem in the real world applications are not always made of sure relation between items so connection between vertices should not be defined in connected or not connected but can be presented in a certain degree of connection.

The fuzzy graph coloring problem (FGC) is an extension of the GCP introduced for the first time by Kaufmann (Kaufmann, 1976), while Rosenfeld (Rosenfeld, 1975) presented another developed definition, including fuzzy vertices and fuzzy edges. Generally, Fuzzy graph can be defined by three ways fuzzy set of vertices with crisp edges or fuzzy edges with crisp vertices set or fuzzy vertices and fuzzy edges (Chentoufi, 2007). In this paper we deal with crisp vertices and fuzzy edges.

In past years, many works deal with the fuzzy graph coloring in the literature such as (Munoz, 2005), where The concept of chromatic number of fuzzy graph was introduced in two different approaches, the first one is based on the successive coloring functions of crisp graphs, the second approach is based on an extension of the concept of coloring function by means of a distance defined between colors. In addition (Eslahchi, 2006) defined the chromatic fuzzy sum and strength of fuzzy graph and to color the fuzzy graph they separate the vertices into different classes and the number of distinct color classes is the fuzzy chromatic number. The authors in (Meirong, 2015) designed a new algorithm using a semi-tensor product and α-cuts with two conditions for the fuzzy graph to find all the feasible coloring schemes. Furthermore, (Gómez, 2006) deal with the image classification by conceiving it as a fuzzy graph problem and define it on a set of pixels where fuzzy edges represent the distance between pixels to get a more flexible hierarchical structure of colors. Moreover, (Keshavarz, 2016) worked on fuzzy graphs coloring problem, with crisp vertices and fuzzy edges, they formulated a binary programming problem and a hybrid local search genetic algorithm to solve the binary programming. In this work a hybrid solution is proposed to solve the fuzzy graph coloring using the genetic algorithm and the greedy sequential concept.

Genetic algorithm is a metaheuristic that belongs to a large class of evolutionary algorithms, inspired by the process of natural selection according to Darwin's evolution theory, for solving both constrained and unconstrained optimization problems (Mitchell 1998). The genetic algorithm is often used to generate high-quality solutions. The process of this evolutionary algorithm start with generating a random initial generation made of suggested solution called chromosomes, to measure the quality of these solutions a fitness function is used to evaluate chromosomes. In each generation, parent selection methods provide chromosomes for crossover to create off-springs for the next generation. Next a mutation function modifies randomly a minority of off-springs. The next generation will be composed of the new off-springs and an elite selection of the parent generation. Commonly, the algorithm is completed when a maximum number of generations is produced, or a satisfactory fitness level is reached.

The greedy sequential algorithm (GSA) is a heuristic, where the vertices of the graph are labeled according to some specific order and assigns the smallest possible color to a vertex that has not been assigned to its neighbors. Such ordering is called a coloring heuristic (Erciyes, 2013).