A genetic algorithm for graph coloring using single parent conflict gene crossover and mutation with conflict gene removal procedure

摘要

Graph Coloring Problem, an NP-hard combinatorial optimization problem is widely applied in various engineering fields. This paper exhibits an improved genetic method which uses the single parent conflict-gene crossover and conflict-gene mutation operators along with the conflict-gene removal procedure to solve the graph coloring problem. These operators reduce the search space by minimizing the number of genetic generations to obtain the optimal solution. A fitness function based on number of conflicting edges, whose vertices assigned with same color has been defined for the initial and subsequent generations of gene sequences. This proposed genetic method is compared on some of the benchmark graphs and the results are found to be promising. The approximation methods that minimize the search space and also increase the percentage of successful runs are exhibited.