求解GCP问题的ILSBR算法

摘要：

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

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

所属期刊栏目：43

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金90412007;60503003;辽宁省自然科学基金20051082;大连理工大学青年教师培训基金

在线出版日期：2008-01-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：43-45