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

An Improved Genetic Algorithm for Solving Graph Coloring Problem

作　　者：李凯[1] 

机构地区：[1]广州大学教务处,广东广州510000

出　　处：《计算机与现代化》2017年第2期6-11,共6页Computer and Modernization

基　　金：国家自然科学基金资助项目(71402036);广州大学教育教学研究项目(JY201545)

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

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]