Computer Engineering and Applications ›› 2007, Vol. 43 ›› Issue (33): 43-45.

• 学术探讨 • Previous Articles     Next Articles

ILSBR algorithm for graph coloring problem

TIAN Rui-xing,JIANG He   

  1. School of Software,Dalian University of Technology,Dalian,Liaoning 116621,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-11-21 Published:2007-11-21
  • Contact: TIAN Rui-xing

求解GCP问题的ILSBR算法

田瑞兴,江 贺   

  1. 大连理工大学 软件学院,辽宁 大连 116621
  • 通讯作者: 田瑞兴

Abstract: Graph Coloring Problem(GCP) is one of the typical NP-hard problems in combinatorial optimization problem.The fast and effective approximate algorithms are needed to solve the large scale problem in reasonable computing time.The known approximate algorithm can not give a good enough solution for larger instance in reasonable time.So ILS based Relation of local optimal and global coloring(ILSBR) is proposed.The algorithm is based on the analysis of the relation of local optimal and global optimal coloring of the GCP finding that the partial solution of the global optimal solution is obtained by a very high probability through intersecting the local optimal solutions.Using the partial solution could construct a kind of perturbation strategy(RLG Re-coloring) which then is applied to Iterated Local Search.The experimental results on DIMACS benchmark show that the ILS outperforms the known best ones in the running time without decreasing in the quality of solutions.

Key words: GCP, NP-hard, partial solution, perturbation

摘要: 图着色问题(GCP,Graph Coloring Problem)是经典的NP-Hard组合优化问题之一。长期以来,人们一直在寻求快速、高效的启发式算法,以便在合理的计算时间内解决大规模问题。由于对规模较大的问题,目前的启发式算法尚不能在较短的时间内给出高质量的解,因此提出了一种基于全局最优解和局部最优解关系的ILS算法(ILSBR)。该算法的基本原理是通过对GCP问题的局部最优解和全局最优解之间关系的分析,发现对局部最优解的简单的相交操作能以很高的概率得到全局最优解的部分解。利用这些部分解构造一种新的扰动策略(RLG重着色),并将其应用到传统的ILS算法中。在DIMACS标准集中,典型实例上的实验结果表明,采用RBILS算法在求解质量不变的情况下,求解速度上与目前的已知算法相比有较大的改进。

关键词: 图着色问题, NP-难解, 部分解, 扰动