##
**An application of a new hybrid genetic algorithm to graph coloring.**
*(Chinese.
English summary)*
Zbl 1150.68548

Summary: Combined with SA and TS, a hybrid genetic algorithm for the graph coloring problem 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 optimization, which prevents the repeat between the new and the old individual through its memory function; and GA is used to global-search. The comparison is carried on with the Greedy GA and the Dsatur, the result indicates that the computing precision of hybrid algorithm is better than the other algorithms. Experiments show that the improved hybrid algorithm can get better computing speed on density graph, but it is not good on sparse graph. This makes it clear that the improved hybrid genetic algorithm is rational and effective.

### MSC:

68W99 | Algorithms in computer science |

05C15 | Coloring of graphs and hypergraphs |

68R10 | Graph theory (including graph drawing) in computer science |