Solving Graph Coloring Problem Based On Tabu Search Algorithm

The graph coloring problem is one of the most well-known NP-hard problems,which is of great significance in both practical applications and theoretical research.At present,there are two main methods to solve the graph coloring problem,exact and heuristic.Heuristic algorithms have fast solving ability and strong generality,and can usually find optimal or near-optimal solutions in practical problems.Tabu search algo-rithm is a heuristic algorithm,which can be applied to graph coloring problems to bring high-quality solutions,named Tabucol.Tabu search algorithm is realized by introduc-ing tabu list and corresponding management rules on the basis of local search.It effec-tively avoids the problem of search falling into local loops and has excellent global optimization ability.The centrality and evacuation of the heuristic algorithm in the search process are the key factors.The centrality is a high-intensity search in the solu-tion space within a certain range according to the inherent laws of the algorithm.The evacuation brings diversification and new solution space regions.The balance of users is the guarantee of algorithm performance.This paper proposes two improved tabu search algorithms for graph coloring prob-lems,and conducts comparative experiments on more than 100 common DIMACS graphs.The experimental results show that these two algorithms can significantly re-duce the number of iterations,improve the success rate,and even some calculations For example,the number of colors has been improved.The first improved algorithm,Tabu-col+,is based on the classic Tabucol and introduces a new scoring strategy to mark more beneficial dyeing actions,and increase their proportion during the dyeing process to improve the overall performance of the algorithm.The second improved algorithm,Tabucol*,is based on the classic Tabucol and introduces a new selection mechanism to screen out more valuable dyeing actions.It effectively avoids potential conflicting edges by reducing the number of adjacent points of the same color.form.The improved algorithms designed in this paper all introduce centrality on the basis of the classic graph coloring tabu search algorithm,and strictly control the influence of centrality to retain enough random samples,which is meaningful for the current best Tabucol algo-rithm.improvement of.The work done in this paper facilitates the optimization of hy-brid heuristics and the solution of related engineering problems.