Genetic Algorithm Applied to the Graph Coloring Problem

23rd Midwest Artificial Intelligence and Cognitive Science Conference 2012

Musa M. Hindi ; Roman V. Yampolskiy

Others  :  http://ceur-ws.org/Vol-841/submission_10.pdf
PID  :  42147

来源: CEUR

【 摘 要 】

In this paper we present a hybrid technique that applies a genetic algorithm followed by wisdom of artificial crowds approach to solving the graph-coloring problem. The genetic algorithm described here utilizes more than one parent selection and mutation methods depending on the state of fitness of its best solution. This results in shifting the solution to the global optimum more quickly than using a single parent selection or mutation method. The algorithm is tested against the standard DIMACS benchmark tests while limiting the number of usable colors to the known chromatic numbers. The proposed algorithm succeeded at solving the sample data set and even outperformed a recent approach in terms of the minimum number of colors needed to color some of the graphs.The Graph Coloring Problem (GCP) is a well-known NP-complete 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: • Map coloring (B. H. Gwee, M. H. Lim and J. S. Ho 1993)• Scheduling (Daniel Marx and D Aniel Marx 2004)• Radio Frequency Assignment (W. K. Hale 1980; S. Singha, T. Bhattacharya and S. R. B. Chaudhuri 2008)• Register allocation (Wu Shengning and Li Sikun 2007)• Pattern Matching• SudokuIn this paper we demonstrate the use of genetic algorithmsin 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.