论文部分内容阅读
图着色问题（GCP，Graph Coloring Problem）是经典的NP-Hard组合优化问题之一。长期以来，人们一直在寻求快速、高效的启发式算法，以便在合理的计算时间内解决大规模问题。由于对规模较大的问题，目前的启发式算法尚不能在较短的时间内给出高质量的解，因此提出了一种基于全局最优解和局部最优解关系的ILS算法（ILSBR）。该算法的基本原理是通过对GCP问题的局部最优解和全局最优解之间关系的分析，发现对局部最优解的简单的相交操作能以很高的概率得到全局最优解的部分解。利用这些部分解构造一种新的扰