计算机与现代化Issue(2)：6-11,6.DOI:10.3969/j.issn.1006-2475.2017.02.002
一种基于改进遗传算法的图着色算法
An Improved Genetic Algorithm for Solving Graph Coloring Problem
摘要
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 simi-lar 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 prelimina-ry, at the same time, they also can optimize the better individuals and make them evolve to the best which is useful for the con-vergence of genetic algorithm. The experiment results show that:the method proposed in the paper not only can converge the glob-al optimal solution but also can improve the genetic algorithm performance.关键词
图着色/遗传算法/整数编码/启发式算子Key words
graph coloring/genetic algorithm/integer coding/heuristic operator分类
信息技术与安全科学引用本文复制引用
李凯..一种基于改进遗传算法的图着色算法[J].计算机与现代化,2017,(2):6-11,6.基金项目
国家自然科学基金资助项目(71402036) （71402036）
广州大学教育教学研究项目(JY201545) （JY201545）
