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

A Min-conflict Weight-learning Algorithm for Graph Coloring Problem

作　　者：朱文兴[1] 张千里[1] 

机构地区：[1]福州大学计算机科学与技术系,福建福州350002

出　　处：《小型微型计算机系统》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 )资助

摘　　要：图着色问题 (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.

关 键 词：图着色 GSAT 权值学习 交叉算子 局部搜索 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]