Hits:

Indexed by:期刊论文

Date of Publication:2007-11-21

Journal:计算机工程与应用

Included Journals:PKU、ISTIC、CSCD

Volume:43

Issue:33

Page Number:43-45

ISSN No.:1002-8331

Key Words:图着色问题;NP-难解;部分解;扰动

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