Combined with SA and TS, a hybrid genetic algorithm for the graph coloring problem (GCP) is proposed. In a hybrid algorithm, SA is used to local-optimize, which can accelerate the optimization process and avoid the premature convergence; TS is used to improve the global-optimize, which prevent the repeat between the new individual and the old individual through its memory function; GA is used to global search. The comparison is carried on with the Greedy GA and the Dsatur, the result indicate that the computing precision of hybrid algorithm is better than the antitheses. Experiments show that the improved hybrid algorithm can get better computing speed on density graph, but slow down on sparse graph. These make it clear that the improved hybrid genetic algorithm is rational and effective.

genetic algorithm; GA-ASATS; adaptive SA operator; tabu operator