A Novel Bi-objective Genetic Algorithm for the Graph Coloring Problem

Author

Han, Lixia ; Han, Zhanli

Author_Institution

Sch. of Comput. Sci. & Technol., China Univ. of Min. & Technol., Xuzhou, China

Volume

4

fYear

2010

Firstpage

3

Lastpage

6

Abstract

Graph coloring problem is a classical NP-hard combinatorial optimization problem. In this paper, a new bi-objective model for the coloring problem is presented. Based on this new model, a bi-objective genetic algorithm is proposed which employs effective crossover and simple mutation operator as the genetic operators. The global convergence of the proposed algorithm to globally optimal set with probability one is proved. Experimental results demonstrate that the proposed algorithm is expected.

Keywords

computational complexity; convergence; genetic algorithms; graph colouring; probability; biobjective genetic algorithm; classical NP-hard combinatorial optimization problem; crossover operator; global convergence; graph coloring problem; mutation operator; probability; Computational modeling; Computer science; Computer simulation; Convergence; Electronic mail; Genetic algorithms; Genetic mutations; Joining processes; Robustness; NP-hard; genetic algorithm; graph coloringproblem;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Modeling and Simulation, 2010. ICCMS '10. Second International Conference on

Conference_Location

Sanya, Hainan

Print_ISBN

978-1-4244-5642-0

Electronic_ISBN

978-1-4244-5643-7

Type

conf

DOI

10.1109/ICCMS.2010.157

Filename

5421531