Vertex-coloring of fuzzy graphs: A new approach

Abstract

In this paper, a new vertex-coloring problem of a fuzzy graph with crisp vertices and fuzzy edges is studied. Membership degree of a fuzzy edge is interpreted as incompatibility degree of its associated incident vertices. This interpretation can be used to define the concept of total incompatibility. Here, unlike the traditional graph coloring problems, two adjacent vertices can receive same colors; these type of vertices and their associated edge are named incompatible vertices and incompatible edge, respectively. In proposed coloring methodology, the total incompatibility of a vertex-coloring is defined as the sum of incompatibility degrees of all incompatible edges. Then, based on the minimum possible degree of total incompatibilities, fuzzy chromatic number of a fuzzy graph is introduced. In order to find an optimal k-coloring, with minimum degree of total incompatibly, firstly a binary programming problem is formulated. Then, a hybrid local search genetic algorithm is designed to solve the large-size problems. Practical uses of the proposed algorithm are illustrated and analyzed by different-size problems. Finally, a cell site assignment problem, as a real world application of the presented fuzzy graph vertex-coloring, is formulated and solved.

Keywords

Fuzzy graph incompatibility degree fuzzy chromatic number binary programming genetic algorithm

1 Introduction

Graph coloring problem is one of the most studied and well known subjects in discrete and combinatorial optimization domain. There are many practical applications that can be modeled and analyzed by graph coloring problems, some classical applications include wiring of printed circuits, loading problems, resource allocation, frequency assignment problem, a wide variety of scheduling problems and computer register allocation [14]. A vertex coloring of a graph is an assignment of colors to all vertices of the graph, one color to each vertex, so that adjacent vertices are colored differently and the number of colors used is minimized [4]. One of the important and attractive extensions of the graph coloring problems is Coloring a Fuzzy Graph.

The preliminary definition of a fuzzy graph was presented by Kaufmann [9], based on Zadeh’s fuzzy relations [21], but more basic graph-theoretic concepts and their properties were elaborated by Rosenfeld [17]. Many variations of the concepts and definitions are suggested thereafter, mostly under the degree of fuzzy vertices, fuzzy paths, fuzzy trees, fuzzy sub-graphs, complement of a fuzzy graph, etc. (see [1 , 13 and 19]).

Fuzzy Graph Coloring problems are interesting, both from theoretical and practical viewpoints; these problems have been studied by a number of researchers. As a primary work, Bershtein and Bozhenuk [2] introduced the degree of internal stable of fuzzy sub-graph and separation degree of a fuzzy graph by k colors, and based on these concepts defined the fuzzy chromatic set. Then suggested and substantiated a method for finding fuzzy chromatic set of a fuzzy graph. Mũnoz et al. [14] modeled and solved two different fuzzy graph coloring problems by generalizing the classical concept of the (crisp) chromatic number of a graph. In the first problem, utilizing the concept of incompatibility and fuzzy linguistic variables, they defined a coloring function of a fuzzy graph, and presented a simple approach based on the successive coloring functions of the crisp graphs to solve the problem. As a practical application of presented approach, they modelled and analyzed a traffic lights problem. In the second problem Mũnoz et al. [14] extended the concept of coloring function by means of a distance, defined between colors, and analyzed a timetabling problem within this problem.

Ramaswamy and Poornima [16] and Poornima and Ramaswamy [15], emulating the Mũnoz et al.’s work [14], extended vertex-coloring of a fuzzy graph to edge-coloring and total coloring of a fuzzy graph, respectively. Eslahchi and Onagh [3] generalized the concepts of chromatic sum and vertex-strength of a (crisp) graph to fuzzy graphs, and studied some properties of these concepts. They showed that there exists an upper bound for the chromatic fuzzy sum of a fuzzy graph. Gómez et al. [6] described an image as a fuzzy graph, defined on the set of pixels, where fuzzy edges represent the distance between pixels, then proposed a crisp coloring methodology, as the basis for a fuzzy classification of pixels in the fuzzy graph of image.

Recently, Rosyida et al. [18] proposed an approach to determine fuzzy chromatic set of fuzzy graphs, in their method, the fuzzy chromatic set of a fuzzy graph is constructed through its δ-chromatic number. They analyzed and investigated some properties of the proposed fuzzy chromatic set of fuzzy graph. Finally Rosyida et al. [18] proposed a fuzzy chromatic algorithm based on their presented proposed.

In this paper, we introduce a new vertex coloring problem of fuzzy graphs, based on the total incompatibility concept. In order to construct this problem, firstly, the total incompatibility degree of a vertex coloring is defined, then utilizing this degree the fuzzy chromatic number of a finite sequence of colorings is introduced, finally the fuzzy chromatic number of a fuzzy graph is defined.

To find a fuzzy chromatic number of a fuzzy graph, we formulate a binary programming problem, with the purpose of searching a k-coloring with the minimum degree of total incompatibility. By solving this problem for different values of k, we can obtain the fuzzy chromatic number of a fuzzy graph. From the computational complexity point of view, the presented binary programming problem can be solved for fairly-sized graphs using the available Integer Programming libraries, such as CPLEX [8]. However for the large and dense graphs, this problem cannot be solved effectively, using the classical methods. To tackle this issue, we design a Hybrid Local Search Genetic Algorithm (HLSGA) which finds approximate optimal solutions for the problem.

In sum, the major contributions of the presented approach and algorithm are: (1) Presented approach, in addition to the theoretical attitude, has been designed based on the realistic interpretations. (2) Presented approach and its models maintain the properties of the crisp models. In fact, our coloring approach of fuzzy graphs is a reasonable extension of the crisp graph coloring problem. (3) In the presented approach, fuzzy chromatic number of a fuzzy graph is defined based on a realistic aspect. (4) For the first time, here a binary programming problem is formulated and solved to achieve the chromatic number of a fuzzy graph. (5) Presented binary programming problems can be solved exactly, for fairly-sized graphs, using the available optimization soft-wares, and for large size graphs we present an efficient HLSGA. (6) Unlike the before researches, the proposed approach has a clear and realistic structure and its methodology is not complex.

The content of this paper is organized as follows. In the next section some of the relevant terminology and definitions are presented. In Section 3, for the purpose of finding an optimal k-coloring of a fuzzy graph, a binary programming problem is formulated, and using it a general algorithm for coloring a fuzzy graph is designed. Section 4 proposes a HLSGA to solve the proposed binary programming. This section provides some experimental examples to illustrate the performance of the algorithm in comparison with the CPLEX solver; also a subsection for analyzing the sensitivity of the algorithm’s parameters is designed. In Section 5, a cell site assignment problem, as a practical application of the presented approach, is formulated and solved. Some concluding remarks and future lines of research are given in Section 6.

2 Terminologies

In this section, at first some basic definitions of fuzzy graphs is summarized, then the concept of total incompatibility of a coloring and fuzzy chromatic number of a fuzzy graph are introduced. Finally, these definitions and concepts are illustrated with a small example.

Definition 1. (Fuzzy Set) Let X be the universe set, whose generic element be denoted by x, then a fuzzy subset $\tilde{A}$ of X is a set of ordered pairs: $\tilde{A} = {(x, μ_{\tilde{A}} (x)) | x \in X}$ (1)

$μ_{\tilde{A}} : X \to [0, 1]$ is called the membership function of $\tilde{A}$ , and $μ_{\tilde{A}} (x)$ is degree of membership of x in $\tilde{A}$ . For simplicity of notation, instead of $\tilde{A}$ , we use the membership function $μ_{\tilde{A}}$ , as a fuzzy set [20].

Definition 2. (Fuzzy Sub-Graph) Let G = (V, E) be a graph with vertex set V and edge set E ⊆ V × V. If μ and ρ be fuzzy subsets of V and E, respectively, then $\tilde{G} = (μ, ρ)$ is called a fuzzy sub-graph of G if ρ (u, v) ≤ min {μ (u) , μ (v)}, for all u, v ∈ V [17]. We call μ, the fuzzy vertex set and ρ the fuzzy edge set of $\tilde{G}$ , respectively.

From the fuzzy relation point of view, defined by Zadeh [21], ρ is a reflexive and symmetric fuzzy relation on μ, so it can be frequently expressed as a fuzzy matrix [13]. The underlying (crisp) graph of $\tilde{G} = (μ, ρ)$ is denoted by G^* = (μ^*, ρ^*), where μ^* = {u ∈ V|μ (u) >0} and ρ^* = {(u, v) ∈ E|ρ (u, v) >0}.

In the most general case, both vertex and edge sets are fuzzy. However, in this paper we deal with a special case which edge set is fuzzy and vertex set is crisp, i.e. μ (u) =1, for all u ∈ V. We use the abbreviated notation $\tilde{G} = (V, ρ)$ for such fuzzy graphs.

If u, v ∈ V, then the membership degree ρ (u, v) can be interpreted as a degree that shows the level of a special relation between u and v. For example degree of similarity (dissimilarity), degree of compatibility (incompatibility), degree of consistency (inconsistency) and so on. Many real-world situations can be described by means of a fuzzy graph that some elements, exhibited by vertices, are incompatible and levels of incompatibility between different pairs of vertices are not equal. These levels of incompatibility can be shown by the membership degrees of associated fuzzy edges. For example, in a social network grouping problem the vertices can represent people, and edges joining pairs of persons with incompatible opinions or counterviews.

Following definitions describe the coloring problem of a fuzzy graph, based on the concept of incompatibility degree.

Definition 3. (k-coloring of a fuzzy graph) A k-coloring of the fuzzy graph $\tilde{G} = (V, ρ)$ , with (crisp) vertex set V and fuzzy edge set ρ, is a map C^k : V → {1, 2, …, k}, giving to each vertex a color among a set of cardinal k, so that for each color, there exists at least one vertex of V assigned that color. A color class of a k-coloring contains all vertices of the same color.

Unlike the classical graph coloring problems, here adjacent vertices can receive same colors, if two adjacent vertices u and v have same colors, i.e. C^k (u) = C^k (v), we say that u and v are incompatible under C^k, with the degree of incompatibility ρ (u, v), equivalently (u, v) named an incompatible edge.

Definition 4. (Degree of Total Incompatibility) Let C^k : V → {1, 2, …, k} be a k-coloring of a fuzzy graph $\tilde{G} = (V, ρ)$ , if IE (C^k) = {(i, j) ∈ ρ^*|C^k (i) = C^k (j)} is the set of all incompatible edges associated with C^k, then total incompatibility and Degree of Total Incompatibility of C^k are defined as follows: $TI (C^{k}) = \sum_{(u, v) \in IE (C^{k})} ρ (u, v)$ (2) $DTI (C^{k}) = \frac{\sum_{(u, v) \in IE (C^{k})} ρ (u, v)}{\sum_{(u, v) \in ρ^{*}} ρ (u, v)}$ (3)

It is easy to verify the following properties of the above definition.

Proposition 1. Let $\tilde{G} = (V, ρ)$ be a fuzzy graph and |V| = n, the following properties hold.

DTI (C^k) ∈ [0, 1] , for all 1 ≤ k ≤ n .

DTI (C¹) =1 and DTI (Cⁿ) =0 .

In the general case, the number of colors can changes from 1 to n, and it may exist various ways in which we can color a graph using k colors, 1 ≤ k ≤ n. But we should find optimal k-colorings with the minimum degree of total incompatibility.

Let $A^{k}, 1 \leq k \leq n,$ be the set of all possible k-colorings of the fuzzy graph $\tilde{G} = (V, ρ)$ and $A = ⋃_{k = 1}^{n} A^{k}$ be the set of all possible colorings of $\tilde{G}$ , using at most n colors. Following definition helps us to introduce the concept of fuzzy chromatic number of a fuzzy graph.

Definition 5. (Fuzzy Chromatic Number) Let $C_{\min}^{k} \in A^{k}$ , 1 ≤ k ≤ n, be a k-coloring of $\tilde{G}$ with minimum degree of total incompatibility ( $C_{\min}^{k}$ is named a minimal k-coloring), then the fuzzy chromatic number of $\tilde{G}$ is defined as the following fuzzy set. ${\tilde{χ}}_{\tilde{G}} = {(k, 1 - DTI (C_{\min}^{k})) | k = 1, 2, \dots, n}$ (4)

In this case the set $Γ_{\tilde{G}} = {C_{\min}^{1}, C_{\min}^{2}, \dots, C_{\min}^{n}} \subseteq A$ is named an optimal coloring set.

In order to illustrate our proposed definitions, consider the following example.

Example 1. Consider the fuzzy graph $\tilde{G} = (V, ρ)$ defined by Fig. 1. Incompatibility degree of two distinct vertices has been shown as membership degree of their associated edge in ρ. It is intuitively clear that if all vertices are assigned the same color (we have only one C¹ coloring), all of the edges in $\tilde{G}$ are incompatible and so $DTI (C^{1}) = \frac{0.7 + 0.8 + 0.5 + 0.3 + 0.4 + 1.0}{0.7 + 0.8 + 0.5 + 0.3 + 0.4 + 1.0} = \frac{3.7}{3.7} = 1$ . However, there are several ways to color V by two, three and four colors. It is easy to verify that: $\begin{matrix} C_{\min}^{2} = {(a, 1), (b, 2), (c, 2), (d, 1)} \Rightarrow \\ IE (C_{2}^{2}) = {(a, d), (b, c)} \Rightarrow DTI (C_{\min}^{2}) = \frac{0.8}{3.7} = 0.21621 \\ C_{\min}^{3} = {(a, 1), (b, 2), (c, 2), (d, 3)} \Rightarrow \\ IE (C_{3}^{2}) = {(b, c)} \Rightarrow DTI (C_{\min}^{3}) = \frac{0.3}{3.7} = 0.08108, \\ C_{\min}^{4} = {(a, 1), (b, 2), (c, 3), (d, 4)} \Rightarrow \\ IE (C_{4}^{2}) = φ \Rightarrow DTI (C_{\min}^{4}) = \frac{0}{3.7} = 0 . \end{matrix}$

Therefore, the fuzzy chromatic number and optimal coloring set of $\tilde{G}$ are as follows: $\begin{matrix} {\tilde{χ}}_{\tilde{G}} = {(1, 0), (2, 0.78379), (3, 0.91892), (4, 1)}, \\ Γ_{\tilde{G}} = {C_{\min}^{1}, C_{\min}^{2}, C_{\min}^{3}, C_{\min}^{4}} . \end{matrix}$

The main difficulty of the coloring problem of a fuzzy graph is finding a sequence of k-colorings with minimum degrees of total incompatibility. In the next section we formulate a binary programming problem which can find these type of colorings.

3 Finding the optimal k-coloring: A binary programming

Let $\tilde{G} = (V, ρ)$ be a fuzzy graph, and ρ = [ρ_ij] denotes the matrix of incompatibility degrees of vertices. The purpose is finding a k-coloring (k ∈ {1, …, n}) of $\tilde{G}$ with minimum degree of total incompatibility. To do so, we introduce the binary variables x_ir and y_ij as follows. $x_{ir} = {\begin{matrix} 1 & if color r assigned to the vertex i \\ 0 & other wise \end{matrix}$ $y_{ij} = {\begin{matrix} 1 & if vertices i and j assigned the same color \\ 0 & other wise \end{matrix}$

Then formulate the following binary programming problem: $\begin{matrix} \min & {TI}_{k} = \sum_{(i, j) \in ρ^{*}} ρ_{ij} y_{ij} & (a) \\ s . t . & \sum_{r = 1}^{k} x_{ir} = 1 & i \in V & (b) \\ \sum_{i \in V} x_{ir} \geq 1 & r = 1, \dots, k & (c) \\ x_{ir} + x_{jr} - y_{ij} \leq 1 & (i, j) \in ρ^{*} & (d) \\ x_{ir} \in {0, 1} & \forall i, \forall r & (e) \\ y_{ij} \in {0, 1} & (i, j) \in ρ^{*} & (f) \end{matrix}$ (5)where, the objective function (5.a) shows the total incompatibility, it must be minimized. Constraint (5.b) guarantees that every vertex is assigned exactly one color. Constraint (5.c) guarantees that for each color r there exists at least one vertex of V assigned to r. In constraint (5.d), x_ir = x_jr = 1 forces y_ij = 1, whereas x_ir + x_jr ≤ 1 allows either value of y_ij, but minimizing the objective function ensures that y_ij = 0.

Regarding the proposition 1, for finding the optimal colorings, it is not necessary to solve the problem (5) for k = 1 and k = n. Hence in the worst case we should solve the problem (5) for k = 2, …, n - 1, and find a sequence of optimal colorings to obtain the fuzzy chromatic number of a fuzzy graph. Algorithm 1, presents a pseudo-code to find a sequence of optimal colorings and the fuzzy chromatic number of a fuzzy graph.

The main challenge in the presented algorithm is solving the problem (5). In fact, this problem is a combinatorial optimization problem, and traditional solving methods have only limited success in solving small to midsize problems. In the next section we combine the Genetic Algorithm (GA) with a Local Search (LS) methodology to design an efficient meta-heuristic algorithm, for solving the model (5).

Algorithm 1 (Fuzzy Graph Coloring)

Input: Set of vertices V = {1, …, n} and matrix of

incompatibility degrees ρ = [ρ_ij].

begin

TI← ∑_(i,j)∈ρ^*ρ_ij ;

k← 1 ;

whilek ≤ ndo

solve the problem (5), find the optimal

solution

(x^{*}, y^{*}), and {TI}_{k}^{*}

;

fori from 1 to n and r from 1 to kdo

x_{ir}^{*} = 1

then

C_{\min}^{k} (i) = r;

end if;

end do;

DTI (C_{\min}^{k}) \leftarrow \frac{{TI}_{k}^{*}}{TI}

, and k ← k + 1;

end do;

end;

Output: The Optimal Coloring Set

Γ_{\tilde{G}} = {C_{\min}^{1}, C_{\min}^{2}, \dots, C_{\min}^{n}}

and the fuzzy chromatic number

{\tilde{χ}}_{\tilde{G}} = {(k, 1 - DTI (C_{\min}^{k})) | k = 1, \dots, n}

4 Solving the presented binary programming: A Hybrid Local Search Genetic Algorithm (HLSGA)

Genetic algorithm (GA), originally developed by Holland [7], is a stochastic search algorithm based on the mechanism of natural selection and natural genetics. This algorithm is a powerful tool for solving several complicated optimization problems [5].

In order to use the GA, feasible solutions of the problem need to be coded into symbol strings, named chromosomes, which have fixed structures. Each bit of the chromosome represents a gene. A set of chromosomes in each generation is called a population. During each generation, the chromosomes are evaluated using some measures of fitness. The fitness value is used to measure the environmental adaptability of a chromosome. In optimization problems, objective function usually plays the role of fitness function.

To create the next generation, new chromosomes which called offspring, are formed by either merging two chromosomes from current generation using a crossover operator or modifying a chromosome using a mutation operator. Selection operators, according to the fitness values, help us to select some parents to perform the crossover and mutation operations, and finally, rejecting surplus chromosomes so as to keep the population size constant. Fitter chromosomes have higher probabilities of being selected. After several generations, the algorithms converge to the best chromosome which hopefully represents the optimum or suboptimal solution to the problem [5].

Here, besides the basic GA operators we use a local search approach to improve the efficiency of the GA and design a hybrid local search GA.

In the following, details of the basic components of the presented algorithm are explained.

4.1 Basic components of the presented HLSGA

Encoding Method: An integer permutation encoding is used to encode a feasible solution as a chromosome. Toward this end, a k-coloring C^k : V → {1, …, k} (k ∈ {1, …, n}) is encoded as a chromosome U (C^k) = (u₁, u₂, …, u_n) ∈ {1, …, k} ⁿ that u_i = C^k (i) , i = 1, … n . It’s clear that, this encoding is the mapping from any chromosome to solution (decoding) belongs to 1-to-1 mapping.

Generation the Initial Population: The initial population is constructed by choosing the integer numbers randomly from the set {1, …, k} .

Fitness Function: Sum of all incompatibilities, as computed in the objective function in the model (5), is used for the fitness value.

Selection Operator: Parents are selected using the classic tournament method. In this method, a small group of individuals are randomly drawn from the population and the individual with best fitness is chosen for reproduction. This procedure is performed twice, once for the selection of each parent.

Crossover Operator: The crossover used here is Incompatibility Elimination Crossover (IEX). This operator is a revised version of the Conflict Elimination Crossover (CEX), designed by Kokosinski et al. [11], to solve a classic vertex graph coloring problem. As mentioned earlier, two adjacent vertices are incompatible under a coloring if they have same colors; we say their color is an incompatible color. In the IEX crossover, offspring tries to copy compatible colors from the parents, without violating feasibility. Feasibility of a k-coloring can be retained when for each color of {1, 2, …, k} there exists at least one vertex of the graph assigned that color.

Genes in a parental chromosome is partitioned into two groups. The first group consists of compatible colors (genes) while the second one is built of the remaining genes that are incompatible. In IEX, compatible genes of each parent are passed to its offspring, and all incompatible genes except one, in both parents, are replaced by corresponding genes taken from the other parent. In order to preserve the feasibility, one of the repetitive incompatible genes which is selected randomly, is not replaced.

An application of the operator IEX is shown inExample 2.

Example 2. Consider the fuzzy graph $\tilde{G} = (V, ρ)$ with 8 vertices, depicted in Fig. 2. Two parents represent different 4-colorings of graph as: U₁ = (1, 2, 1, 3, 4, 3, 2, 1) and U₂ = (4, 3, 1, 4, 2, 3, 1, 3). Incompatible colors are marked by bold fonts. U₁ has two repetitive incompatible colors, 1 and 3, but U₂ has one repetitive incompatible color i.e. 4. Replacing the incompatible genes by genes taken from the other parent and retaining one of the repetitive incompatible genes we obtain the following two chromosomes: S₁ = (4, 2, 1, 4, 4, 3, 2, 1) and S₂ = (1, 3, 1, 4, 2, 3, 1, 3). It is observed that the total incompatibilities of U₁, U₂, S₁ and S₂ are 1.7, 0.8, 1.1 and 0.7 respectively.

Mutation Operator: Here we use a Color Transposition Mutation (CTM), in which two colors are randomly selected then colors of all vertices assigned these two colors are transposed.

As an example, in Fig. 2, consider a 5-coloring of graph as: U = (3, 2, 5, 4, 2, 5, 3, 1). If 3 and 5 are the randomly selected colors, then S = (5, 2, 3, 4, 2, 3, 5, 1) is the new 5-coloring, obtained by CTM.

Local Search Operator: The idea of combining GA and local search heuristics for solving optimization problems is one of extensively investigated methods to modify the performance of GA. Our presented search approach is a local search, implemented on the colors space, and is successively performed on a randomly selected set of chromosomes, after the crossover and mutation operators. Figure 3 shows details of the presented local search procedure. As a simple example, consider U = (1, 2, 2, 3, 2, 3, 1, 2) as a 3-coloring of the graph shown in Fig. 2, its total incompatibility is TI (U) =1.9. By performing the presented local search, we obtain a new 3-coloring with smaller value of total incompatibility as: U′ = (1, 1, 2, 3, 2, 3, 1, 3), TI (U′) =0.9.

Based on the above operators, general structure of our presented hybrid local search GA is described as follows:

Algorithm 2 (HLSGA)

Input: Fuzzy graph data: n, ρ = [ρ_ij], number of

colors and GA parameters

begin

t ← 0; // t is a counter for the number of generations.

Initialize a randomly generated population

P (t) = {U₁, U₂, …, U_ps} ⊂ {1, …, k} ⁿ of chromosomes;

// ps is the population size.

Evaluate P (t) using the fitness function;

while (not termination condition) do

Select the parental population T1 (t) from P (t);

Create the offspring populations OX (t) and

OM (t) from T1 (t) by IEX (crossover) and CTM (mutation);

P (t) ← P (t) ∪ OX (t) ∪ OM (t);

Evaluate P (t) using the fitness function;

Select the parental population T2 (t) from P (t);

Create the offspring populations OLS (t) from

T2 (t) by Local Search Procedure;

P (t) ← P (t) ∪ OLS (t);

Evaluate and sort P (t) members using the

fitness function;

Select the new population P (t + 1) from P (t),

by eliminating extra members;

t ← t + 1;

end do;

end;

Output: The best solution (k-coloring)

4.2 Numerical experiments

We implement the proposed Hybrid Local Search GA using five graphs, randomly generated based on a MATLAB code. Computational experiments on the10-vertex/31-edge, 20-vertex/124-edge, 30-vertex/222-edge, 50-vertex/569-edge and 100-vertex/2501-edge test-problems have been done under the same GA parameter settings: population size (popsize = 20), crossover probability (cp = 0.80), mutation probability (mp = 0.50), mutation rate (mr = 0.05), local search probability (lsp = 0.5), stopping condition (evaluation of 50 generations). In order to evaluate the results of each test, we consider the mean value of the optimal obtained results between all iterations. Tables 1 to 5 show the computational results (in CPU time) of solving generated instances with our proposed approach and compare them with the solutions obtained utilizing the Mixed-Integer Programming (MIP) solver of CPLEX12. All computer experiments were performed on a Pentium IV personal computer with a 2.8 GHz CPU and a 2 GB RAM.

As can be seen, when the number of colors is not very large the performance of the HLSGA is extremely efficient, and considering the elapsed times for large number of colors it has acceptable performance.

4.3 Analyzing the parameters of HLSGA

For the sake of evaluating the performance of the presented HLSGA, we conduct a sensitivity analysis on the main parameters of the algorithm. Population size, number of generations, crossover probability (cp), mutation probability (mp) and local search probability (lsp) are the main parameters of HLSGA. In the following discussion, we describe the effect of these parameters on the fitness values and elapsed times of algorithm, from a computational point of view. In order to provide truer results, all of our analyses are performed on a graph with 50 vertices and 569 edges, its associated coloring problem was solved in the previous sub-section, and we call it the test problem.

Population size: Generally, increasing the population size can have positive effect on the performance of algorithm. But if the number of generations is constant, it may extremely affect the algorithm’s elapsed time. We have examined the effect of changing population size on fitness values and elapsed times for the test problem, other parameters are: cp = 0.8, mp = 0.3, mr = 0.05, lsp = 0.8, number of generations = 15. The results are shown in Figs. 4 and 5, these results are based on the mean values obtained from 10 runs of the algorithm.

In Figs. 4 and 5, it can be seen that large sizes of population have small effect on the fitness value, but extremely increase the elapsed time. For this problem a good compromise between good fitness value and reasonable speed can be a population size between 50 and 200. Experimental tests showed that increasing the number of runs of algorithm, by a fixed population size, produces better results than increasing the population size.

Number of generations: We ran the before test problem by a number 100 of generations, once with and once without the local search procedure. This process repeated many times. Obtained results showed that in most cases, fitness value does not change from the fifteenth generation to the next, in the presence of the local search procedure, and it does not change in the absence of the local search procedure after the fifty-fifth generation. Figure 6 shows the number of generations’ effect on the fitness values for an example case.

As can be verified from the results of Fig. 6, the local search procedure has an essential role for improving the fitness values.

Crossover: In order to identify the effect of presented IEX crossover on the fitness value and elapsed time we ran the algorithm with different values of crossover probability, with and without the presence of the local search procedure. Obtained results, which have been listed in Table 6, show that the effect of the crossover probability on the fitness value, in the absence of the local search is stronger than its effect in the presence of the local search, but do not forget that with the local search, although more time will be spent, much better fitness values are achieved.

Mutation: Table 7 shows the effect of presented CTM mutation on the fitness value and elapsed time, with and without the presence of the local search procedure. As can be seen in Table 7, increasing the pm, greater than 0.4, is not useful. It seems 0.3 ≤ mp ≤ 0.4 is an adequate probability for experimental purposes.

Local search: As mentioned earlier, the local search procedure has a key role in the presented algorithm. In order to verify this claim, we run the algorithm by different levels of pls, with and without the presence of crossover and mutation. Figure 7 shows details of the results. This figure also confirms that this procedure cannot alone has a good performance, and its combination with crossover and mutation produces acceptable results.

As a final point, it should be noted that in addition the previous parameters, size of graph, i.e. number of vertices and edges, and the number of colors can affect the performance of the presented algorithm and its elapsed time.

5 An application of the presented approach to cell site assignment problem

In this section, we use the presented approach to model and solve a cell site assignment problem, as a fuzzy graph coloring problem. In this problem that arises in mobile telecommunications [10], there are a number n of cell sites and at most a number of k Multi-service Nodes (MSN) within a geographic area. MSNs send/receive packets of mobile telecommunications traffic to/from the cell sites, and connect to the global telecommunications network and to the internet. It is supposed that, in a common network architecture, each cell site is assigned to exactly one MSN and communicates with its assigned MSN using a direct connection. This architecture would be used with cell sites in locations where Metro Ethernet is not available [10].

Each cell site is able to serve mobile telecommunication customers within a particular geographic service area around the cell site. If two cell sites are close to each other, their geographic service areas could overlap. The main problem is assigning MSNs to cell sites in such a way that the total overlap of the paired cell sites, which are assigned to the same MSN, is minimized. Our proposed fuzzy graph coloring approach can be used to model this cell site assignment problem.

In order to model the cell site assignment problem, the cell sites correspond to the vertices of graph, active MSNs correspond to colors; and each edge connects two distinct cell sites (vertices) whose geographic service areas do overlap. For an edge (u, v) the membership degree of this edge, i.e. ρ (u, v) ∈ [0, 1], is defined by the degree of overlap of two vertices u and v. So in this case the concept of incompatibility is equivalent to the overlap concept. If two cell sites (vertices) have a large degree of overlap, then it is important to assign them to different MSNs (colors). Thus, if one of the MSNs should fail (and, therefore, one of the cell sites be unable to communicate with the internet, etc.), the other cell site would be able to serve at least part of the geographic service area associated with the disabled site. As before, if two adjacent cell sites (vertices) u and v assigned to the same MSNs (colors), we say that u and v are incompatible, with the degree ρ (u, v) of incompatibility.

To achieve the desired goal, it can be a total attitude to the problem, in which the objective is to minimize the sum total of the overlaps (incompatibilities) that are associated with cell site pairs that are assigned to the same MSN. If there exists at most k MSNs, then finding the fuzzy chromatic number of the cell site graph can solve the explained problem, and suggest best assignments of MSNs to cell sites, for different number of active MSNs.

In order to implement the presented approach and hybrid local search genetic algorithm for cell site assignment problem, let us consider a real data set with 74 cell sites and 6 MSNs for an Iranian geographic region. There are 310 edges in associated graph, i.e. 310 pairs of the cell sites have positive degrees of overlap. We use the following formula to determine the degree of overlap of two distinct cell sites u and v. $ρ (u, v) = {\begin{matrix} 1 - \frac{dist (u, v)}{R_{u} + R_{v}} & dist (u, v) < R_{u} + R_{v} \\ 0 & otherwise \end{matrix}$ (6)where dist (u, v) is the distance from u and v, and R_u is the coverage radius of u. Table 6, shows the results of solving the problem, using the presented HLSGA.

Using the results of Table 8, fuzzy chromatic number of the cell site assignment’s graph is:

$\begin{matrix} {\tilde{χ}}_{\tilde{G}} = {(1, 0), (2, 0.6559), (3, 0.8718), (4, 0.9477) \\ (5, 0.9823), (6, 0.9933)} \end{matrix}$ (7)

It’s obvious that the above fuzzy chromatic number has been written for 6 colors, because at most 6 MSNs are available.

6 Conclusion and further researches

In this paper we have introduced, formulated and solved a coloring problem on fuzzy graphs, with crisp vertices and fuzzy edges. In order to interpret the fuzzy edges, the concept of incompatibility of vertices has been used. We have applied this concept to define the total incompatibility degree of a vertex-coloring, and then introduced the fuzzy chromatic number of a fuzzy graph. For the purpose of finding the optimal k-colorings of a fuzzy graph, with minimum degree of total incompatibility, we formulated a binary programming problem and designed a hybrid local search genetic algorithm to solve the presented binary programming. In the experimentations that have been conducted on various instances, we showed that the proposed algorithm has acceptable speed and accuracy for solving the large-sized problems. Finally, we used the presented approach to model and solve a cell site assignment problem as a fuzzy graph coloring problem.

Future researches may include some improvement of the presented concepts and models on the fuzzy graphs with fuzzy vertices and edges, or defining the fuzzy chromatic number for a crisp graph. Also, modifying the proposed hybrid algorithm, or designing new meta-heuristic algorithms for solving the presented model can be another possible researches.

Footnotes

Acknowledgments

The author thanks the Associate Editor, Dr. Sergejs Solovjovs, and three anonymous reviewers whoseconstructive comments improve the quality of this article. This research is financially supported by the Office of Vice Chancellor for Research of Islamic Azad University, Sirjan Branch.

References

Anjali

and Mathew

, On blocks and stars in fuzzy graphs, J Intell Fuzzy Syst 28 (2015), 1659–1665.

Bershtein

L.S.

and Bozhenuk

A.V.

, Fuzzy coloring for fuzzy graphs, 10th IEEE Int Conf Fuzzy Syst (Cat. No.01CH7) 3 (2001), 1101–1103.

Eslahchi

and Onagh

B.N.

, Vertex-strength of fuzzy graphs, Int J Math Math Sci 01 (2006), 1–9.

Gary

and Ping

, Chromatic Graph Theory, CRC Press, Boca Raton, 2009.

Gen

, Cheng

and Lin

, Network Models and Optimization: Multi-objective Genetic Algorithm Approach, Springer, London, 2008.

Gomez

, Montero

and Yanez

, A coloring fuzzy graph approach for image classification, Inf Sci 176 (2006), 3645–3657.

Holland

J.H.

, Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, MI, Internal Report, 1975.

IBM ILOG CPLEX, http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/

Kaufmann

, Introduction a la Theorie des Sous-Ensembles Flous, Masson, Paris, 1973.

10.

Klincewicz

J.G.

, Using GRASP to solve the generalized graph colouring problem with application to cell site assignment, Int. J Mobile Network Des Innov 4 (2012), 148–156.

11.

Kokosiski

, Kwarciany

and Krzysztof

, Efficient graph coloring with parallel genetic algorithms, Comp Inform 24 (2005), 123–147.

12.

Mathew

and Sunitha

M.S.

, Fuzzy graphs: Basics, Concepts and Applications, Lap Lambert Academic Publishing, 2012.

13.

Mordeson

J.N.

and Nair

P.S.

, Fuzzy graph and fuzzy hypergraphs, Physica-Verlag Heidelberg, 2000.

14.

Muñoz

, Ortuño

M.T.

, Ramírez

and Yáñez

, Coloring fuzzy graphs, Omega 33 (2005), 211–221.

15.

Poornima

and Ramaswamy

, Total coloring of a fuzzy graph, Int J Comp Appl Math 5 (2010), 11–22.

16.

Ramaswamy

and Poornima

, Edge coloring of a fuzzy graph, Advances in Fuzzy Mathematics 4(1) (2009), 49–58.

17.

Rosenfeld

, Fuzzy graphs, in: Zadeh

L.A.

, Fu

K.S.

and Shimura

(Eds.), Fuzzy Sets Their Appl to Cogn Decis Process, Academic Press, New York, 1975, pp. 77–95.

18.

Rosyida

, Indrati

, Rini Widodo

and Sugeng

K.A.

, A new approach for determining fuzzy chromatic number of fuzzy graph, J Intell Fuzzy Syst 28 (2015), 2331–2341.

19.

Sunitha

M.S.

and Mathew

, Fuzzy graph theory: A survey, Ann Pure Appl Math 4 (2013), 92–110.

20.

Zadeh

L.A.

, Fuzzy sets, Inf Control 8 (1965), 338–353.

21.

Zadeh

L.A.

, Similarity relations and fuzzy ordering, Inf Sci 3 (1971), 177–200.