图着色问题的一个最小冲突权值学习算法

• 作者: 张千里 朱文兴
• 来源期刊: 小型微型计算机系统
• 学科: 工学
• 关键词: 图着色 GSAT 权值学习 交叉算子 局部搜索
• 年，卷（期）: 2004,（1）
• 页码范围: 72-75
• 页数: 4页
• 分类号: TP18
• 字数: 4572字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-1220.2004.01.017

摘要

图着色问题(GCP)是NP完全问题. 近年来求解GCP的启发式局部搜索算法引起人们的关注,GSAT是最著名的局部搜索算法之一. 许多局部搜索算法引入跳出局部极小的机制来提高搜索效率,权值学习是一种被广泛采用的方式之一. 我们从一些权值学习局部搜索算法抽象出一个通用的权值学习算法(SWLA),进一步把SWLA和GSAT相结合提出了最小冲突权值学习算法(MCWLA),算法还应用还原策略和"权值交叉"算子来提高搜索后期的效率. 算法在求解一些难解测试范例时显示出较高的效率,能求得GSAT及SWLA无法求得的最优解.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	朱文兴	福州大学计算机科学与技术系	44	465	10.0	21.0
2	张千里	福州大学计算机科学与技术系	3	48	2.0	3.0