摘要
图着色问题 (GCP)是 NP完全问题 .近年来求解 GCP的启发式局部搜索算法引起人们的关注 ,GSAT是最著名的局部搜索算法之一 .许多局部搜索算法引入跳出局部极小的机制来提高搜索效率 ,权值学习是一种被广泛采用的方式之一 .我们从一些权值学习局部搜索算法抽象出一个通用的权值学习算法 (SWL A) ,进一步把 SWL A和 GSAT相结合提出了最小冲突权值学习算法 (MCWL A) ,算法还应用还原策略和“权值交叉”算子来提高搜索后期的效率 .算法在求解一些难解测试范例时显示出较高的效率 ,能求得 GSAT及 SWL A无法求得的最优解 .
Graph Coloring problem (GCP) is an NP hard problem. Solving GCP by heuristic local search algorithm has received a lot of attention in the last few years. Among them GSAT is the most famous one. Various local search algorithms incorporate schemes that enhance local search to escape from local minima. Weight-learning is one of the most widely adopted method. The SWLA , which is a general algorithm abstracted from some Weight-learning local search algorithms by us, can solve combinatorial optimization problem effectively. The MCWLA presented in this paper is an extension of GSAT and SWLA for GCP,which use 'Weight Crossover' operator and 'restore strategy' to avoid the inefficiency during later local search period. The performance of the MCWLA is efficient in solving some difficult GCP benchmarks. Moreover, the algorithm can find the optimal solution while GSAT and SWLA can not.
出处
《小型微型计算机系统》
CSCD
北大核心
2004年第1期72-75,共4页
Journal of Chinese Computer Systems
基金
国家 973项目 (G19980 3 0 60 0 )资助
福建省自然科学基金 (A0 0 10 0 10 )资助
福建省教育厅科技开发基金(JA0 0 14 3 )资助
关键词
图着色
GSAT
权值学习
交叉算子
局部搜索
graph coloring
GSAT
weight learning
crossover operator
local search
