Abstract: Generic genetic algorithms need generate initial population iteratively for solving the coloring problem. Based on this problem, an improved algorithm is presented. The novel algorithm adopts a comparative mechanism to eliminate the unfeasible genes, and gives the valid individual a greater probability to survive to the next generation by using the dynamic fitness function. Thus, the proposed algorithm avoids the repetitious production of the initial population. Compared with the algorithms under the traditional architecture, the proposed algorithm can shorten the time of finding the optimal solution at least by up to 51 percent. Moreover, the novel algorithm has the advantages of jumping from a local optimal solution to next one quickly and converging to the global optimal solution in the end.

Key words: graph coloring problem, genetic algorithm, local search, global convergence