计算机与现代化

• 算法设计与分析 • 上一篇    下一篇

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

  

  1. (广州大学教务处,广东广州510000)
  • 收稿日期:2016-07-26 出版日期:2017-03-09 发布日期:2017-03-20
  • 作者简介:李凯(1987-),男,湖南衡阳人,广州大学教务处助理研究员,硕士,研究方向:数据挖掘,智能算法。
  • 基金资助:
    国家自然科学基金资助项目(71402036); 广州大学教育教学研究项目(JY201545)

An Improved Genetic Algorithm for Solving Graph Coloring Problem

  1. (Office of Academic Affairs, Guangzhou University, Guangzhou 510000, China)
  • Received:2016-07-26 Online:2017-03-09 Published:2017-03-20

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

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

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

中图分类号: