Dissertation > Excellent graduate degree dissertation topics show

Hybrid Genetic Algorithms for Graph Coloring Problems

Author: LanShaoJiang
Tutor: WangYuPing
School: Xi'an University of Electronic Science and Technology
Course: Operational Research and Cybernetics
Keywords: Graph Coloring Problem Hybrid Genetic Algorithm NP- complete problem Compact genetic algorithm Probability matrix
CLC: TP18
Type: Master's thesis
Year: 2008
Downloads: 125
Quote: 1
Read: Download Dissertation

Abstract


The genetic algorithm is to simulate the natural process of biological evolution and mechanisms to solve the optimization problem for a class of self-organizing , adaptive random search algorithm , coding techniques and genetic manipulation is relatively simple, low requirements on the optimization problem of restrictive conditions , with strong parallel and global search capability . Can solve many practical problems , has been in machine learning , pattern recognition , image processing, optimizing control, portfolio optimization and management decision-making and other fields has been very good application . First, the graph coloring problem is a classic NP- complete problem . The essential characteristics of the graph coloring problem vertex by individual initialization method based on the degree of the population , and the intersection of the crossover operator ; designed to speed up the convergence rate of the algorithm , a new greedy local search operator to improve hybridization produces offspring . On this basis , a new hybrid genetic algorithm for solving the graph coloring problem , and 10 standard operator example simulation results show that the new hybrid genetic algorithm can obtain high quality solutions of the problem , is a potential algorithm . Secondly, based on the characteristics of vertex split , A new solution for the graph coloring problem . Probability matrix populations in the solution , greatly save storage space ; combined in order to speed up the convergence rate of the algorithm , a local search operator to improve the quality of the hybrid offspring ; probability matrix elements take 1 or 0:00 , the algorithm stops. Simulation of the standard graph coloring problem , and compare with existing algorithms , the results show that the new algorithm solving performance , and fast convergence .

Related Dissertations

  1. The Research of the Asphalt Pavement Evaluation Index of Xinjiang between the Handing Over and Completion of Test Datas and the PCI Grade,U416.217
  2. Study of the Dynamic Orders Scheduling Based on Mixed-GA,TH163
  3. Research on Qos Routing Constraint Problems Based on GA_ACO Algorithm,TP393.02
  4. Optimizing Empty Container Allocation Based on Hybrid Genetic Algorithm,U695.22
  5. Study on Optimization of the Reservoir Operation Chart of Hydropower Stations,TV697.11
  6. Binary optics design and craftsmanship,TH74
  7. Research and Application of DNA Computing Model Based on Plasmids,Q523
  8. Study on the Optimal Algorithm of Parameters of Power System Stabilizer,TM44
  9. Hybrid Genetic Algorithm for Bin Packing,TP18
  10. Two Supply Chain Optimal Models and Optimization Algorithms,F224
  11. Study on Selective Assembly Method and Application of Mechanical Products in Modern Manufacturing Environment,TH122
  12. The Research of Protein Configuration Forecasting Based on Mixed Genetic Algorithm,Q51-33
  13. Portal users browsing behaviors in,F49
  14. Research of Multicast Routing Algorithms with QoS Constraint Based on IP Network,TN915.02
  15. The Integrated Research on Intelligent Distribution System of Logistics,F253
  16. Multigroup annealing greed Research and Application of hybrid genetic algorithm,TP18
  17. Logistics Scheduling Optimization Model and Its Application,F252
  18. Research on Method of Physical Recombination Optimization of Manufacture Resource,TH16
  19. Research on the Vehicle Scheduling Optimization of the Logistics Distribution with Real-Time Demand Information,F253.4
  20. Free-floating space robot system dynamic control of arms,TP242

CLC: > Industrial Technology > Automation technology,computer technology > Automated basic theory > Artificial intelligence theory
© 2012 www.DissertationTopic.Net  Mobile