Title :
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
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;
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
DOI :
10.1109/ICCMS.2010.157
