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

Cao, Li; Cheng, Hao; Xu, Zhong

J. Shaanxi Norm. Univ., Nat. Sci. Ed. 35, No. 3, 24-27 (2007).

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

Keywords:

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

Software:

DSATUR