一种基于改进遗传算法的图着色算法

• 作者: 李凯
• 来源期刊: 计算机与现代化
• 学科: 工学
• 关键词: 图着色 遗传算法 整数编码 启发式算子
• 年，卷（期）: 2017,（2）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 6-11
• 页数: 6页
• 分类号: TP393
• 字数: 5620字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-2475.2017.02.002

摘要

针对基于行结构的整数编码遗传算法在求解图着色问题时存在的2个主要问题:编码冗余引起的性能下降和遗传算法易"早熟"陷入局部最优,本文给出一种新的适应度值计算函数,能够使遗传算法对冗余编码获得相同的适应度值,从而将冗余编码作为同一编码处理,减少对冗余编码的无效操作,并且在此基础上,设计与适应度函数相适应的遗传算子,这些算子一方面能使遗传算法在前期产生优秀个体并且维护优秀个体对种群进化的引导作用,加速遗传算法的收敛;另一方面能在遗传算法后期对优秀个体进行爬山优化,弱化优秀个体对种群进化的控制作用,使遗传算法能够收敛到全局最优解.实验结果表明,本文的算法能够准确解决图的点着色问题,并且在时间性能上要优于穷举法和基本遗传算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李凯	广州大学教务处	5	2	1.0	1.0