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

摘要

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