The Graph Coloring Problem (GCP) is a well-known NPcomplete problem. Graph coloring includes both vertex coloring and edge coloring. However, the term graph coloring usually refers to vertex coloring rather than edge coloring.

Given a number of vertices, which form a connected graph, the objective is to color each vertex such that if two vertices are connected in the graph (i.e. adjacent) they will be colored with different colors. Moreover, the number of different colors that can be used to color the vertices is limited and a secondary objective is to find the minimum number of different colors needed to color a certain graph without violating the adjacency constraint. That number for a given graph (G) is known as the Chromatic Number (χ(G)) (Isabel Méndez Díaz and Paula Zabala 1999).

If k = {1, 2, 3... } and P(G, k) is the number of possible solutions for coloring the graph G with k colors, then χ(G) = min(k: P(G, k) > 0)

(1)

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 (CSPs). The practical applications of Graph Coloring Problems include but are not limited to: In this paper we demonstrate the use of genetic algorithms in solving the graph-coloring problem while strictly adhering to the usage of no more than the number of colors equal to the chromatic index to color the various test graphs.

A great deal of research has been done to tackle the theoretical aspects of the Graph Coloring Problem in terms of its generalization as a Constraint Satisfaction Problem (Isabel Méndez Díaz and Paula Zabala 1999). The problem's various applications and solutions have been discussed in detail in Porumbel's paper (Daniel Cosmin Porumbel 2009). Evolutionary computation and parameter control has been detailed in a number of papers including ones by Back, Hammel, and Schwefel (T. Back, U. Hammel and H. P. Schwefel 1997) as well as work by Eiben, Hinterding and Michalewicz (A. E. Eiben, R. Hinterding and Z. Michalewicz 1999). Srinivas and Patnaik examined crossover and mutation probabilities for optimizing genetic algorithm performance (M. Srinivas and L. M. Patnaik 1994). Genetic algorithms and evolutionary approaches have been used extensively in solutions for the Graph Coloring Problem and its applications (F. F. Ali, et al. 1999;K. Tagawa, et al. 1999;Cornelius Croitoru, et al. 2002;C. A. Glass and A. Prugel-Bennett 2003;Justine W. Shen 2003;Greg Durrett, Muriel Médard and Una-May O'Reilly 2010;Lixia Han and Zhanli Han 2010). Most recent work utilized a parallel genetic algorithm on a similar dataset to the one used in this paper (Reza Abbasian and Malek Mouhoub 2011).

The concept of utilizing a crowd of individuals for solving NP complete problems has also been the topic of various papers. Most notably the Wisdom of Crowds concept has been used in solving the Traveling Salesman Problem (Sheng Kung Michael Yi, et al. 2010b) as well as the Minimum Spanning Tree Problem (Sheng Kung Michael Yi, et al. 2010a). In this paper we attempt to supplement the solution produced by the genetic algorithm utilizing an artificial crowd (Leif H. Ashby and Roman V. Yampolskiy 2011; Roman V. Yampolskiy and Ahmed El-Barkouky 2011).

Genetic algorithms share an overall structure and workflow yet they vary in the specific details according to the particular problem. The algorithm consists of a parent selection method, a crossover method and a mutation method.

The general algorithm is: The goal of the previous algorithm is to improve the fitness of the population by mating its fittest individuals to produce superior offspring that offer a better solution to the problem. This process continues until a terminating condition is reached which could be simply that the total number of generations has been run or any other parameter like non-improvement of fitness over a certain number of generations or that a solution for the problem has been found.

The chromosome representation of the GCP is simply an array with the length set to the number of vertices in the graph. Each cell in the array is assigned a value from 0 to the number of colors -1. The adjacencies between the vertices are represented by an adjacency matrix of dimensions n×n where n: the number of vertices.

Figure 1 displays the chromosome representation of a graph of 7 vertices using 4 colors:

The ultimate goal when solving GCPs is to reach a solution where no two adjacent vertices have the same color. Therefore, the GA process continues until it either finds a solution (i.e. 0 conflicts) or the algorithm has been run for the predefined number of generations. In addition to the GA, if a run fails to reach a solution a Wisdom of Crowds approach will be applied to the top performers in an attempt to produce a better solution.

The overall genetic algorithm in this approach is a generational genetic algorithm. The population size is kept constant at all times and with each generation the bottom performing half of the population is removed and new randomly generated chromosomes are added. The population size is set to 50 chromosomes. The value was chosen after testing a number of different population sizes. The value 50 was the least value that produced the desired results.

The GA uses two different parent selection methods, a single crossover method and two different mutation methods. Which of the parent selection and mutation methods ends up selected depends on the state of the population and how close it is to finding a solution. The parent selection, crossover and mutation methods are outlined as follows: A bad edge is defined as an edge connecting two vertices that have the same color. The number of bad edges is the fitness score for any chromosome. As mentioned above, the alteration between the two different parent selection and mutation methods depends on the best fitness. If the best fitness is greater than 4 then parentSelection1 and mutation1 are used. If the best fitness is 4 or less then parentSelection2 and mutation2 are used. This alteration is the result of experimenting with the different data sets. It was observed that when the best fitness score is low (i.e. approaching an optimum) the usage of parent selection 2 (which copies the best chromosome as the new child) along with mutation2 (which randomly selects a color for the violating vertex) results in a solution more often and more quickly than using the other two respective methods.

Finally, the algorithm is run for 20,000 generations or until a solution with 0 bad edges is found. If a solution is not found after 20,000 generations the wisdomOfArtificialCrowds algorithm is run. The algorithm used is a localized wisdom of crowds algorithm that only builds a consensus out of the violating edges in the best solution. Moreover, it uses the best half of the final population to produce an aggregate solution. Only a localized consensus is generated so as not to produce a result that alters the correctly colored vertices. Also, it takes the best half because they share the most similarity and thus will most likely be different at the level of the bad edges rather than the good ones. A number of lines follow the header with each line denoting the connected edges and their vertex indices: e 1 100 16 files were chosen from the DIMACS collection. The graphs the files represent vary in vertex count, edge count and overall complexity. The vertex count ranges between 11 and 561 and the edge count ranges from 20 to 11654. The rationale behind the selection of these graphs other than the wide range of variation is that there is a known chromatic number for each of them, or at least a good approximation.

The following files were used in this approach: (myciel3.col, myciel4.col, myciel5.col, queen5_5.col, queen6_6.col, queen7_ 7.col, queen8_8.col, huck.col, jean.col, david.col. games120.col, miles250.col, miles1000.col, anna.col, fpsol2.i.1.col, homer.col).

Table 1 displays the following statistics for each file: The tests were run on a desktop PC with the following specifications: CPU: Intel Core i7 860 @2.8Ghz RAM: 8 GB DDR3 @1333MHz The following graphs plot the relationship between the fitness and the generation for a sample set of the files used: Figures 2 and 3 are not very interesting since the solutions are found after a few generations. The next plot, however, is of particular interest since it clearly represents the erratic behavior of the fitness score between the initial rapid drop until a solution is ultimately found. In standard genetic algorithms the fitness score continues to increase or decrease (depending of the definition of better fitness) until the end of the run. This is not the case here. This factor plays a huge role in obtaining the global optimum with a higher probability than without it as will be discussed later.

During the design of this approach, the issue of designing good operators was a constant concern. The goal of any good operator is to bring the chromosomes of a population closer to the desired solution. However, during the process, a chromosome's fitness often improves but eventually ends up in a local optimum. The overall design of this approach aimed to improve fitness towards the global optimum while avoiding the pitfalls of local optima.

To achieve that, a number of factors need to be considered. Initially, the crossover function is applied to parents that result from the first parent selection method. This method selects parents by conducting a small tournament between random pairs of chromosomes. Two pairs are chosen randomly and the fitter of each pair becomes a parent. These fit parents are then used as input to this crossover method. The crossover conducts a simple one-point crossover with the cross point being chosen at random. The result of this crossover is then subjected to the first mutation method. The mutation is carried out at a high rate of 0.7. This mutation examines each vertex and if a vertex violates the coloring constraint a valid color is chosen at random.

This process is very effective in reducing the number of conflicts rapidly which can be seen in all the plots through an almost perpendicular drop in fitness. However, in spite of this method's effectiveness at increasing fitness rapidly, it has the side effect of keeping the solution at a local optimum.

To fix that, another parent selection and mutation method is introduced. The two methods are applied when the overall fitness of the best solution drops below 5 conflicts.

After that point crossover is no longer applied. The top performer is selected and is subjected to the second mutation method. This method finds the conflicting vertices and replaces their conflicting colors with random colors; which could be invalid as well. This has the potential to either find a globally optimum solution (i.e. 0 conflicts) or produce a solution that is worse! This can be observed by the erratic pattern in some of the graphs after the sharp descent and before the actual resolution of the problem.

This seemingly worsening fitness is not bad however. In fact, it is partly due to this worsening of the fitness that some solutions are found at all! When the solution becomes worse the fitness score increases. This will force the algorithm back to using the first parent selection and mutation methods. But, the population now contains a solution that hadn't been there before, which increases the possibility of reaching the global optimum. The continuous back and forth between parent selection and mutation methods plays a crucial role in shifting the solution from a local optimum to a global optimum.

Finally, if a solution is not found after 20,000 generations, a Wisdom of Artificial Crowds algorithm is applied to the resultant population to produce a better solution. The genetic algorithm had been producing optimal results and thus, per the algorithmic workflow, the Wisdom of Artificial Crowds postprocessor wouldn't be applied. However, in order to test its effectiveness, a test was conducted by decreasing the generation count to 10,000 to intentionally produce a suboptimal solution. The test was carried out on the miles1000.col file. Before the postprocessor was applied the best solution had 5 conflicting edges. After application of the Wisdom of Artificial Crowds postprocessor the graph was colored slightly differently but still had 5 conflicting edges. It is worth noting that the postprocessor added an average of 250 ms to the overall process.

The test cases used were very useful in both testing and tuning the algorithm. The algorithm was able to scale across the different graphs and produce optimum solutions in each case. A recent 2011 publication presented a parallel genetic algorithm for the GCP (Reza Abbasian and Malek Mouhoub 2011). This paper used most of the same test files that were used in Abbasian's approach. That approach's proposed algorithm failed to solve three of the graphs and only produced solutions when the color count was increased by 1. The files representing these graphs are queen6_6.col, queen7_7.col and queen8_8.col. The algorithm used in our approach successfully solved these three files using the specified known chromatic number as the number of colors used. Our approach is also generally faster at finding a solution. It is faster in all cases except four. Three of those cases are the three aforementioned files, which the comparative method did not succeed at finding a solution using the known chromatic index. The fourth case is miles1000.col.

The overarching algorithm used in this approach is a genetic algorithm with a subsequent Wisdom of Crowds post-processor. Within the genetic algorithm itself is a set of operators that utilize methods from the genetic algorithm domain as well as applying various heuristics in a stochastic manner. The end result is an quick progressive climb to the peak of the globally optimum solution.

The algorithms described here can also be applied to the various subsets of the general GCP. In particular, Sudoku can benefit from these algorithms where it can be represented as a graph with 81 vertices that must be colored using no more than 9 different colors (i.e. different numbers).