Abstract: The graph coloring problem is an NP-hard problem,which has a wide range of applications in reality,such as register allocation,airport scheduling and so on.Tabu search algorithm is a classic heuristic search algorithm,which is widely used in the algorithm design of graph coloring problems.As a low-level operator,the tabu search algorithm is also commonly used in the design of graph coloring algorithms such as hybrid evolutionary algorithm(HEA),which plays a key role in the performance of the algorithm.Therefore,the improvement of the tabu search algorithm has practical significance for promoting the research of graph coloring algorithm.Aiming at the problem of graph coloring,this paper proposes an improved version of Tabucol+ to enhance the concentration of search.Based on the traditional tabu search strategy,the proposed algorithm introduces a new scoring strategy.Experimental results show that the new algorithm can significantly reduce the number of iterations andsearch time.In some cases,even the improvement of the number of colors has been achieved.

Key words: Tabu search algorithm, Graph coloring problem, Vertices with the same score