解决图着色问题的一种新禁忌搜索算法

摘要

In this paper, in order to find the global optimum of a typical combinatorial optimisation problem, colouring the vertices of a graph, we propose a new Tabu search algorithm, SEQTS, based on enhanced SEQ in combination with the advantages and disadvantages of the enhanced SEQ algorithm and Tabu search algorithm. It uses the strong capability of the enhanced SEQ algorithm in structuring optimal solution to construct multiple initial optimum solutions for Tabu search algorithm at first, and then performs Tabu search on these initial solutions for getting global optimum. It is proved by computer experimental results that this new algorithm (SEQTS) has preferable search ability which strengthens its effectiveness.%为了解决典型的组合优化问题——图顶点着色问题,结合增强SEQ算法和禁忌搜索算法的优点与缺点,提出一种基于增强SEQ的新禁忌搜索算法(SEQTS).该算法利用增强SEQ算法较强的构造较优解的能力来为禁忌搜索算法构造多个较优初始解,然后进行多初始解禁忌搜索以找到全局最优解.计算机实验的结果表明该算法(SEQTS)有较好的寻优能力,增强了该算法的有效性.