A Genetic Algorithm For Graph Vertex Coloring Problem

Graph Vertex Coloring Problem, which is NP Hard and belongs to the classicalcombinatorial optimization problems, is generated from the famous Four ColorTheorem, while playing a vital role both in theoretical and practical. As a decisive branchof Graph Theory, Graph Vertex Coloring Problem lies in special important position. Withthe persistent efforts of lots of scholars, Graph Vertex Coloring Problem makes atremendous contribution for the prosperous situation of Graph Theory. In our practical life,Graph Vertex Coloring Problem can be used to solve a mass of problems, such as theresource allocation problem, VLSI wiring and frequency assignment etc. In addition,many other issues can be boiled down to the Graph Vertex Coloring Problem.Researchers who are engaged in Graph Theory or engineering, all face an arduousconundrum that is finding an efficient algorithm to solve the Graph Vertex ColoringProblem. As we know, it’s hard, or in another word, impossible to found the optimalsolution by an exact algorithm when scale of problem is huge. As a result, it’s an informeddecision to divert our focus to the research of heuristic algorithms.Genetic Algorithm, which is based on Darwin’s The Origin of Species and Mendel’slaws of The Theory of inheritance, is an heuristic algorithm. The algorithm which can’tguarantee the optimal solution, is sure to found suboptimal solution in acceptable timewhile the acquired result could meet the demands in practical application most of the time.The adoption of Greedy Algorithm, a stradegy to choose the local optimum each step,aids greatly to the defect of poor ability in local search of the Genetic Algorithm.Experiments on a good deal of graphs, both structure and random graph, confirm theeffectiveness of our algorithm, proposed in this thesis, in finding suboptimal solutions ofGraph Vertex Coloring Problem.