关键词: 图着色, 遗传算法, 整数编码, 启发式算子

Abstract:  When the people apply the genetic algorithm which is encapsulated with the structure of line and coded by integer in solving the graph coloring problem, redundancy codes makes the performance of algorithm degrade and easily plunges into local optimum. In order to solve these problems, the paper proposes a new fitness function which can deal with the redundancy or similar codes. Based on the fitness function, the paper also extends the genetic operator, such as selection operator and so on. These operators can make sure that in the preliminary, the genetic algorithm can generate good individuals and enforce their guidance function, while in the later period they can weaken the control function of good individuals which are generated in the preliminary, at the same time, they also can optimize the better individuals and make them evolve to the best which is useful for the convergence of genetic algorithm. The experiment results show that: the method proposed in the paper not only can converge the global optimal solution but also can improve the genetic algorithm performance.


Key words: graph coloring, genetic algorithm, integer coding, heuristic operator