Research And Implementation Based On Tabu Search Algorithm For Graph Coloring

Tabu Search (Tabu Search or Taboo Search, TS) is a relatively new intelligent optimization algorithm. It is the same as genetic algorithm (GA), particle swarm optimization (PSO), ant colony algorithm (ACS), and so on, included in natural computation (Natural Computation). Tabu search algorithm, its more general algorithm framework, flexible storage structure and the corresponding tabu criteria could avoid its searching process into a cycle. Because of this point, tabu search algorithm causes widespread attention by many scholars. As the continuous development of computer science, graph and human lives are closely linked. In reality, many problems can be attributed to the composition of points and lines like graph problems. So, many scholars introduced graph into engineering application area and to simplify some problems using graph model. Therefore, in recent years, more and more people pay attention to the graph applications and have been attracted to study it in engineering application area. It is very meaningful to solve graph coloring problem using tabu search algorithm.Based on comprehension of the theoretical framework of tabu search algorithm, in this paper, it is the key to research the application of tabu search algorithm to solve the graph coloring problem. In this paper, it connects with tabu search algorithm and graph coloring problem, established a map for the algorithm framework and the solution space of the problem, using traditional tabu search algorithm to solve the problem, and do simulation experiments, and then analysis the result of simulation experiment, and at last evaluate the time complexity. In addition, in this paper, it improves the traditional tabu search algorithm and using the mixed tabu search algorithm for simulating experiment to solve the graph vertex coloring problem. The experimental result proved that it is considerable. In this paper, the main work and creative points could be summarized as follows:(1) Deeply understand the basic theory of tabu search algorithm in this paper, and explain and analysis the operating parameters of tabu search algorithm, in this paper, it Combines the theoretical framework of tabu search algorithm with the constraints of the graph vertex coloring problem, using tabu search algorithm to solve the classical graph vertex coloring problem. According to the constraints of solving the graph vertex coloring problem, at first, it establishes a model to work out the graph vertex coloring problem, taking advantage of tabu search algorithm.(2) Further study of traditional tabu search algorithm and analysis of its disadvantage in practical application theoretically, it proposed an improved tabu search algorithm to solve graph vertex coloring problem. Traditional tabu search algorithm is not very perfect, and has some disadvantages, such as its initial solution strongly dependent to the problem, and the serial search characteristic of itself. Point to these shortages of traditional tabu search algorithm, in this paper, it connects the SEQ algorithm, and puts forward a much better way to solve graph vertex coloring problem. The experimental result proved that this new way could get better effects.(3) Based on the applications of traditional and the improved tabu search algorithm, in this paper, it gives the analysis and summary. And according to the disadvantages reflected in these applications, in this paper, it raises some improved methods, and discusses the prospect of its application in theory.