用混合遗传算法求解图的邻强边着色问题

• 作者: 刘会新 王淑栋 许进
• 来源期刊: 系统工程与电子技术
• 学科: 工学
• 关键词: 邻强边着色 邻强边色数 遗传算法 NP-完全问题
• 年，卷（期）: 2003,（5）
• 所属期刊栏目: 软件、算法与仿真
• 页码范围: 617-620
• 页数: 4页
• 分类号: O29|TB11
• 字数: 3790字
• 语种: 中文
• DOI: 10.3321/j.issn:1001-506X.2003.05.028

摘要

图的邻强边着色算法是一个NP-完全问题.提出了图的邻强边着色问题的混合遗传算法.在设计交叉、变异方式时,将两点交叉与局部扫描结合起来,避免了种群的退化,从而有利于快速找到最好的解域.根据实际情况,将图的结构性质和迭代次数结合起来,巧妙地设计了算法的终止条件.实验仿真结果表明,混合遗传算法可以获得问题高质量的解,即对图进行邻强边着色所使用的颜色数接近图的邻强边色数.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许进	华中科技大学控制科学与工程系	117	2149	25.0	39.0
2	王淑栋	华中科技大学控制科学与工程系	30	316	10.0	17.0
6	刘会新	华中科技大学控制科学与工程系	6	85	5.0	6.0