基于独立集划分的图着色算法

摘要：

针对经典的图着色问题,在顶点集随机划分的基础上,设计了一种寻求集合个数最少的独立集划分遗传算法.运行算法获得的独立集个数即为图的色数.算法引入了模块化函数思想,采用了单向传递交叉算子.通过贪婪局部优化初始种群和杂交后代个体,使算法具有较好的收敛速度.对四个经典算例的仿真结果表明,本文提出的算法可获得问题的高质量解,是一种有潜力的算法.

关键词：图着色、遗传算法、单向传递交叉

所属期刊栏目：15

分类号：TP18(自动化基础理论)

资助基金：上海市重点学科建设项目S30501;上海市研究生创新基金项目JWCXSL0902

在线出版日期：2011-01-28（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：95-98,103