Dissertation > Excellent graduate degree dissertation topics show

Research and Implementation of tabu search algorithm based graph coloring

Author: MaYanPing
Tutor: WuXiaoJun
School: Shaanxi Normal University
Course: Applied Computer Technology
Keywords: Intelligent Optimization Algorithm Tabu Search Graph vertex coloring Improved Algorithm
CLC: TP301.6
Type: Master's thesis
Year: 2011
Downloads: 165
Quote: 1
Read: Download Dissertation

Abstract


Tabu search (Tabu Search, TS) is a relatively new intelligent optimization algorithms, and genetic algorithms (GA), particle swarm optimization algorithm (PSO), ant colony algorithm (ACS), are included in the Natural Computation (Natural Computation ) range. The algorithm uses the generic algorithm framework, flexible storage structure and the corresponding taboo guidelines can be as much as possible to avoid the algorithm into a cycle search in solving combinatorial optimization problems and function optimization attracted the attention of many scholars within the field. With the continuous development of computer science, graph and human life are getting closer, a lot of problems in the real world can be attributed to the point and line graphics, many scholars introducing graph theory to solve the engineering applications a lot of problems. In recent years in the engineering field of study and application of the diagram more and more attention has been paid, therefore, is very meaningful tabu search algorithm to solve the graph coloring problem. In this paper, the theoretical framework for the understanding of the basic tabu search algorithm based on tabu search algorithm in graph coloring problem focuses on. In this paper, tabu search algorithm for the vertex coloring problem combination the algorithm framework Figure vertex coloring problem solution space mapping, application of traditional tabu search algorithm to solve the vertices of the graph coloring problem, the analysis of simulation results, the evaluation algorithm time complexity . In addition, this article analyzes the traditional taboo search algorithm, traditional tabu search algorithm improvements, improved hybrid tabu search algorithm to solve the vertex coloring problem, simulation experiments, the experimental effect is remarkable. Thesis work and innovation can be summarized as the following: (1) describe and analyze the operating parameters of the tabu search algorithm, combined with the theoretical framework of tabu search algorithm with graph vertex coloring problem constraints, the first traditional tabu search algorithm to solve typical graph vertex coloring problem, a tabu search algorithm to solve the graph vertex coloring algorithm model. (2) Further study tabu search algorithm, analysis of the deficiencies of traditional tabu search algorithm embodied in the theory and practical application, such as the initial solution to to treat dependence solve the problem, search iteration serializability paper for combined SEQ algorithm, an improved tabu search algorithm to solve the graph vertex coloring problem the better programs, simulation results show that the improved algorithm is better. (3) Based on the traditional taboo search algorithm with improved tabu search algorithm applied research paper on its analyzed and summarized in the application of traditional tabu search algorithm reflected the shortcomings of the proposed algorithm improvement programs, and in theory on the prospect of its application prospects.

Related Dissertations

  1. Research on Simultaneous Cyclic Scheduling and Optimization Poblems of the Refinery CSTR Processing,F273
  2. The Decision Support System for Production and Logistics Operation Management in Metallurgical Enterprises,F426.32
  3. The Research of Signal Detecting Algorithms and Improved Sphere Detecting Algorithms in MIMO Systems,TN919.3
  4. Multi Rules Production Scheduling Simulation Optimization in Discrete Manufacturing System,F273
  5. Robust Resource Scheduling Approach and Application in Satellite Scheduling,V474.26
  6. Research on Intelligent Optimization Algorithm and Its Application in Communication,TN92
  7. Research on Anycast Routing Algorithm with Multiple QoS Parameters Constraint,TP393.02
  8. A Dynamic Hardware-software Partitioning Algorithm Based on Reconfigurable System,TN791
  9. The hydrometallurgy electrolysis process energy consumption optimization Control Research and application,TF813
  10. Utilization Research of Neural Networks for the Caster Surface Quality Prediction Model,TF777
  11. The Scheduling for Hot-Chain Logistics and Energy in Iron and Steel Industry,F252
  12. Modeling to Ship-stowage Logistics Planning of Finished Steel Coils and Its System Development,TF758
  13. Short-Term Load Forecasting Study Based on Neural Network,TM715
  14. Research on Selecting and Scheduling Observations of Agile Satellites,V448.2
  15. Job Shop Scheduling Problem Based on Immune Clonal Selection Algorithm,TP18
  16. Evolutionary Algorithm for Motif Discovery,TP18
  17. A Research of Multi-object Grid Task Scheduling Based on Niche-genetic-tabu Search Algorithms,TP393.02
  18. Research on QoS Based Multicast Routing Algorithms,TP393.09
  19. Memetic Algorithm Based on Content-Based Image Retrieval,TP391.41
  20. Cellular Particle Swarm Optimization and Its Applications on Flexible Job Shop Scheduling Problem,TP301.6
  21. Study on Some Theories of DNA Computing,TP301.6

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > General issues > Theories, methods > Algorithm Theory
© 2012 www.DissertationTopic.Net  Mobile