Dissertation > Excellent graduate degree dissertation topics show

Graph Vertex Coloring Problem Algorithm Based on Particle Swarm Optimization

Author: WangXiaoQiong
Tutor: XuJin
School: Huazhong University of Science and Technology
Course: Systems Engineering
Keywords: Figure vertex shader Particle swarm optimization Genetic Algorithms Simulated annealing algorithm
CLC: TP18
Type: Master's thesis
Year: 2007
Downloads: 98
Quote: 1
Read: Download Dissertation

Abstract


Combinatorial optimization is an emerging field , with mathematical optimization as an important part of operations research , and emphasis on the application of mathematics . A typical problem in Figure combinatorial optimization problems , namely vertex coloring problem . The vertices of the graph coloring problem is a typical NP-complete combinatorial problems in scheduling arrangements and timetable for the preparation of many applications to construct the figure, find the vertex coloring problem approximate optimal algorithm has important practical significance . The particle swarm algorithm is a new random optimization algorithm based on swarm intelligence , its most attractive features is simple and easy to implement compared with other evolutionary algorithms and stronger global optimization capability . To this end , the particle swarm algorithm has been proposed , immediately aroused extensive attention of scholars in other fields as evolutionary computation , a lot of research and in a few years time , the formation of a research hotspot in function optimization , neural networks training , industrial system optimization and fuzzy system control and other fields has been widely used . In this paper, a graph vertex coloring of the standard particle swarm algorithm , designed vertex coloring problem encoding method and fitness function to determine the particle swarm flight . Standard particle swarm into local optimum and overcome by the introduction of the simulated annealing algorithm to improve the search performance of particle groups . Subsequently, through the study of the nature of the evolution equation of particle swarm flight speed by the corresponding part of the evolutionary characteristics and genetic algorithms analogies design genetic particle swarm optimization , crossover and mutation operator by the genetic algorithm , the same implementation of the profile of the particle velocity . And the experimental results prove that this genetic particle swarm optimization vertex coloring problem better than the accuracy of the standard particle swarm algorithm to search . However, due to the lack of genetic algorithms in the convergence rate , we added in the particle flight simulated annealing operator to significantly improve the speed of convergence of the algorithm .

Related Dissertations

  1. Research on Feature Extraction and Classification of Tongue Shape and Tooth-Marked Tongue in TCM Tongue Diagnosis,TP391.41
  2. Computing Minimum Distance between Curves/Surfaces Based on PSO Algorithm,O182
  3. Development of the on-line Training and Examination System of Army,TP311.52
  4. Designs and Applications of Fuzzy Synthetic Evaluation Models Based on Parallel Algorithms,TP18
  5. Active Power Filter and Its Application in Distribution Network,TN713.8
  6. Research on Fuzzy C-Mean Clustering Algorithm Based on Particle Swarm Optimization and Shuffled Frog Leaping Algorithm,TP18
  7. Based on Genetic Algorithm Pishihang irrigation canal water allocation marshalling model of,S274
  8. Genetic Algorithm in logistics and warehousing Optimization Research,F259.2
  9. Mining resources based on genetic algorithm optimization model of,O224
  10. Research on the Improvements and Applications of Particle Swarm Optimization,TP18
  11. Segmentation of cDNA Microarray Image Using Fuzzy C-means Algorithm Optimized by Particle Swarm,TP391.41
  12. The Research and Application of Modified Algorithms About Fuzzy Predictive Functional Control,TP273
  13. Study on Electromagnetic Bandgap Structure with Bow-tie Units,TN454
  14. Research on Medical Image Segmentation Method Based on Markov Random Field Model,TP391.41
  15. Research on Modification and Application of Particle Swarm Optimization Algorithm Based on Control Methods,TP301.6
  16. Optimal Control of Emulsion System in Cold Rolling,TP273
  17. Research on the Marshalling-scheduling Model and Algorithms of Freight Trains Based on Game Theory,O225
  18. Multi-directional Mutation Genetic Algorithm and Research on Neural Network Optimization,TP18
  19. The Application of Using Genetic Algorithms on Universities Course-arranging System,TP18
  20. Research on Mobile Robot Path Planning and Simulation Realization,TP242
  21. Research on Routing Algorithmin Sensor Networks Based on Cluster with Mobile Sink,TP212.9

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